From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA24640; Tue, 7 Aug 2001 14:23:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA24862 for ; Tue, 7 Aug 2001 14:23:28 +0200 (MET DST) Received: from mail.cs.uu.nl (sunset.cs.uu.nl [131.211.80.32]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f77CNS901136 for ; Tue, 7 Aug 2001 14:23:28 +0200 (MET DST) Received: from silvester.cs.uu.nl (silvester.cs.uu.nl [131.211.80.119]) by mail.cs.uu.nl (Postfix) with SMTP id C08E14535; Tue, 7 Aug 2001 14:23:27 +0200 (MET DST) Received: by silvester.cs.uu.nl (sSMTP sendmail emulation); Tue, 7 Aug 2001 14:23:27 +0200 Date: Tue, 7 Aug 2001 14:23:27 +0200 From: Frank Atanassow To: Costin Stefan Cc: caml-list@inria.fr Subject: Re: [Caml-list] list in functional style Message-ID: <20010807142327.B26097@cs.uu.nl> References: <3B6FB7E3.8FD8903@auctionwatch.ro> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <3B6FB7E3.8FD8903@auctionwatch.ro>; from costins@auctionwatch.ro on Tue, Aug 07, 2001 at 12:41:55PM +0300 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 = # let cons x xs n c = c x (xs n c);; val cons : 'a -> ('b -> ('a -> 'c -> 'd) -> 'c) -> 'b -> ('a -> 'c -> 'd) -> 'd = # let fold n c xs = xs n c;; val fold : 'a -> 'b -> ('a -> 'b -> 'c) -> 'c = # 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 = 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 = 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