CODEWITHSUNDEEP
functional-programmingocamllazy-evaluation
Jackson Tale
Jackson Tale

Reputation: 25812

The execution of lazy evaluation (OCaml)

I am trying to under the execution of lazy evaluation.

I created a lazy list type and according map function.

type 'a zlist = 'a node_t lazy_t
and 'a node_t = Empty | Node of 'a * 'a zlist

let rec zlist_of_list l = lazy (
  match l with
    | [] -> Empty
    | hd::tl -> Printf.printf "transforming %d\n" hd;Node (hd, zlist_of_list tl)
)

let rec list_of_zlist zl = 
  match Lazy.force zl with
    | Empty -> []
    | Node (hd, tl) -> hd::(list_of_zlist tl)

let rec map_z f zl = lazy (
  match Lazy.force zl with
    | Empty -> Empty
    | Node (hd, tl) -> Node (f hd, map_z f tl)
)

First question:

From my understanding, lazy just encapsulate things inside () behind without immediate execution.

So for function zlist_of_list, the whole 

match l with
  | [] -> Empty
  | hd::tl -> Node (hd, zlist_of_list tl)

Will be delayed, not a single bit is executed when zlist_of_list is applied, so does map_z.

Am I right?

Below, I try to do double lazy map 

let f1 x = Printf.printf "%d\n" x; x

let f2 x = Printf.printf " %d\n" (-x); (-x)

let zl = zlist_of_list [1;2;3]

let zl_m2 = map_z f2 (map_z f1 zl)

let _ = list_of_zlist zl_m2

The outcome is

transforming 1
1
 -1
transforming 2
2
 -2
transforming 3
3
 -3

The I don't understand. It seems the execution is by column, not by row. I thought it should be

  1. Every element is transformed first
  2. Then f1 is mapped to every element
  3. The f2 is mapped to every element

Second question:

Why via lazy, the execution order becomes like that?

Upvotes: 1

Views: 1194

Answers (1)

gsg
gsg

Reputation: 9377

To your first question: that's right, map_z will return a thunk that calculates the next part of the list, not the list itself. In particular, the recursive call within the definition of map_z will not descend into the rest of the list until it is forced - you can take one transformed element from the result of a map_z without calculating the rest.

This is also the answer to your second question: the reason you see one element being transformed, then passed to f1, then f2 is that at each step you are taking one element from a lazy list and the others remain suspended.

And that's the whole point of lazy lists! Doing things that way is useful because it provides a fairly natural way to program with infinite (or very large) lists. If an entire list had to be calculated first before using the elements, it would not really be a lazy data structure.

Upvotes: 5

Related Questions