[Camllist] Wasn't O'Caml a functional language?

Alessandro Baretta

Alessandro Baretta

Michaël_Grünewald
 Pixel

Alessandro Baretta
 Alessandro Baretta

Michaël_Grünewald

Alessandro Baretta
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20020924 (13:23) 
From:  Alessandro Baretta <alex@b...> 
Subject:  Re: [Camllist] Re: Wasn't O'Caml a functional language? 
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 >> sideeffects. 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 datastructuretraversal 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 sideeffect. > Now, queues are containers, so I'd expect sideeffects > and inplace 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 lamdaabstraction operator and function application) has the full expressive power of a fullfledged procedural language. You can simulate letbindings with lambdaabstraction 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 lambdaabstraction 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners