Re: [Caml-list] Patterns in ML vs OCaml ...

[Brian Hurt <bhurt@spnz.org>]

First off, there's an Ocaml's beginner's list this would be more 
appropriate for:
http://groups.yahoo.com/group/ocaml_beginners/

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
        else
            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
            else
                loop accu t
    in
    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 *)
            true
        else
            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
            true
        else
            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 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners