[Camllist] list in functional style

Costin Stefan
 Frank Atanassow
 Frank Atanassow
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Frank Atanassow <franka@c...> 
Subject:  Re: [Camllist] list in functional style 
Costin Stefan wrote (on 070801 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 nonempty list, since otherwise hd and tl are partial. For possiblyempty 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 differentlytyped 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 possiblyempty 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 etaepand: # 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) 2533261 Fax +31 (030) 251379  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr