Re: [Caml-list] list in functional style

[Frank Atanassow <franka@cs.uu.nl>]

Costin Stefan wrote (on 07-08-01 12:41 +0300):
> Excuse my ignorance,
> 
> I have the following problem : want to define lists but using only
> functions :
> But the type inference make problems, and I don't get it.
> Here is the code :
> 
> let cons x l=fun a-> a x l;;
> let hd l=
>     let _hd=fun x _->x
>     in l _hd;;
> 
> let tl l=
>     let _tl=fun _ l->l
>     in l _tl;;

I guess you want to define lists using the Church encoding. What you are
defining above is more like a non-empty list, since otherwise hd and tl are
partial. For possibly-empty lists, the correct deconstructor is Ocaml's
fold_right.

> This type inference mess up all the construction :-(
> It infers that the type of hd may be the same as the type of tl.
> But this works only for this example. A usual list is like :
> # let l=cons 1 (cons 2 3);;

You have two differently-typed values in the second argument of cons: int and
"list". I don't believe that can be made to work in Ocaml's type system.

Anyway, here is the usual Church encoding of possibly-empty lists. I suspect
this is what you wanted in the first place:

# let nil n c = n;;
val nil : 'a -> 'b -> 'a = <fun>
# let cons x xs n c = c x (xs n c);;  
val cons :
  'a -> ('b -> ('a -> 'c -> 'd) -> 'c) -> 'b -> ('a -> 'c -> 'd) -> 'd =
  <fun>
# let fold n c xs = xs n c;;
val fold : 'a -> 'b -> ('a -> 'b -> 'c) -> 'c = <fun>
# fold 0 (+) (cons 1 (cons 2 (cons 3 nil)));;
- : int = 6

Note that the type of a list over elements of type 'a is:

  'b -> ('a -> 'b -> 'b) -> 'b

The first argument is the nil, and the second is the cons; 'b is the fold's
result type.

Unfortunately, a bare list like this:

# cons 1 (cons 2 nil);;
- : '_a -> (int -> '_a -> '_a) -> '_a = <fun>

still yields ungeneralized type variables, which means you will only ever be
able to fold it into one result type. So you need to eta-epand:

# fun n c -> (cons 1 (cons 2 (cons 3 nil))) n c;;
- : 'a -> (int -> 'a -> 'a) -> 'a = <fun>

which is admittedly annoying.

-- 
Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr