----------------------------------- wtd Mon Mar 06, 2006 10:49 pm O'Caml Lesson #1 ----------------------------------- 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: [] We represent the act of adding some element onto a list as: value :: list Thus the list with one element appears as: value :: [] And since that is a list, we can represent a list with two elements as: value2 :: value1 :: [] Of syntactic sugar Fortunately O'Caml offers a quicker way of representing lists in syntax. [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. value3 :: [value2; value1] The @ operator concatenates two lists. The following examples are exactly identical. [1; 2; 3; 4] [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. 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. let rec length input_list = match input_list with | Empty -> 0 | Node (x, xs) -> 1 + length xs ----------------------------------- rizzix Tue Mar 07, 2006 3:16 am ----------------------------------- 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 Tue Mar 07, 2006 3:47 am ----------------------------------- As is it is in SML. O'Caml/SML: 1 :: 2 :: 3 :: [] Haskell: 1 : 2 : 3 : [] Lisp (cons 1 (cons 2 (cons 3 '()))) ----------------------------------- MysticVegeta Mon Mar 13, 2006 2:34 pm ----------------------------------- How to add elements to a list using loops? ----------------------------------- rizzix Mon Mar 13, 2006 3:19 pm ----------------------------------- #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 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. 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 Mon Mar 13, 2006 6:30 pm ----------------------------------- wow thats so simplified and easier than loops! Damn I should start learning OCaml .. instead of java... ----------------------------------- wtd Mon Mar 13, 2006 6:46 pm ----------------------------------- :) ----------------------------------- MysticVegeta Mon Mar 13, 2006 7:25 pm ----------------------------------- Any particular website you would recommend for a COMPLETE noobie to O'Caml? ----------------------------------- Cervantes Mon Mar 13, 2006 8:25 pm ----------------------------------- [url=www.compsci.ca]CompSci.ca and [url=http://www.compsci.ca/wiki/index.php?title=IRC_channel]#compsci.ca :) ----------------------------------- wtd Mon Mar 13, 2006 10:25 pm ----------------------------------- http://caml.inria.fr ----------------------------------- rizzix Tue Mar 14, 2006 12:18 am ----------------------------------- instead of java... :disgusted: 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 Tue Mar 14, 2006 12:44 am ----------------------------------- loops in haskell... square_list xs = do x square_list lol so where's the loop ;) ----------------------------------- wtd Tue Mar 14, 2006 1:49 am ----------------------------------- loops in haskell... square_list xs = do x square_list lol so where's the loop ;) squareList = map (^ 2) ;) No pesky monads to describe in my version. And no senseless eta expansion. ----------------------------------- MysticVegeta Tue Mar 14, 2006 6:18 pm ----------------------------------- instead of java... :disgusted: 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