[Haskell-cafe] Re: appending an element to a list
Ronald Guida wrote:
Thank you, apfelmus. That was a wonderful explanation; the debit
method in [1] finally makes sense.
A diagram says more than a thousand words :)
My explanation is not entirely faithful to Okasaki, let me elaborate.
In his book, Okasaki calls the process of transferring the debits from
the input
xs = x1 : x2 : x3 : ... : xn : []
111 ... 11 0
ys = y1 : y2 : y3 : ... : ym : []
111 ... 11 0
to the output
xs ++ ys = x1 : x2 : x3 : ... : xn : y1 : y2 : y3 : ... : ym : []
222 ... 22111 ... 11 0
debit inheritance. In other words, the debits of xs and ys (here 1 at
each node) are carried over to xs ++ ys (in addition to the debits
created by ++ itself). In the thesis, he doesn't give it an explicit
name, but discusses this phenomenon in the very last paragraphs of
chapter 3.4 .
The act of relocating debits from child to parent nodes as exemplified with
xs ++ reverse ys =
x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : []
111 ... 11n0 ... 00 0
xs ++ reverse ys =
x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : []
222 ... 2200 ... 00 0
is called debit passing, but Okasaki doesn't use it earlier than in
the chapter Implicit recursive slowdown. But the example I gave here
is useful for understand the scheduled implementation of real time
queues. The trick there is to not create a big suspension with n
debits but to really physically distribute them across the data structure
x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : []
222 ... 2222 ... 22 2
and discharge them by forcing a node with every call to snoc . I say
physically because this forcing performs actual work, it does not
simply mentally discharge a debit to amortize work that will be done
later. Note that the 2 debits added to each yi are an overestimation
here, but the real time queue implementation pays for them nonetheless.
My focus on debit passing in the original explanation might suggest that
debits can only be discharged when actually evaluating the node to which
the debit was assigned. This is not the case, an operation may discharge
any debits, even in parts of the data structure that it doesn't touch.
Of course, it must discharge debits of nodes it does touch.
For instance, in the proof of theorem 3.1 (thesis) for queues, Okasaki
writes We can restore the invariant by discharging the first (two)
debit(s) in the queue without bothering to analyze which node this
will be. So, the front queue might look like
f1 : f2 : f3 : ... : fn : f{n+1} : f{n+2} : ... : fm : []
001 ... 11n0 ... 00 0
and it's one of the nodes that carries one debit, or it could look like
f2 : f3 : ... : fn : f{n+1} : f{n+2} : ... : fm : []
00 ... 00 n-3 0 ... 00 0
and it's the node with the large amount of debits. In fact, it's not
even immediate that these two are the only possibilities.
However, with the debit passing from my previous post, it's easier to
say which node will be discharged. But even then, only tail discharges
exactly the debits of nodes it inspects while the snoc operation
discharges debits in the untouched front list. Of course, as soon as
identifying the nodes becomes tractable, chances are that you can turn
it into a real-time data structure.
Another good example are skew heaps from
[2]:
Chris Okasaki. Fun with binary heap trees.
in J. Gibbons, O. de Moor. The Fun of Programming.
http://www.palgrave.com/PDFs/0333992857.Pdf
Here, the good nodes are annotated with one debit. Every join
operation discharges O(log n) of them and allocates new ones while
walking down the tree, but the time to actually walk down the tree is
not counted immediately. This is just like (++) walks down the first
list and allocates debits without immediately using O(n) time to do that.
Regards,
apfelmus
PS: In a sense, discharging arbitrary debits can still be explained with
debit passing: first pass those debits to the top and the discharge them
because any operation has to inspect the top.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: appending an element to a list
Abhay Parvate wrote:
I somehow thought it would be easy to talk about complexity of calculating
individual elements in an infinite list should be sufficient, but that seems
to be involved, and my over-generalization doesn't seem to work. Thanks for
the link; particularly it has reference to Wadler's papers exactly on this
problem.
Note however that Wadler's and similar formalisms are still a
unsatisfactory in that they are quite clumsy to work with, it's quite
tedious/impossible to analyze examples with a lot of lazy evaluation.
But they are a good guideline.
In his book about purely functional data structures [1], Okasaki takes a
different approach; each node of a data structure is given a debit, a
cost to evaluate it. For instance, consider
xs = x1 : x2 : x3 : ... : xn : []
111 ... 11 0
ys = y1 : y2 : y3 : ... : ym : []
111 ... 11 0
The numbers below indicate the time it takes to evaluate the node to
weak head normal form. For demonstration purposes, I arbitrarily chose 1
for each (:) here.
The combined list will then have debits like
xs ++ ys = x1 : x2 : x3 : ... : xn : y1 : y2 : y3 : ... : ym : []
222 ... 22111 ... 11 0
In other words, the ys list is copied verbatim but each element of xs
incurs an additional cost of 1, corresponding to one step in the
evaluation of the concatenation with (++).
In order to force/inspect a constructor/node, you have to pay off its
debits first. In the above example, head (xs ++ ys) would have to pay
2 units of time (one unit for head xs and one for the (++)). Now, the
thing about debits is that we can relocate them to the top and only
overestimate the total running time if we do that. For instance, we
could push all debits to the top
xs ++ ys = x1 : x2 : x3 : ... : xn : y1 : y2 : y3 : ... : ym : []
2n+m 00 ... 00000 ... 00 0
so that evaluating head (xs ++ ys) is now estimated to cost (2n+m)
units of time while the rest is free/fully evaluated.
The above example is rather useless, but consider the case n == m and
xs = x1 : x2 : x3 : ... : xn : []
000 ... 00 0
ys = y1 : y2 : y3 : ... : yn : []
000 ... 00 0
i.e. two fully evaluated lists of the same length. Then, we have
xs ++ reverse ys =
x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : []
111 ... 11n0 ... 00 0
because reversing the list ys is monolithic, i.e. looking at its head
already forces the tail of the list. But now, we can distribute the
debits upwards
xs ++ reverse ys =
x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : []
222 ... 2200 ... 00 0
and thereby amortize the cost of reversing the second lists over the n
elements of the first list. This is used in the implementation of purely
functional queues, see also Okasaki's book.
[1]: Chris Okasaki. Purely Function Data Structures.
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
(This is the thesis on which the book is based.)
Regards,
apfelmus
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: appending an element to a list
Thank you, apfelmus. That was a wonderful explanation; the debit method in [1] finally makes sense. [1]: Chris Okasaki. Purely Function Data Structures. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: appending an element to a list
Tillmann Rendel wrote: Abhay Parvate wrote: I think I would like to make another note: when we talk about the complexity of a function, we are talking about the time taken to completely evaluate the result. Otherwise any expression in haskell will be O(1), since it just creates a thunk. I don't like this notion of complexity, since it seems not very suited for the analysis of composite expression in Haskell. Is this intuitive view generalizable to arbitrary datatypes (instead of lists) and formalized somewhere? See also the thread section beginning with http://thread.gmane.org/gmane.comp.lang.haskell.cafe/34398/focus=34435 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: appending an element to a list
I somehow thought it would be easy to talk about complexity of calculating individual elements in an infinite list should be sufficient, but that seems to be involved, and my over-generalization doesn't seem to work. Thanks for the link; particularly it has reference to Wadler's papers exactly on this problem. Abhay On Sun, Jun 1, 2008 at 1:07 PM, apfelmus [EMAIL PROTECTED] wrote: Tillmann Rendel wrote: Abhay Parvate wrote: I think I would like to make another note: when we talk about the complexity of a function, we are talking about the time taken to completely evaluate the result. Otherwise any expression in haskell will be O(1), since it just creates a thunk. I don't like this notion of complexity, since it seems not very suited for the analysis of composite expression in Haskell. Is this intuitive view generalizable to arbitrary datatypes (instead of lists) and formalized somewhere? See also the thread section beginning with http://thread.gmane.org/gmane.comp.lang.haskell.cafe/34398/focus=34435 Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: appending an element to a list
Abhay Parvate wrote: I think I would like to make another note: when we talk about the complexity of a function, we are talking about the time taken to completely evaluate the result. Otherwise any expression in haskell will be O(1), since it just creates a thunk. I don't like this notion of complexity, since it seems not very suited for the analysis of composite expression in Haskell. For example, repeat 42 has infinite complexity according to your definition (it doesn't even terminate if completely evaluated), but take 5 $ repeat 42 has only constant complexity even if fully evaluated. It is not clear how to reuse the finding about the complexity of (repeat 42) to determine the complexity of (take 5). Instead, my view of complexity in lazy languages includes the interesting behaviour of the rest of the program as variables. For example, (repeat 42) needs O(n) steps to produce the first n elements of its output. Now, (take 5 x) restricts x to the first 5 elements, so (take 5 $ repeat 42) needs O(min(n, 5)) = O(1) steps to produce the first n elements of its output. Is this intuitive view generalizable to arbitrary datatypes (instead of lists) and formalized somewhere? Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: appending an element to a list
Tillmann Rendel [EMAIL PROTECTED] writes:
Hi! (Cool, another guy from DAIMI on haskell-cafe!)
Another (n - 1) reduction steps for the second ++ to go away.
last (o ++ l)
A) ~ last ('o' : ++ l))
L) ~ last ( ++ l)
A) ~ last (l)
L) ~ 'l'
And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
steps. Counting together, we had to use
n + (n - 1) + (n - 2) + ... = n!
reduction steps to get rid of the n calls to ++, which lies in O(n^2).
Thats what we expected of course, since we know that each of the ++
would need O(n) steps.
I really liked the excellent and very clear analysis! But the last
formula should be:
n + (n - 1) + (n - 2) + ... = n * (n+1) / 2
which is still of order n^2.
--
Martin Geisler
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
pgpxgbfpNjJtq.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: appending an element to a list
I think I would like to make another note: when we talk about the complexity
of a function, we are talking about the time taken to completely evaluate
the result. Otherwise any expression in haskell will be O(1), since it just
creates a thunk.
And then the user of the program is to be blamed for running the program,
since that is what caused evaluation of those thunks :)
Abhay
2008/5/31 Martin Geisler [EMAIL PROTECTED]:
Tillmann Rendel [EMAIL PROTECTED] writes:
Hi! (Cool, another guy from DAIMI on haskell-cafe!)
Another (n - 1) reduction steps for the second ++ to go away.
last (o ++ l)
A) ~ last ('o' : ++ l))
L) ~ last ( ++ l)
A) ~ last (l)
L) ~ 'l'
And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
steps. Counting together, we had to use
n + (n - 1) + (n - 2) + ... = n!
reduction steps to get rid of the n calls to ++, which lies in O(n^2).
Thats what we expected of course, since we know that each of the ++
would need O(n) steps.
I really liked the excellent and very clear analysis! But the last
formula should be:
n + (n - 1) + (n - 2) + ... = n * (n+1) / 2
which is still of order n^2.
--
Martin Geisler
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
