[Caml-list] fib with lazy list

[Caml-list] fib with lazy list

[SooHyoung Oh]

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 ------------------
---
SooHyoung Oh

-------------------
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

Re: [Caml-list] fib with lazy list

[sebastien FURIC]

 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

Re: [Caml-list] fib with lazy list

[sebastien FURIC]

 Sorry, a typo:

sebastien FURIC a écrit :
> 
>  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
    ^^^^^^^^^^^^^^^^^^^^^
    | LList (_, lxs) -> Lazy.force lxs

 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

Re: [Caml-list] fib with lazy list

[Michel Quercia]

Le Wed, 23 Apr 2003 19:53:28 +0900 "SooHyoung Oh" <shoh@duonix.com>
écrivit:

> 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?
> 
> 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 rec x = ... x ... is allowed only when the right hand side is a functionnal value or "x is inside an argument of some constructor in the rhs". The following code should work (the constructor here is LzCons) :

let rec fib_list = LzCons(1, lazy(map fib (from 1)))
and fib n =
    match n with
    | n when n < 0 -> failwith "invalid argument"
    | 0 -> 1
    | 1 -> 1
    | _ -> nth fib_list (n-1) + nth fib_list (n-2)
;;

-- 
Michel Quercia
23 rue de Montchapet, 21000 Dijon
http://michel.quercia.free.fr (maths)
http://pauillac.inria.fr/~quercia (informatique)
mailto:michel.quercia@prepas.org

-------------------
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