[ Pobierz całość w formacie PDF ]
." Flatten of X|Xr where X is a nested list, is Z whereflatten of X is Y,flatten of Xr is Yr, andappend Y and Yr to get Z." Flatten of X|Xr where X is not a list, is Z whereflatten of Xr is Yr, andZ is X|Yr.Following this reasoning, we get the following definition:fun {Flatten Xs}case Xsof nil then nil[] X|Xr andthen {IsList X} then{Append {Flatten X} {Flatten Xr}}[] X|Xr thenX|{Flatten Xr}endendCalling:{Browse {Flatten [[a b] [[c] [d]] nil [e [f]]]}}displays [a b c d e f].This program is very inefficient because it needs to domany append operations (see Exercises).Now let us reason again in the sameway, but with difference lists instead of standard lists:" Flatten of nil is X#X (empty difference list)." Flatten of X|Xr where X is a nested list, is Y1#Y4 whereflatten of X is Y1#Y2,flatten of Xr is Y3#Y4, andequate Y2 and Y3 to append the difference lists." Flatten of X|Xr where X is not a list, is (X|Y1)#Y2 whereflatten of Xr is Y1#Y2.We can write the second case as follows:" Flatten of X|Xr where X is a nested list, is Y1#Y4 whereflatten of X is Y1#Y2 andflatten of Xr is Y2#Y4.This gives the following program:Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.4 Programming with recursion 147fun {Flatten Xs}proc {FlattenD Xs ?Ds}case Xsof nil then Y in Ds=Y#Y[] X|Xr andthen {IsList X} then Y1 Y2 Y4 inDs=Y1#Y4{FlattenD X Y1#Y2}{FlattenD Xr Y2#Y4}[] X|Xr then Y1 Y2 inDs=(X|Y1)#Y2{FlattenD Xr Y1#Y2}endend Ysin{FlattenD Xs Ys#nil} YsendThis program is efficient: it does a single cons operation for each non-list in theinput.We convert the difference list returned by FlattenD into a regular list bybinding its second argument to nil.We write FlattenDas a procedure becauseits output is part of its last argument, not the whole argument (see Section 2.5.2).It is common style to write a difference list in two arguments:fun {Flatten Xs}proc {FlattenD Xs ?S E}case Xsof nil then S=E[] X|Xr andthen {IsList X} then Y2 in{FlattenD X S Y2}{FlattenD Xr Y2 E}[] X|Xr then Y1 inS=X|Y1{FlattenD Xr Y1 E}endend Ysin{FlattenD Xs Ys nil} YsendAs a further simplification, we can write FlattenD as a function.To do this, weuse the fact that S is the output:fun {Flatten Xs}fun {FlattenD Xs E}case Xsof nil then E[] X|Xr andthen {IsList X} then{FlattenD X {FlattenD Xr E}}[] X|Xr thenCopyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 148 Declarative Programming TechniquesX|{FlattenD Xr E}endendin{FlattenD Xs nil}endWhat is the role of E? It gives the rest of the output, i.e., when the FlattenDcall exhausts its own contribution to the output.Reversing a listLet us look again at the naive list reverse of the last section.The problem withnaive reverse is that it uses a costly append function.Perhaps it will be moreefficient with the constant-time append of difference lists? Let us do the naivereverse with difference lists:" Reverse of nil is X#X (empty difference list)." Reverse of X|Xs is Z, wherereverse of Xs is Y1#Y2 andappend Y1#Y2 and (X|Y)#Y together to get Z.Rewrite the last case as follows, by doing the append:" Reverse of X|Xs is Y1#Y, wherereverse of Xs is Y1#Y2 andequate Y2 and X|Y.It is perfectly allowable to move the equate before the reverse (why?).This gives:" Reverse of X|Xs is Y1#Y, wherereverse of Xs is Y1#(X|Y).Here is the final definition:fun {Reverse Xs}proc {ReverseD Xs ?Y1 Y}case Xsof nil then Y1=Y[] X|Xr then{ReverseD Xr Y1 X|Y}endend Y1in{ReverseD Xs Y1 nil} Y1endCopyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 3.4 Programming with recursion 149Look carefully and you will see that this is almost exactly the same iterativesolution as in the last section.The only difference between IterReverse andReverseD is the argument order: the output of IterReverse is the secondargument of ReverseD.So what s the advantage of using difference lists? Withthem, we derived ReverseD without thinking, whereas to derive IterReversewe had to guess an intermediate state that could be updated.3.4.5 QueuesAn important basic data structure is the queue.A queue is a sequence of elementswith an insert and a delete operation.The insert operation adds an element toone end of the queue and the delete operation removes an element from the otherend.We say the queue has FIFO (First-In-First-Out) behavior.Let us investigatehow to program queues in the declarative model.Anaive queueAn obvious way to implement queues is by using lists.If L represents the queuecontent, then inserting X gives the new queue X|L and deleting X is done bycalling {ButLast L X L1}, which binds X to the deleted element and returnsthe new queue in L1.ButLastreturns the last element of L in X and all elementsbut the last in L1.It can be defined as:proc {ButLast L ?X ?L1}case Lof [Y] then X=Y L1=nil[] Y|L2 then L3 inL1=Y|L3{ButLast L2 X L3}endendThe problem with this implementation is that ButLast is slow: it takes timeproportional to the number of elements in the queue.On the contrary, we wouldlike both the insert and delete operations to be constant-time.That is, doing anoperation on a given implementation and machine always takes time less thansome constant number of seconds.The value of the constant depends on theimplementation and machine.Whether or not we can achieve the constant-timegoal depends on the expressiveness of the computation model:" In a strict functional programming language, i.e., the declarative modelwithout dataflow variables (see Section 2.7.1), we cannot achieve it.Thebest we can do is to get amortized constant-time operations [138].Thatis, any sequence of n insert and delete operations takes a total time thatis proportional to some constant times n.Any individual operation mightnot be constant-time, however.Copyright © 2001-3 by P.Van Roy and S.Haridi.All rights reserved. 150 Declarative Programming Techniques" In the declarative model, which extends the strict functional model withdataflow variables, we can achieve the constant-time goal.We will show how to define both solutions.In both definitions, each operationtakes a queue as input and returns a new queue as output.As soon as a queueis used by the program as input to an operation, then it can no longer be usedas input to another operation.In other words, there can be only one version ofthe queue in use at any time.We say that the queue is ephemeral.7 Each versionexists from the moment it is created to the moment it can no longer be used.Amortized constant-time ephemeral queueHere is the definition of a queue whose insert and delete operations have constantamortized time bounds
[ Pobierz całość w formacie PDF ]
