Module `Zlist.Lazy_list`Source

Lazily-realized lists.

A lazy structure allows arbitrary transformations to be executed without forcing each intermediate representation in memory. When the final result is desired, it can be transformed into a strict structure.

One interesting property of lazy lists is that infinite structures can be constructed without being evaluated.

This implementation is heavily inspired by "Functional Programming in Scala", by Chiusano and Bjarnason (2014).

Some examples

Each of these examples assumes that

  open Zlist
  open Lazy_list

has been executed.

Generate an infinite sequence of even numbers and sample 10 of them:

  let evens = enum_from 0 |> map (fun x -> 2 * x) in
  evens |> take 4 ;;

  - : int list = [0; 2; 4; 6]

Compute an infinite list of Fibonacci numbers and sample 8 of them:

  let fibs = iterate (0, 1) (fun (a, b) -> b, a + b) |> map snd in
  fibs |> take 8 |> to_list ;;

  - : int list = [1; 1; 2; 3; 5; 8; 13; 21]

A quicksort-like algorithm:

  let ( !! ) = Lazy.force ;;
  let ( ++ ) = concat ;;

  let rec sort = function
    | Nil -> Nil
    | Cons (p, lxs) -> begin
        let smaller = filter ((<) p) !!lxs in
        let greater = filter ((>=) p) !!lxs in
        sort smaller ++ unit p ++ sort greater
      end
  in
  sort (of_list [10; 2; 8; 5; 1; 0; 20; 3]) |> to_list ;;

  - : int list = [20; 10; 8; 5; 3; 2; 1; 0]

Representation

Sourcetype 'a t =

| Nil
| Cons of 'a Lazy.t * 'a t Lazy.t

Construction

Sourceval of_list : 'a list -> 'a t

Sourceval of_array : 'a array -> 'a t

Sourceval unit : 'a -> 'a t

unit a constructs a lazy list consisting only of the item a.

Generation

These functions are used to generate lazy lists from specifications.

Sourceval fill : int -> 'a -> 'a t

fill n a generates a lazy list consisting of n instances of the item a.

Sourceval unfold : 's -> ('s -> ('s * 'b) option) -> 'b t

State-based generation.

Starting with an initial state, generate a new state and a value. Termination is indicated by an outcome of None.

Sourceval iterate : 'a -> ('a -> 'a) -> 'a t

Generate an infinite lazy list by repeatedly iterating on a value.

Sourceval continually : 'a -> 'a t

continually a generates an infinite lazy list consisting of the item a.

Sourceval enum_from : int -> int t

enum_from z generates an infinite lazy list consisting of the integers beginning at z and incremented by one at each step.

Sourceval enum_from_to : int -> int -> int t

Like enum_from, but the result is a finite lazy list that terminates at the upper bound.

Sourceval cycle : 'a t -> 'a t

Generate an infinite lazy list consisting of cycles of the argument.

Manipulation

Sourceval head : 'a t -> 'a option

The first item in a lazy list, or None if the list is empty.

Sourceval tail : 'a t -> 'a t

Everything but the first item in a lazy list. This is the dual of head.

In the case of an empty lazy list, the result is Nil.

Sourceval take : int -> 'a t -> 'a t

take n t is a lazy list consisting of the first n items in t.

Sourceval take_while : ('a -> bool) -> 'a t -> 'a t

take_while f t is a lazy list consisting of the first items of t that satisfy the predicate f. The first item in t that does not satisfy the predicate terminates the sequence.

Sourceval drop : int -> 'a t -> 'a t

drop n t is the lazy list t without its first n items.

Sourceval drop_while : ('a -> bool) -> 'a t -> 'a t

drop_while f t is the lazy list t without the first items that satisfy the predicate f. The first item in t that does not satisfy the predicate terminates the sequence.

Sourceval map : ('a -> 'b) -> 'a t -> 'b t

map f t is the lazy list t with the f applied to each of its items.

Sourceval flat_map : ('a -> 'b t) -> 'a t -> 'b t

flat_map f t is equivalent to map f t |> flatten.

Sourceval filter : ('a -> bool) -> 'a t -> 'a t

filter f t is the lazy list t with only the items that satisfy the predicate f.

Sourceval map_filter : ('a -> 'b option) -> 'a t -> 'b t

map_filter f t applies f to each element in t and produces a new lazy list consisting of the non-None values.

Sourceval flatten : 'a t t -> 'a t

Flatten a lazy list of lazy lists.

Querying

Sourceval exists : ('a -> bool) -> 'a t -> bool

Check for the existence of an item in the lazy list that satisfies a predicate.

The first item to satisfy the predicate terminates the realization of the list.

Sourceval for_all : ('a -> bool) -> 'a t -> bool

Check that all items in the lazy list satisfy the predicate.

This requires realizing the entirety of the structure.

Sourceval find : ('a -> bool) -> 'a t -> 'a option

Return the first item in the lazy list that satisfies the predicate.

Combining

Sourceval concat : 'a t -> 'a t -> 'a t

Combine two lazy lists into a single lazy list, one after the other.

Sourceval zip_with : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Merge two lazy lists together with a generating function.

Sourceval zip : 'a t -> 'b t -> ('a * 'b) t

Merge two lazy lists into a lazy list of pairs.

Sourceval zip_all_with : ('a option -> 'b option -> 'c) -> 'a t -> 'b t -> 'c t

Like zip_with, but merge elements from differently sized lazy lists.

Sourceval zip_all : 'a t -> 'b t -> ('a option * 'b option) t

Like zip, but merge elements from differently sized lazy lists.

Folding

Sourceval to_list : 'a t -> 'a list

Realize a lazy list into a strict list.

Sourceval fold_right : 'b Lazy.t -> ('a -> 'b Lazy.t -> 'b) -> 'a t -> 'b

Fold over a lazy list from the right with an accumulation function.

Since the folding function is lazy in the second argument, evaluation of the lazy list can be short-circuited.

Sourceval fold_left : 'b -> ('b -> 'a -> 'b) -> 'a t -> 'b

Fold over a lazy list from the left with an accumulation function.

Iterating

Sourceval iter : ('a -> unit) -> 'a t -> unit

iter f t applies the function f to each item in the lazy list. This only makes sense when f performs stateful effects.

package zlist

Module Zlist.Lazy_listSource