O'Caml Lesson #1

[wtd]

O'Caml Lesson #1

Recursive nature of lists

In programming we almost incessantly deal with sequences of things. It is therefore critical that we understand how such things work.

What is a list?

Rather let's ask a simpler question. What's the simplest possible list?

Well that's easy. It's nothing. The simplest list is one that contains nothing.

If you got that, then what's the next simplest list? It's clearly a list with only one element.

How are these two lists related? Well, just as one is clearly just zero plus one, a list with one element is just an empty list plus some element. And an empty list and a list with one element are both lists, so we can simplify that statement.

"A list can be a list plus some element."

We can combine that with our previous statement about an empty list.

A list can be nothing. A list can be a list plus some element.

The first sentence is very simple. The second however is recursive. If a list contains a list then where does it stop? That's where the first sentence comes back into play. It provides a definition for a list that doesn't contain another list.

Demonstrating this with code

In O'Caml we represent the empty list as:

code:

[]

We represent the act of adding some element onto a list as:

code:

value :: list

Thus the list with one element appears as:

code:

value :: []

And since that is a list, we can represent a list with two elements as:

code:

value2 :: value1 :: []

Of syntactic sugar

Fortunately O'Caml offers a quicker way of representing lists in syntax.

code:

[value2; value1]

But it's important to realize that this is simply syntactic sugar, and the two forms are exactly identical. We can mix them if we wish.

code:

value3 :: [value2; value1]

The @ operator concatenates two lists.

The following examples are exactly identical.

code:

[1; 2; 3; 4]

code:

[1; 2] @ [3; 4]

Lists meet pattern matching

The recursive nature of lists is directly expressed by pattern matching on lists. Let's construct a recursive function to find the length of a list.

code:

let rec length input_list =    match input_list with    | [] -> 0    | x::xs -> 1 + length xs

The first pattern is the empty list. In this case, if a list is empty, then its length is zero.

The second pattern is some value x, tacked onto some list xs (intented to be the plural of "x").

Exercise

Define a generic my_list type such that the following conversion of the previously demonstrated length function works.

code:

let rec length input_list =    match input_list with    | Empty -> 0    | Node (x, xs) -> 1 + length xs

[rizzix]

for those who don't know the correct term for what wtd is describing is the "cons" operator. In the case of O'Caml it seems to be ::. I the case of haskell it is :.

[wtd]

As is it is in SML.

O'Caml/SML:

code:

1 :: 2 :: 3 :: []

Haskell:

code:

1 : 2 : 3 : []

Lisp

code:

(cons 1 (cons 2 (cons 3 '())))

[MysticVegeta]

How to add elements to a list using loops?

[rizzix]

#1] These cons-lists are not the same as the list and arrays you know. They behave differently.

#2] Tail recursion is highly optimised by these functional programming compilers, hence there's no need for loops. I don't know about o'caml but loop-constructs are not present in Haskell (although you can gain similar functionality using the <- operator on lists in a do-block), but almost always, looping is handled through recursion.

[wtd]

rizzix wrote:

#2] Tail recursion is highly optimised by these functional programming compilers, hence there's no need for loops. I don't know about o'caml but loop-constructs are not present in Haskell (although you can gain similar functionality using the <- operator on lists in a do-block), but almost always, looping is handled through recursion.

Loops are present in O'Caml, but as lists are immutable, using a loop would be overly cumbersome.

code:

let foo = [23; 54; 12] let bar =    let bar' = ref [] in       for i = 0 to List.length foo - 1 do          bar' := !bar' @ [List.nth foo i * 2]       done;       !bar';; for i = 0 to List.length bar - 1 do    Printf.printf "%d\n" (List.nth bar i) done

vs.

code:

let foo = [23; 54; 12] let bar = List.map (fun x -> x * 2) foo;; List.iter (Printf.printf "%d\n") bar

And if we wish to say this is cheating since I've used the standard libray, then I'll demonstrate the creation of simple map and iter functions.

code:

let rec map f lst =    match lst with    | [] -> []    | x::xs -> f x :: map f xs let rec iter f lst =    match lst with    | [] -> ()    | x::xs -> f x; iter f xs

Still doesn't look nearly as bad as using loops, does it?

And yet, the principles in many ways remain the same.

In iter, for instance, I have an initial condition when I call the function. The list starts out as 23, 54, and 12. I have an exit condition. When the list is empty, then we're done. And I have an update. I call the fucntion again, but this time with the list minus its first element.

The body of the loop is just the application of the first element in the list to the function I passed in as an argument.

[MysticVegeta]

wow thats so simplified and easier than loops! Damn I should start learning OCaml .. instead of java...

[wtd]

[MysticVegeta]

Any particular website you would recommend for a COMPLETE noobie to O'Caml?

[Cervantes]

CompSci.ca
and
#compsci.ca

[wtd]

http://caml.inria.fr

[rizzix]

MysticVegeta wrote:

instead of java...

You just had to add that part didn't you?

I'll give you this early warning: learn java as well, or you _will_ be lost (in the not-so-distant future). Java is far too popular and is a main-stream programming language. You have to learn it whether you like it or not. It's the same with C/C++.

[rizzix]

loops in haskell...

Haskell:

square_list xs = do     x <- xs     return (x*x)

GHCi:

*Main> square_list [1 .. 5] [1,4,9,16,25] *Main> _

lol so where's the loop

[wtd]

rizzix wrote:

loops in haskell...

Haskell:

square_list xs = do     x <- xs     return (x*x)

GHCi:

*Main> square_list [1 .. 5] [1,4,9,16,25] *Main> _

lol so where's the loop

code:

squareList = map (^ 2)

No pesky monads to describe in my version. And no senseless eta expansion.

[MysticVegeta]

rizzix wrote:

MysticVegeta wrote:

instead of java...

You just had to add that part didn't you?

I'll give you this early warning: learn java as well, or you _will_ be lost (in the not-so-distant future). Java is far too popular and is a main-stream programming language. You have to learn it whether you like it or not. It's the same with C/C++.

Hmm, I didnt really meant that lol. I "have" to do Java too cause TC doesnt support O'Caml