[Caml-list] list in functional style

[Costin Stefan <costins@auctionwatch.ro>]

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