Lazy lists

Here is the type of polymorphic lazy lists:

type 'a lazy_list =
  | Lnil
  | Lcons of 'a * 'a lazy_list Lazy.t;;

Analysis:

• Lnil is a zero-ary constructor that represents the empty lazy list; and

• Lcons is a binary constructor that, given

  • a value v and
  • a suspension that, when forced, yields a lazy list,

  constructs a lazy list that starts with v and whose tail is represented by the suspension and thus not computed yet.

For example, Lnil has a polymorphic type:

# Lnil;;
- : 'a lazy_list = Lnil
#

And nonempty lazy lists, e.g., of integers, are constructed with Lcons:

# Lcons (0, lazy Lnil);;
- : int lazy_list = Lcons (0, lazy Lnil)
# Lcons (1, lazy (Lcons (0, lazy Lnil)));;
- : int lazy_list = Lcons (1, <lazy>)
#

Ditto for nonempty lazy lists, e.g., of Booleans:

# Lcons (true, lazy Lnil);;
- : bool lazy_list = Lcons (true, lazy Lnil)
# Lcons (false, lazy (Lcons (true, lazy Lnil)));;
- : bool lazy_list = Lcons (false, <lazy>)
#

Exercise 03

So int lazy_list is the type of lazy lists of integers and bool lazy_list is the type of lazy lists of Booleans.

1. What is the type of lazy lists of strings? Exhibit a simple OCaml expression with that type.
2. What is the type of lazy lists of pairs of integers and Booleans? Exhibit a simple OCaml expression with that type.
3. What is the type of lazy lists of lists of integers? Exhibit a simple OCaml expression with that type.
4. What is the type of lists of lazy lists of integers? Exhibit a simple OCaml expression with that type.
5. What is the type of lazy lists of lazy lists of integers? Exhibit a simple OCaml expression with that type.
6. What is the type of lazy lists of functions that map integers to integers? Exhibit a simple OCaml expression with that type.
7. What is the type of lazy lists of functions that map strings to integers? Exhibit a simple OCaml expression with that type.
8. What is the type of lazy lists of polymorphic values? Exhibit a simple OCaml expression with that type.
9. What is the type of lazy lists of lazy lists of polymorphic values? Exhibit a simple OCaml expression with that type.
10. What is the type of lazy lists of lists of polymorphic values? Exhibit a simple OCaml expression with that type.
11. What is the type of lists of lazy lists of polymorphic values? Exhibit a simple OCaml expression with that type.

Version

Created [27 Oct 2022]