CODEWITHSUNDEEP
ocamllazy-evaluation
Jackson Tale
Jackson Tale

Reputation: 25812

The difference between these two lazy type definition?

type 'a list_t =
    | Empty
    | Node of 'a * 'a list_t lazy_t


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

I don't see many differences.

The only thing I can identify is that in the 2nd type, even the Empty is put to a lazy thunk, am I right? If I am right, then what is the purpose of put Empty to thunk?

Any other differences?

Edit

I am asking the differences between the two types of list: list_t and zlist_t.

Upvotes: 2

Views: 119

Answers (3)

newacct
newacct

Reputation: 122449

There is absolutely no difference between 'a node_t and 'a list_t, since you can substitute the definition of the alias 'a zlist_t into the definition of 'a node_t and what you get is exactly analogous to 'a list_t.

You said you are asking about the difference between 'a list_t and 'a zlist_t. Well, 'a zlist_t is just a type alias for 'a node_t lazy_t. As we noted above that node_t and list_t are equivalent, that means 'a zlist_t, i.e. 'a node_t lazy_t, is equivalent to 'a list_t lazy_t. So your question is basically asking what is the difference between 'a list_t and 'a list_t lazy_t.

Well, from looking at it, the difference is simple -- one is the other wrapped in a lazy_t, which means it's the lazy version of the other. If you have a value of type 'a list_t, it means that the first cons cell is already evaluated, since it's value must either be Empty or Node, without evaluating lazy expressions. Further, if it is Node, the first item must also be evaluated, since it lives inside the Node without a lazy_t. On the other hand, if you have a value of type 'a list_t lazy_t, it means the first cons cell may not be evaluated; you don't get an 'a list_t until you force it.

Upvotes: 1

Jonathan Protzenko
Jonathan Protzenko

Reputation: 1739

The problem with the first one, I think, is that Node (foo, lazy Empty) cannot be wrapped in a Lazy.t to make the evaluation of foo itself lazy.

Let me explain a little bit more with two examples :

# type 'a list_t = Empty | Node of 'a * 'a list_t lazy_t;;
type 'a list_t = Empty | Node of 'a * 'a list_t lazy_t
# Node ((print_endline "hello"; 1), lazy Empty);;
hello
- : int list_t = Node (1, lazy Empty)

Here, the evaluation of the 'a element has been performed before I could build the list. In other words, the first type definition you wrote is a definition for lists whose head element has always been evaluated. Conversely, the second definition does not force you to evaluate the head of the list in order to build it.

# type 'a node_t = Empty | Node of 'a * 'a zlist_t and 'a zlist_t = 'a node_t lazy_t;;
type 'a node_t = Empty | Node of 'a * 'a zlist_t
and 'a zlist_t = 'a node_t lazy_t
# let x = ((lazy (Node ((print_endline "hello"; 1), lazy Empty))): int zlist_t);;
val x : int zlist_t = <lazy>

The evaluation of the element of type 'a contained in the head of the list takes place when you first force the list, for instance as follows:

# match Lazy.force x with Empty -> () | Node _ -> ();;
hello
- : unit = ()

Upvotes: 3

Martin Jambon
Martin Jambon

Reputation: 4929

There's no difference. 'a zlist_t is an alias for 'a node_t lazy_t. After performing the substitution, we end up with:

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

What you could do is:

type 'a node_t =
    | Empty
    | Node of ('a * 'a node_t) lazy_t

Perhaps better written as:

type 'a node =
    | Empty
    | Node of 'a zlist

and 'a zlist = ('a * 'a node) lazy_t

Note that since OCaml 3.08 or so we can force the evaluation of lazy expressions during pattern-matching like this:

match l with
| Empty -> ...
| Node (lazy (..., ...)) ->

Don't use this definition. It's better to have the list completely lazy like in your definitions. Independently you can always make the elements of the list lazy if you wish.

Upvotes: 0

Related Questions