From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA18136; Tue, 24 Sep 2002 15:23:04 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA15916 for ; Tue, 24 Sep 2002 15:23:03 +0200 (MET DST) Received: from athlon.baretta.com (host121-68.pool80116.interbusiness.it [80.116.68.121]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g8ODN2D11221 for ; Tue, 24 Sep 2002 15:23:02 +0200 (MET DST) Received: from baretta.com (localhost.localdomain [127.0.0.1]) by athlon.baretta.com (Postfix) with ESMTP id 7830B27399; Tue, 24 Sep 2002 15:32:35 +0200 (CEST) Message-ID: <3D906973.5020909@baretta.com> Date: Tue, 24 Sep 2002 15:32:35 +0200 From: Alessandro Baretta Organization: Baretta srl -- www.baretta.com User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 X-Accept-Language: it, en MIME-Version: 1.0 To: "M E Leypold @ labnet" , Ocaml Subject: Re: [Caml-list] Re: Wasn't O'Caml a functional language? References: <3D8CF6F8.2050904@baretta.com> <15756.65084.40025.869484@spike.artisan.com> <3D8D050F.9000108@baretta.com> <871y7m1wlv.fsf@ketanu.dyndns.org> <3D90263D.2010706@baretta.com> <15760.15527.648990.807473@hod.void.org> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk M E Leypold @ labnet wrote: > > Hello, > > Alessandro Baretta writes: > > <...> > >> is equivalent to f e1; f e2; f e3 >> >> which is correct with respect to what I need. This is >> the reason for using Queues. I somehow expected this to >> be the only difference with respect to Lists, and did >> not suspect that some of the functions of the Queue >> module (other than the obvious add and take) had >> side-effects. I realize that > > I'm not so very much surprised. Let's look at stacks. A > stack is algebraically equivalent to a list (Queues > aren't, that's whay I'm talking about stacks for a > moment). ... Alright. AFAIK, the stack is the fundamental data structure holding the state of a program in all procedural languages. A stack is something very intrinsically procedural in nature. A queue is not. From a functional point of view, that is, if you disregard "operations" on queues, and forget how they are built -- for they are built in a sequential, as opposed to recursive, manner -- you can just state that a queue is a sequence of data whose iterators act upon in direct, as opposed to inverse, order of construction. Of course, such a behavior can be achieved using lists and a recursive data-structure-traversal to generate them, but for some uses a data type with a FIFO nature is just easier to imagine and work with. When I looked at the Queue.transfer function, I was not looking for a means of implementing a transition in an abstract state machine. I was looking for an implementation of the abstract operation of concatenation on the free monoid of the sequences of elementary data tokens of a given type. Alright, "transfer" is a name that quite transparently maps to something a little different, but somehow I just overlooked the side-effect. > Now, queues are containers, so I'd expect side-effects > and in-place update of state. In computer science, a data type is usually defined as a set of values and a set of operations on it. This definition coincidentally is the definition of an algebraic structure. The algebraic structure I need to work with consists of the set of sequences of elementary data tokens. So, you see, I'm not really interested in the state model for Queues. > Of course this is all very > imperative and not functional, but in a sense all ML > dialects seem not to be pure in that respect. (OK, don't > shoot me for the use of 'pure' here: I'm not a computer > scientist, so I might use the word wrongly). BANG! ;) Yes, ML is not purely functional, whatever that means, because you can show that "pure" lambda calculus (having only the lamda-abstraction operator and function application) has the full expressive power of a full-fledged procedural language. You can simulate let-bindings with lambda-abstraction and function application ( let t = M in N <=> (\t.N) M). You can simulate operation sequences with let bindings (let foo1 = M1 N1 in let foo2 = M2 N2 in ...). You can simulate any loop with a while loop and a while loop with with recursion (letrec f = if M then N else f). Finally, you can simulate recursion with lambda-abstraction and function application (http://www.enseignement.polytechnique.fr/informatique/M2/lp/a1.html). > As far as your original problem is concerned: I think a > purely functional and efficient 'queue' is not so easy to > be implemented: you can't share the tail in such a nice > way as lists do. At least: not as easy. > > Regards -- Markus On the contrary, if no destructive operations exist on a datastructure, aliasing is never a problem. However, the meaning of "destructive" has to be defined. Alex ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners