Simple trivial O'Caml code

[GnuVince]

let rec butLast mylist =
if List.tl mylist = [] then []
else List.hd mylist :: butLast (List.tl mylist);;


This functions recieves on argument, a list of any type (int list, string list, etc.) and will return the same list without the last element. Small note, the 'rec' word means the function is recursive. Here's how List.tl (tail) and List.hd (head) work:


# List.hd [1;2;3;4];;
- : int = 1
# List.tl [1;2;3;4];;
- : int list = [2; 3; 4]
# List.hd [1];;
- : int = 1
# List.tl [1];;
- : int list = []




Here's a function that will remove all elements 'x' from a list.

let rec remAll e mylist =
if mylist = [] then []
else if List.hd mylist = e then remAll e (List.tl mylist)
else List.hd mylist :: remAll e (List.tl mylist);;


Running it gives us:

# remAll 3 [1;2;3;4;3];;
- : int list = [1; 2; 4]



This function will reverse a string:

let reverse s =
let rec loop old_s new_s old_p new_p =
if old_p = ~-1 then new_s
else begin
new_s.[new_p] <- old_s.[old_p];
loop (old_s) (new_s) (old_p - 1) (new_p + 1)
end
in
loop (s) (String.copy s) ((String.length s) - 1) (0)



This is an example of a nested function (a function inside another function).

[kmj]

sweet.. thanks for the code bits. I've been interested in getting a little look at o'caml.

[GnuVince]

You're welcome kmj. Since jemfinch retired, I guess that makes me the O'Caml guy though I don't know 10% of what he did (but then again his knowledge of programming concepts was much greater than mine)

If you need anything, you can ask me.

[sans-hubris]

O'Caml is pretty self-descriptive. It should be pretty easy to learn and there is a lot of functional programming in it.

GnuVince or anyone that can answer this question, is there a quick tutorial to O'Caml for experienced (functional){0,1} programmers? It seems wasteful to read tutorials meant for the more uninformed when I can clearly glean quite a bit of information about how the language works just by looking at source code, but I would still need a little more information.

[GnuVince]

http://www.cs.caltech.edu/courses/cs134/cs134b/book.pdf
http://caml.inria.fr/ocaml/htmlman/index.html
http://caml.inria.fr/oreilly-book/

[PrBacterio]

Actually its better to use pattern matching when iterating over lists as its more readable; that is the standard way of doing things. Also pattern-matching is the more general cosntruct and getting comfortable with it is one of the most important things to learn when getting into OCaml.

Here is, e.g., a better version of butlast:

let rec butlast = function
[h] -> []
| h :: t -> h :: butlast t
| [] -> raise (Invalid_argument "butlast")


The 'remAll' function is already, as a more generalized version, in the standard library, it is called 'filter'. You would then write remAll using higher-order programming something like

let remall k lst = List.filter (( <> ) k) lst


[edit]
also a note on style: it is uncommon to use identifiers which use capital letters in OCaml; those are usually reserved for constructors and module identifiers. A good rule is to use mixed case for constructors, using underscores to separate words; upper-case only for module types; mixed-case for modules; and lower-case again with underscores to separate words for function and type names.

[GnuVince]

prBacterio, I don't understand how the first one works if you give it no parameters? and what does ( <> ) represent exaclty?

[Dru Lee Parsec]

My guess is that <> means "Not Equals". Or at least that was what <> meant in several old versions of BASIC.

[GnuVince]

Dru: Not sure, in the object model, { <> } is to duplicate an object or something like that

[PrBacterio]

GnuVince:
Ill answer the second question first. As Im sure you all know, operators are just functions of two parameters, which happen to be written IN BETWEEN their arguments instead of in front of them as usual, i.e. you write a <> b instead of <> a b.

Writing an operator inside of a pair of parentheses in OCaml returns that operator as a normal (non - infix) function; i.e., for example, ( + ) 2 3 is equivalent to 2 + 3 and so on.

