(* Continuations Course: COMP 302: Programming Languages and Paradigms Author: Brigitte Pientka *) (* Direct-style append append: 'a list * 'a list -> 'a list *) fun append(nil, k) = k | append(h::t, k) = h::(append(t,k)) (* Continuation-style append with the use of the continuation-style function app_tr: 'a list * 'a list * ('a list -> 'a list) -> 'a list *) fun app_tr (l1, l2) = let fun app' (nil, l, c) = c l | app' (h::t, l, c) = app' (t, l, (fn r => c (h::r))) in app' (l1, l2 , fn r => r) end (* Traversing a tree and finding an element *) datatype 'a tree = Empty | Node of 'a tree * 'a * 'a tree fun find(p, Empty) = NONE | find(p, Node(L, d, R)) = if (p d) then SOME(d) else (case find(p, L) of NONE => find(p, R) | SOME(d') => SOME(d')) fun find_tr(p, Empty, cont) = cont () | find_tr(p, Node(L, d, R), cont) = if (p d) then SOME(d) else find_tr(p, L, fn () => find_tr(p, R, cont)) fun find' (p,t) = find_tr (p, t, fn () => NONE) (* val l1 = Node (Node (Empty,3,Empty),5,Node (Empty,7,Empty)) val t = Node(Node (Node (Empty,3,Empty),5,Node (Empty,7,Empty)), Node(Empty, 15, Empty)) val p = (fn x => x = 15) find_tr(p, t, fn () => NONE) --> find_tr(p, l1, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) ------ work we still may need to do on the right --- --> find_tr(p, Node (Empty,3,Empty), fn () => find_tr(p, Node(E, 7, E), ....)) --> find_tr(p, Empty, fn () => find_tr(p, Empty, fn () => find_tr(p, Node(E, 7, E), ....)) --> (fn () => find_tr(p, Empty, fn () => find_tr(p, Node(E, 7, E), ....)) () *** pop the stack ! *** --> find_tr(p, Node(E, 7, E), fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) --> find_tr(p, E, fn () => find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) (***** pop the last element of the stack! ***) --> (fn () => find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE))) () ---> find_tr(p, Empty, fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) --> (fn () => find_tr(p, Node(Empty, 15, Empty), fn () => NONE)) () --> find_tr(p, Node(Empty, 15, Empty), fn () => NONE --> SOME(15) *) fun findAll (p, Empty) = [] | findAll (p, Node(L,d,R)) = if (p d) then findAll(p,L)@[d]@findAll(p,R) else (case findAll(p,L) of [] => findAll(p,R) | el' => (el')@[d]@findAll(p,R)) fun findAll' (p, Empty, sc) = sc [] | findAll' (p, Node(L,d,R), sc) = if (p d) then findAll' (p, L, fn el => findAll'(p,R, fn er => sc (el@(d::er)))) else findAll' (p, L, fn el => findAll' (p, R, fn er => sc (el@er))) fun findEvery (p,T) = findAll'(p,T, fn el => case el of nil => NONE | _ => SOME(el)) fun findAll2 (p, Empty, sc) = sc [] | findAll2 (p, Node(L,d,R), sc) = findAll2 (p, L, fn el => findAll2(p, R, (fn er => let val cl = if p d then el@(d::er) else el @ er in sc cl end))) ; fun findEvery2 (p,T) = findAll2 (p,T, fn el => el) val L = Node (Node (Empty, 2, Empty), 5, Node (Empty, 6, Empty)); val R = Node (Empty, 12, Empty); val T = Node (Node (L, 7, Node (Empty, 8, Empty)), 11, R); fun even x = (x mod 2) = 0 fun odd x = (x mod 2) = 1 val l = findEvery (even , T) val l' = findEvery2 (even , T) val r = findEvery (odd , T) val r' = findEvery2 (odd , T) (* ---------------------------------------------------------------------------- *)