[Caml-list] list in functional style

[Caml-list] list in functional style

[Costin Stefan]

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;;

Load into the toplevel system give the followings signatures :

val cons : 'a -> 'b -> ('a -> 'b -> 'c) -> 'c = <fun>
val hd : (('a -> 'b -> 'a) -> 'c) -> 'c = <fun>
val tl : (('a -> 'b -> 'b) -> 'c) -> 'c = <fun>

Now :

# let l=cons 1 2;;
val l : (int -> int -> '_a) -> '_a = <fun>
# hd l;;
- : int = 1
# tl l;;
- : int = 2
# l;;
- : (int -> int -> int) -> int = <fun>

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);;
val l : (int -> ((int -> int -> '_a) -> '_a) -> '_b) -> '_b = <fun>
# hd l;;
- : int = 1
Now l has the following type :

# l;;
- : (int -> ((int -> int -> '_a) -> '_a) -> int) -> int = <fun>

So the tl will miserably fail  :

# tl l;;
This expression has type (int -> ((int -> int -> 'a) -> 'a) -> int) ->
int
but is here used with type
  (int -> ((int -> int -> 'a) -> 'a) -> (int -> int -> 'a) -> 'a) -> 'b

So why the type of the result of hd may be the same of the type of the
result of tl !

Why the type of the result of a cons isn't a polymorphic function ?

Any suggestion ?


-------------------
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

Re: [Caml-list] list in functional style

[Frank Atanassow]

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

Re: [Caml-list] list in functional style

[Frank Atanassow]

Costin Stefan wrote (on 07-08-01 12:41 +0300):
> I have the following problem : want to define lists but using only
> functions :

Sorry, I was not reading very carefully and now recognize that my post was a
complete non-answer.

> So why the type of the result of hd may be the same of the type of the
> result of tl !
> 
> Why the type of the result of a cons isn't a polymorphic function ?

Type variables of the form '_a are not generalized; they can be instantiated
only once. This is a conservative criterion to ML-like languages use to handle
the interaction between polymorphism and imperative side-effects.

You can read about it in the FAQ:

  http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#variables_de_types_faibles

-- 
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