Thanks for sharing. That's great. And I actually remembered most of
it from my OCaml cramming for 330. It is a cool language that I need
to study more. I'm still not sure if I'm happy with functional
languages in general, but they certainly are powerful. The problem is
that when you first look at source code it is usually quite difficult
to figure out what it's doing. After a while though, I'm confident
that it would become easier. It's just a matter of taking the plunge.
On Wed, 14 Jul 2004 21:37:50 -0500, Michael Halcrow <[EMAIL PROTECTED]> wrote:
> Computer scientists on the list: sit and gaze in awe at the mighty
> powers of OCaml. Just for the fun of it, I sat down and hammered out
> a binary tree-ish implementation in OCaml. Here it is below, with
> line-by-line Action Commentary (TM).
>
> (* Pseudo-Binary Tree, an Happy Fun OCaml Experiment (HFOE)
> Written by Michael Halcrow *)
>
> type 'a bintree = Empty | Tree of 'a bintree * 'a * 'a bintree;;
>
> (* 'a means dynamic type selection; because it's used with a <
> operator on an int list in the insert_value function, it takes form as
> an int via type inference. Think of this as an enum. The a * b * c
> results in a tuple (a,b,c) - it's a recursive definition. Think
> context-free grammer. If you have no idea what I'm talking about,
> take CS252. *)
>
> let l = [ 3 ; 9 ; 1 ; 4 ; 2 ; 5 ] in
>
> (* an int list *)
>
> let rec insert_value value tree =
>
> (* rec clues the ocaml compiler into the fact that this function calls
> itself *)
>
> match tree with
>
> (* Pattern matching! Only with something other than strings! Yay! *)
>
> Empty ->
>
> (* The first pattern to attempt a match. The Magic Type-Infering
> Engine (MTIE)(TM) figures out that the tree parameter is of type 'a
> bintree at this point *)
>
> begin
>
> (* syntactic sugar; think of this as a scope delimiter *)
>
> Printf.printf "Empty\n";
> Tree (Empty,value,Empty)
>
> (* This is a return value *)
>
> end
> | Tree (l,v,r) -> if value < v then
>
> (* If Empty didn't match, this will. It assigns aliases to the
> elements of the tuple. BTW, the _ character is the catch-all for these
> match expressions, in case you manage to build an incomplete matching
> set someday. *)
>
> begin
> Printf.printf "Inserting left: [%d]\n" value;
> Tree (insert_value value l,v,r)
>
> (* Here is where the recursive action takes place. Note that this is
> tail-recursive. This means that no activation record will be created
> for this call (C programmers, pay attention)! We could operate on an
> infinitely big tree and never run out of memory. *)
>
> end
> else
> begin
> Printf.printf "Inserting right: [%d]\n" value;
> Tree (l,v,insert_value value r)
> end in
>
> (* The ``in'' part limits scope for the variants (not variables -
> there are no variables in OCaml) and function definitions *)
>
> let rec buildtree lst head =
>
> (* This is really shorthand for ``let rec buildtree = function lst ->
> function head ->''; OCaml functions can really only have one
> parameter. Currying is the name of the game, boys and girls. *)
>
> match lst with
> [] -> head
>
> (* The Terminating Condition (TC)(TM). Just return the list in its
> current form. *)
>
> | hd::tl -> buildtree tl (insert_value hd head) in
>
> (* :: is the cons operator, for those Lisp programmers in the
> audience. We have the first element on the list, and the remainder of
> the list, aliased by hd and tl, respectively. Here is have a nested
> recursive function call. insert_value will, serendipitously, return a
> new list with the head of the list correctly inserted, and buildtree
> will pass that along in the following (tail-recursive) call to
> buildtree. *)
>
> let rec printtree tree =
> match tree with
> Empty -> ""
> | Tree (l,v,r) -> String.concat "" [ (string_of_int v); "(" ;
> (printtree l); ")" ; "(" ; (printtree r) ; ")" ] in
>
> (* Have you ever before seen such elegance? *)
>
> let thistree = buildtree l Empty in
> Printf.printf "Done: %s\n" (printtree thistree)
>
> (* End program. *)
>
> We haven't even gotten started with polymorphic variants,
> subject/observer patterns, optional labels, or the many other fun
> aspects of OCaml. Stay tuned for more OCaml excitement, coming your
> way!
>
> If anyone wants to modify this to keep the tree balanced, go for it!
> :-P
>
> Now entirely free of segfaults, ClassCastExceptions, and
> NullPointerReferences, and loving life,
> Mike
> .___________________________________________________________________.
> Michael A. Halcrow
> Security Software Engineer, IBM Linux Technology Center
> GnuPG Fingerprint: 05B5 08A8 713A 64C1 D35D 2371 2D3C FDDA 3EB6 601D
>
> I am not a "consumer." I am a CITIZEN of the United States of
> America.
>
>
____________________
BYU Unix Users Group
http://uug.byu.edu/
___________________________________________________________________
List Info: http://uug.byu.edu/cgi-bin/mailman/listinfo/uug-list
