Standard ML

sequences

---

lazy lists

• Elements are not evaluated until their values are required
• May be infinite
• Example: a sequence of all even integers $0, 2, -2, 4, \ldots$

lazy lists in ML

ML evaluates E in Cons(x,E), so to obtain laziness we must write Cons(x, fn()=>E)

datatype 'a seq = Nil
    | Cons of 'a * (unit -> 'a seq);

fun take s 0 = []
  | take Nil _ = []
  | take (Cons (x, xf)) n = x :: take (xf ()) (n - 1);

examples of sequences

$1, 2, 3, 4, \ldots$

fun from k = Cons (k, fn () => from (k + 1));

from 1;

take it 10;

examples of sequences

$0, 2, -2, 4, \ldots$

fun from_even n = let
    val next = if n > 0 then ~n else ~n + 2
  in
    Cons (n, fn () => from_even next)
  end;

from_even 0;

take it 10;

---

Processing sequences

squares takes a sequence of integers and returns a sequence of their squares:

fun squares Nil = Nil
  | squares (Cons (x, xf)) =
        Cons (x * x, fn () => squares (xf ()));

squares (from 1);

take it 10;

addq

Implement addq that takes two integer sequences and adds them element-wise

...
(*val addq = fn : int seq * int seq -> int seq*)

addq

fun addq (Cons (x, xf), Cons (y, yf)) =
        Cons (x + y, fn () => addq (xf (), yf ()))
  | addq _ = Nil;

addq (from 1, from 1);
take it 10;

appendq

Implement appendq that appends two sequences

...
(*val appendq = fn : 'a seq * 'a seq -> 'a seq*)

appendq

fun appendq (Nil, yq) = yq
  | appendq (Cons (x, xf), yq) =
        Cons (x, fn () => appendq (xf (), yq));

What would appendq(xq,yq) be if xq is infinite?

mapq

Implement mapq that applies a function on the elements of a sequence

...
(*val mapq = fn : ('a -> 'b) -> 'a seq -> 'b seq*)

mapq

fun mapq f Nil            = Nil
  | mapq f (Cons (x, xf)) =
        Cons (f x, fn () => mapq f (xf ()));

mapq (fn x => x * 3) (from 1);
take it 10;

filterq

Implement filterq that filters a sequence based on a predicate

...
(*val filterq = fn : ('a -> bool) -> 'a seq -> 'a seq*)

filterq

fun filterq pred Nil = Nil
  | filterq pred (Cons (x, xf)) =
        if pred x
        then Cons (x, fn () => filterq pred (xf ()))
        else filterq pred (xf ());

filterq (fn x => x mod 2 <> 0) (from 1);
take it 10;

interleaveq

Implement interleaveq that interleaves two sequences.

e.g.: Interleaving 1,2,3,... and 11,12,13,... returns: 1,11,2,12,3,13,4,...

...
(*val interleaveq = fn : 'a seq * 'a seq -> 'a seq*)

interleaveq

fun interleaveq (Nil, yq)       = yq
  | interleaveq (Cons (x, xf), yq) =
        Cons (x, fn () => interleaveq (yq, xf ()));

interleaveq (from 1, from 11);
take it 10;

dropq

dropq takes a sequence s and a positive number n and returns s without its first n elements

...
(*val dropq = fn: 'a seq -> int -> 'a seq*)

dropq

fun dropq seq 0 = seq
  | dropq Nil _ = Nil
  | dropq (Cons (x, xf)) n = dropq (xf ()) (n - 1);

dropq (from 1) 10;
take it 10;

seqToList

seqToList takes a sequence and returns a list of its elements

...
(*val seqToList = fn: 'a seq -> 'a list*)

seqToList

fun seqToList Nil = []
  | seqToList (Cons (x, xf)) = x :: (seqToList (xf ()));

listToSeq

listToSeq takes a list and returns a sequence of its elements

...
(*val listToSeq = fn: 'a list -> 'a seq*)

listToSeq

fun listToSeq [] = Nil
  | listToSeq (x :: xs) = Cons (x, fn () => listToSeq xs);

---

Exam Question

...

fraction

fun fraction m n =
  if m mod n = 0
  then Nil
  else Cons (m * 10 div n mod 10, fn () => fraction (m * 10) n);

fraction 1 7;
take it 10;

Exam Question

...

lazy_divide

fun lazy_divide m n = (m div n, fraction (m mod n) n);

---

Sequences exercise

(a hard one in fact…)

Let’s define a lazy tree datatype, using sequences:

datatype 'a seq = Nil | Cons of 'a * (unit -> 'a seq)

datatype 'a option = NONE | SOME of 'a;

datatype 'a node =
  Node of 'a * (unit -> 'a node option) * (unit -> 'a node option);

type 'a lazy_tree = unit -> 'a node option;

fun take s 0 = []
  | take Nil _ = []
  | take (Cons (x, xf)) n = x :: take (xf ()) (n - 1);

Let’s define some trees:

fun t1 () = NONE;
fun t2 0 () = SOME (Node (0, t1, t1))
  | t2 n () = SOME (Node (n, t2 (n div 2), t2 (n - 1)));

Implement lazy bfs traversal of lazy trees

...

local
  fun aux [] [] = Nil
    | aux [] ts = aux (map (fn t => t ()) ts) []
    | aux (NONE :: ns) ts = aux ns ts
    | aux ((SOME (Node (h, l, r))) :: ns) ts = 
    	Cons(h, fn () => aux ns (ts @ [l, r]))
in
  fun bfs t = aux [t ()] []
end;

take (bfs (t2 10)) 10;