Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Patterns in ML vs OCaml ...
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-10-24 (18:32)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] Patterns in ML vs OCaml ...

First off, there's an Ocaml's beginner's list this would be more 
appropriate for:

On Sun, 24 Oct 2004, Vasili Galchin wrote:

> Hello,
>     I'm sorry this is a very elementary question (but I am pulling my hair out). With a function written in ML:
> fun filter_list P []       = [] |
>     filter_list P (h :: t) = let val ft = filter_list P t
>                              in if P h then (h :: ft)
>                                 else ft
>                              end;

A literal translation of this function into Ocaml would be:

let rec filter_list p = function
    | [] -> []
    | h :: t ->
        let ft = filter_list p t in
        if p h then
            h :: ft

Of course, the problem with this function is that it's not tail recursive.  
For sufficiently long lists (say, more than few tens of thousands of 
elements) you'll blow the stack.  A better implementation would be:

let filter_list p =
    let rec loop accu = function
        | [] -> List.rev accu
        | h :: t ->
            if p h then
                loop (h :: accu) t
                loop accu t
    loop []

Also note that this function already exists in the standard library with 
the name List.filter.  If this is the actual function you need, use the 
standard library version instead.

> fun member (e, nil) = false |
>     member (e , (h :: t)) = if (e=h) then true
>                                      else member (e, t) ;

The literal translation of this function would be:

let rec member = function
    | (e, []) -> false
    | (e, (h :: t)) ->
        if e = h then (* note: structural comparison *)
            member (e, h)

The problem with this function is that every call requires the allocation 
of a new tuple.  A better implementation is probably:

let rec member e = function
    | [] -> false
    | h :: t ->
        if e = h then
            member e t

Once again, this function exists in the standard library, with the name 
List.mem (A variant, which uses referential equality instead of structural 
equality, also exists with the name List.memq).

"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: