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)?
There seem to be two different issues at hand here:
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
