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 OAA01936; Wed, 23 Apr 2003 14:14:25 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA01424 for ; Wed, 23 Apr 2003 14:14:24 +0200 (MET DST) Received: from mailhost.tni.fr (firewall.tni.fr [195.25.255.61]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h3NCENH02368 for ; Wed, 23 Apr 2003 14:14:23 +0200 (MET DST) Received: from groscool.tni.fr ([195.25.255.1]) by mailhost.tni.fr (Netscape Messaging Server 3.62) with SMTP id 703; Wed, 23 Apr 2003 14:14:05 +0200 Received: from 192.168.7.60 by groscool.tni.fr (InterScan E-Mail VirusWall NT); Wed, 23 Apr 2003 14:14:05 +0200 (Paris, Madrid (heure d'été)) Message-ID: <3EA6827C.64D3D22@tni.fr> Date: Wed, 23 Apr 2003 14:09:32 +0200 From: "sebastien FURIC" X-Mailer: Mozilla 4.78 [fr] (Windows NT 5.0; U) X-Accept-Language: fr MIME-Version: 1.0 To: SooHyoung Oh CC: OCaml Mailing list Subject: Re: [Caml-list] fib with lazy list References: <003901c30986$92677ff0$fe00a8c0@hama> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; furic:01 tni-valiosys:01 caml-list:01 rec':01 lls:99 failwith:01 3.06:01 val:01 htmlman:01 ecrit:01 ocaml:01 caml:01 int:01 rec:01 lazy:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hi, SooHyoung Oh a écrit : > > I'm trying to implement "fib" function with lazy list. > I met the error with message: > File "eg1.ml", line 19, characters 19-35: > This kind of expression is not allowed as right-hand side of `let rec' > > Can anyone solve this problem? > > ------- source begin --------- > type 'a lzlist = LzCons of 'a * 'a lzlist Lazy.t;; > let rec forever n = LzCons (n, lazy (forever n));; > let rec lzlist f n = LzCons (n, lazy (lzlist f (f n)));; > let hd (LzCons (n, l)) = n;; > let tl (LzCons (n, l)) = Lazy.force l;; > let from n = > let add1 m = m + 1 in > lzlist add1 n > ;; > let rec map f lls = > LzCons (f (hd lls), lazy (map f (tl lls))) > ;; > let rec nth lls n = > match n with > | 0 -> hd lls > | n -> nth (tl lls) (n-1) > ;; > > let rec fib_list = map fib (from 0) (* ERROR *) > and fib n = > match n with > | 1 -> 1 > | n -> nth fib_list (n-1) + nth fib_list (n-2) > ;; > > let main = fib 5;; > -------------- end of source ------------------ This error is due to a restriction in the "let rec" construct (see http://caml.inria.fr/ocaml/htmlman/manual015.html#s:localdef). The following code solves your problem: type 'a llist = LList of 'a * 'a llist Lazy.t | Empty let tl = function | Empty -> failwith "tl: empty list" | LList (_, xs) -> xs let rec map2 f xs xs' = match xs, xs' with | Empty, Empty -> Empty | LList (x, lxs), LList (x', lxs') -> LList (f x x', lazy (map2 f (Lazy.force lxs) (Lazy.force lxs'))) | Empty, LList _ | LList _, Empty -> invalid_arg "map2" let rec nth xs n = match xs, n with | Empty, _ -> failwith "nth" | LList (x, _), 0 -> x | LList (_, lxs), _ -> nth (Lazy.force lxs) (n - 1) Objective Caml version 3.06 # let rec fib = LList (1, lazy (LList (1, lazy (map2 ( + ) fib (tl fib)))));; val fib : int llist = LList (1, ) # nth fib 0;; - : int = 1 # nth fib 1;; - : int = 1 # nth fib 2;; - : int = 2 # nth fib 10;; - : int = 89 # Short explanation: fib = 1, 1, 2, 3, 5, 8, ... tl fib = 1, 2, 3, 5, 8, ... map2 ( + ) fib (tl fib) = 2, 3, 5, 8, ... Cheers, Sebastien. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners