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.
pgp59oQAJMacK.pgp
Description: PGP signature
____________________ BYU Unix Users Group http://uug.byu.edu/ ___________________________________________________________________ List Info: http://uug.byu.edu/cgi-bin/mailman/listinfo/uug-list
