How do I create a call-by-need list with increasin

Question

I am trying to create a lazy list with list elements which together represent all the combinations of zeros and ones.

Example: [[], [0], [1], [0,0], [0,1], [1,0]...]

Is this even possible in ML? I can't seem to find a way to change the pattern of the list elements once I have defined it. It seems that there is also a need to define a change in the binary pattern, which is not really possible in a functional language (I've never encountered binary representations in functional language)?

Answer 1

There seem to be two different issues at hand here:

1. How do we generate this particular infinite data structure?
2. In ML, how do we implement call-by-need?

---

Let's begin by considering the first point. I would generate this particular data structure in steps where the input to the nth step is a list of all bit patterns of length n. We can generate all bit patterns of length n+1 by prepending 0s and 1s onto each pattern of length n. In code:

fun generate patterns =
  let
    val withZeros = List.map (fn pat => 0 :: pat) patterns
    val withOnes = List.map (fn pat => 1 :: pat) patterns
    val nextPatterns = withZeros @ withOnes
  in
    current @ generate nextPatterns
  end

val allPatterns = generate [[]]

If you were to implement this approach in a call-by-need language such as Haskell, it will perform well out of the box. However, if you run this code in ML it will not terminate. That brings us to the second problem: how do we do call-by-need in ML?

---

To do call-by-need in ML, we'll need to work with suspensions. Intuitively, a suspension is a piece of computation which may or may not have been run yet. A suitable interface and implementation are shown below. We can suspend a computation with delay, preventing it from running immediately. Later, when we need the result of a suspended computation, we can force it. This implementation uses references to remember the result of a previously forced suspension, guaranteeing that any particular suspension will be evaluated at most once.

structure Susp :>
sig
  type 'a susp
  val delay : (unit -> 'a) -> 'a susp
  val force : 'a susp -> 'a
end =
struct
  type 'a susp = 'a option ref * (unit -> 'a)
  fun delay f = (ref NONE, f)
  fun force (r, f) =
    case !r of
      SOME x => x
    | NONE => let val x = f ()
              in (r := SOME x; x)
              end
end

Next, we can define a lazy list type in terms of suspensions, where the tail of the list is delayed. This allows us to create seemingly infinite data structures; for example, fun zeros () = delay (fn _ => Cons (0, zeros ())) defines an infinite list of zeros.

structure LazyList :>
sig
  datatype 'a t = Nil | Cons of 'a * 'a t susp

  val singleton : 'a -> 'a t susp
  val append : 'a t susp * 'a t susp -> 'a t susp
  val map : ('a -> 'b) -> 'a t susp -> 'b t susp

  val take : 'a t susp * int -> 'a list
end =
struct

  datatype 'a t = Nil | Cons of 'a * 'a t susp

  fun singleton x =
    delay (fn _ => Cons (x, delay (fn _ => Nil)))

  fun append (xs, ys) =
    delay (fn _ =>
      case force xs of
        Nil => force ys
      | Cons (x, xs') => Cons (x, append (xs', ys)))

  fun map f xs =
    delay (fn _ =>
      case force xs of
        Nil => Nil
      | Cons (x, xs') => Cons (f x, map f xs'))

  fun take (xs, n) =
    case force xs of
      Nil => []
    | Cons (x, xs') =>
        if n = 0 then []
        else x :: take (xs', n-1)
end

With this machinery in hand, we can adapt the original code to use lazy lists and suspensions in the right places:

fun generate patterns =
  delay (fn _ =>
    let
      val withZeros = LazyList.map (fn pat => 0 :: pat) patterns
      val withOnes = LazyList.map (fn pat => 1 :: pat) patterns
      val nextPatterns = LazyList.append (withZeros, withOnes)
    in
      force (LazyList.append (patterns, generate nextPatterns))
    end)

val allPatterns = generate (LazyList.singleton [])

We can force a piece of this list with LazyList.take:

- LazyList.take (allPatterns, 10);
val it = [[],[0],[1],[0,0],[0,1],[1,0],[1,1],[0,0,0],[0,0,1],[0,1,0]]
  : int list list