The <> operator tests for structural inequality. There are different 4 equality operators in OCaml:
== which tests for physical equality;
!= which tests for physicial INequality and is the inverse to ==;
= which tests for structural equality, and
<> which tests for structural INequality and is the inverse to =.


For example,

let a = "foo"
and b = "foo" in
a = b , a == b


might return (true,true) or (true,false), because the two strings, "foo", and "foo", while they are structurally equivalent (i.e. they represent the same object), might actually be represented by two different pointers.

Thats why strings, floats and all other boxed (allocated) objects should be compared with = and <>, instead of with == and !=.

So, ( <> ) is a function of type 'a -> 'a -> bool that returns if its two parameters are (structurally) equal; and (( <> ) k) is a partial application of that function, a function that takes one argument and compares it to k.

On to the first question: The function DOES get parameters. It just uses them in a pattern-matching construct.

Maybe youve already seen THIS syntax:

let rec butlast lst =
match lst with
[h] -> []
| h :: t -> h :: butlast t
| [] -> raise (Invalid_argument "butlast")


pattern-matching is really the central, most powerful feature in the ML types of languages (and many other functional languages like Haskell and Clean) and if you dont already know about it you should really read it up now; otherwise youll never know the real power in those languages :).

Basically what it does is, it matches the given value (the argument) against a "type" or "format" of a value, e.g. the form "a :: b" matches against non-empty lists etc.

The function keyword introduces a new function which is defined by pattern-matching of its (single) argument. Youve already used the most simple form of pattern-matching - simply matching against a catch-all variable - many times in constructs like


let foo bar = bar * bar


which is actually equivalent to

let foo = function bar -> bar * bar


So what the definition of the function 'butlast', as formerly given by me, does is introduce a function by a generalized case-construct (pattern-matching) which uses different expressions for different cases of the arguments.

I think pattern-matching is, once you know the basics, really easier to read than other methods of function-definition: E.g., given the above example, 'butlast', we can clearly see the three distinct cases and their associated expressions:

let rec butlast = function
[h] -> []
| h :: t -> h :: butlast t
| [] -> raise (Invalid_argument "butlast")


This definition reads as:
The function butlast of an argument is
The empty list, when a list with only exactly one item is given as an argument;
The head h of the list, plus the (butlast) of the rest (tail) of the list, butlast t, for any other non-empty list of a head (h) and a tail (t), giving h :: t;
an error, if the empty list is given to it.

[Strike]

This is the ordered insert function I came up with. It takes an argument, and puts it into a sorted list in the right place:

# let rec insert i i_list = match i_list with
[] -> [i]
| h::t when i > h -> if i < (List.hd t) then h::(i::t)
else h::(List.hd t)::(insert i (List.tl t))
| _ -> i::i_list;;
val insert : 'a -> 'a list -> 'a list = <fun>

Here's some action:

# insert 'a' ['a'; 'b'; 'c'];;
- : char list = ['a'; 'a'; 'b'; 'c']
# insert 2.0 [1.0; 2.0; 3.0; 4.0];;
- : float list = [1; 2; 2; 3; 4]
# insert 100 [];;
- : int list = [100]
# insert 1 [2; 3; 4; 5];;
- : int list = [1; 2; 3; 4; 5]
# insert [] [[]; []];;
- : '_a list list = [[]; []; []]
# insert [1] [[2]; [3]];;
- : int list list = [[1]; [2]; [3]]
# insert [4] [[2]; [3]];;
- : int list list = [[2]; [3]; [4]]

[Strike]

Couple this with List.fold_right and you have a sorted list merger:

# let merge_i list1 list2 =
List.fold_right insert list1 list2;;
val merge_i : 'a list -> 'a list -> 'a list = <fun>
# merge_i [1; 4; 9; 16] [5; 10; 15; 20];;
- : int list = [1; 4; 5; 9; 10; 15; 16; 20]