Re: [Caml-list] fib with lazy list

["sebastien FURIC" <sebastien.furic@tni-valiosys.com>]

 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, <lazy>)
# 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