CODEWITHSUNDEEP
streamocamllazy-evaluation
Nick Heiner
Nick Heiner

Reputation: 122450

Ocaml: Lazy Lists

How can I make a lazy list representing a sequence of doubling numbers? Example:

1 2 4 8 16 32

Upvotes: 9

Views: 7144

Answers (4)

Chris
Chris

Reputation: 36581

Answer from the distant future...

OCaml 4.07 introduced the Seq module which can facilitate this.

# let rec lazy_list start f () =
    Seq.Cons (start, lazy_list (f start) f);;
val lazy_list : 'a -> ('a -> 'a) -> 'a Seq.t = <fun>
# lazy_list 1 @@ ( * ) 2
  |> Seq.take 5 
  |> List.of_seq;;
- : int list = [1; 2; 4; 8; 16]

Upvotes: 1

james woodyatt
james woodyatt

Reputation: 2196

Also, there is a lazy list module called Cf_seq in my OCaml Network Application Environment Core Foundation. In fact, I wrote a whole passle of functional data structures. It's all available under a 2-clause BSD license. Enjoy.

Update: the code has been renamed "Oni" and it's now hosted at BitBucket. You can also use the GODI package for it.

Upvotes: 3

jdb
jdb

Reputation: 562

If you want to do it by hand, I'd say you have to main options:

  • Use a custom lazy_list type, like ephemient said (except his solution is a bit broken):

    type 'a lazy_list =
    | Nil
    | Cons of 'a * 'a lazy_list

let head = function
    | Nil -> failwith "Cannot extract head of empty list"
    | Cons (h, _) -> h

let tail = function
    | Nil -> failwith "Cannot extract tail of empty list"
    | Cons (_, t) -> t

  • Use a kind of thunk (like the thing used to implement lazy evaluation in a language that does not support it). You define your list as a function unit -> 'a that says how to get the next element from the current one (no need to use streams for that). For example, to define the list of all natural integers, you can do

    let make_lazy_list initial next =
    let lazy_list current () =
        let result = !current in
        current := (next !current); result
    in lazy_list (ref initial)

let naturals = make_lazy_list 0 (function i -> i + 1)

    The if you do

    print_int (naturals ());
print_int (naturals ());
print_int (naturals ())

    you will get the following output:

    0
1
2

Upvotes: 2

ephemient
ephemient

Reputation: 204768

Using streams:

let f x = Stream.from (fun n -> Some (x * int_of_float (2.0 ** float_of_int n)))

or

let f x =
  let next = ref x in
    Stream.from (fun _ -> let y = !next in next := 2 * y ; Some y)

Using a custom lazy_list type:

type 'a lazy_list =
  | Nil
  | Cons of 'a * 'a lazy_list lazy_t
let rec f x = lazy (Cons (x, f (2*x)))

Upvotes: 13

Related Questions