(**** LECTURE 9: Queues and Search Strategies ****) (* $Id: queues.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp $ *) (*Naive breadth-first traversal -- slow because of append!*) fun nbreadth [] = [] | nbreadth (Lf :: ts) = nbreadth ts | nbreadth (Br(v,t,u) :: ts) = v :: nbreadth(ts @ [t,u]); (*Applicative queues represented by (heads, reversed tails). deq can take a long time but amortized time per operation is constant. F.W. Burton, ``An efficient functional implementation of FIFO queues'' Information Processing Letters 14 (1982) 205-206. *) datatype 'a queue = Queue of 'a list * 'a list; (*The empty queue*) val qempty = Queue([],[]); (*Is queue empty?*) fun qnull(Queue([],[])) = true | qnull _ = false; (*Normalized queue, if nonempty, has nonempty heads list*) fun norm (Queue([],tails)) = Queue(rev tails, []) | norm q = q; (*Inspect head of queue*) fun qhd(Queue(x::_,_)) = x; (*Remove head of queue. Normalize in case heads becomes empty*) fun deq(Queue(x::heads,tails)) = norm(Queue(heads,tails)); (*Add to end of queue. Normalize in case heads is empty*) fun enq(Queue(heads,tails), x) = norm(Queue(heads, x::tails)); (*Breadth-first traversal using efficient queues*) fun breadth q = if qnull q then [] else case qhd q of Lf => breadth (deq q) | Br(v,t,u) => v :: breadth(enq(enq(deq q, t), u)); val t = fulltree(1,10); nbreadth [t]; (*SLOW*) breadth (enq(qempty,t)); (*FAST*)