# ImperialViolet

### O'Caml (07 Sep 2002)

After a brief holiday, The Memory Hole is ticking again.

People keep talking about it and it's high time that I looked into it. O'Caml is an ML based language and has all the standard ML language stuff (curried functions etc). It uses inferred typing, which is very useful, despite the few drawbacks (more on that later).

It also has polymorphic typing:

```# let f = function (a, b) -> a;;
val f : 'a * 'b -> 'a = <fun>```

That function takes a 2-tuple of any type and returns the first element and polymorphically works within the type-system.

There is a translation of a French O'Reilly O'Caml book online, but I find it's a little heavy for a introductionary text. I find that this book it nicer to start with. Maybe move on the O'Reilly book afterwards.

This code snippet, which implements red-black binary tree insertion, should demonstrate the power of O'Caml even if you don't understand it. (This assumes you've seen what a mess a red-black insert looks like in C/C++. If not, see this, and I have reasonable reason to suspect there's an error in there since it was done partly from CLR).

```let balance = function
Black, Node (Red, Node (Red, a, x, b), y, c), z, d ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| Black, Node (Red, a, x, Node (Red, b, y, c)), z, d ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| Black, a, x, Node (Red, Node (Red, b, y, c), z, d) ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| Black, a, x, Node (Red, b, y, Node (Red, c, z, d)) ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| a, b, c, d ->
Node (a, b, c, d)

let insert x s =
let rec ins = function
Leaf -> Node (Red, Leaf, x, Leaf)
| Node (color, a, y, b) as s ->
if x < y then balance (color, ins a, y, b)
else if x > y then balance (color, a, y, ins b)
else s
in
match ins s with    (* guaranteed to be non-empty *)
Node (_, a, y, b) -> Node (Black, a, y, b)
| Leaf -> raise (Invalid_argument "insert");;
```

However, there are a couple of silly bits on O'Caml. Firstly, the bitwise (not, logical) AND function is called land. Secondly, the namespace for record fields is flat within a module, so you can't have 2 record/struct types with the same named field in a single module. I'm pretty sure that there isn't a deep reason for that (the shallow reason has to do with type inference).

Dee M Cee A!

From one of Coderman's friends....

```(Sung to the tune of Y.M.C.A by the Village People)

Net geeks
There's no need to feel guilt
I said, net geeks
For the software you built
I said, net geeks
'Cause you're not in the wrong
There's no need to feel unhappy!

Net geeks
You can burn a CD
I said, net geeks
You can play them
Many ways to take them real far!

It's fun to violate
the D M C A !
It's fun to violate
the D M C A-AY !
You have everything
You need to enjoy

It's fun to violate
the D M C A !
It's fun to violate
the D M C A-AY !

You can share over cable
You can annoy the
Record Labels!
```