"Brent Yorgey" wrote:

Well, (:) has type a -> [a] -> [a], so a function corresponding to (:) for Hughes lists should have type

foo :: a -> H a -> H a

[...] I think the key sentence from the paper is this: "by representing a list xs as the function (xs ++) that appends this list to another list that has still to be supplied." If you understand that sentence, then you can understand why [] is id and (++) is (.).

Yes, I did. They key was not thinking that : has type (:) :: a -> a -> [a] , or, put differently, beat the lisp out of me, thanks. The problem is merely that Haskell and lisp are too similar in a much too different way. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

Achim Schneider wrote:

(define (cons x y) (lambda (m) (m x y)))

(define (car z) (z (lambda (p q) p)))

(define (cdr z) (z (lambda (p q) q)))

, which, just for completeness, can be of course also be done in Haskell: cons :: a -> b -> (a -> b -> c) -> c cons x y m = m x y car :: ((a -> b -> a) -> c) -> c car z = z $ \p q -> p cdr :: ((a -> b -> b) -> c) -> c cdr z = z $ \p q -> q Prelude> car $ cdr $ cdr $ cons 1 $ cons 2 $ cons 3 () 3 -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

On Thu, 3 Jan 2008, Isaac Dupree wrote:

Achim Schneider wrote:

...

Achim Schneider wrote:

...

[...]

I'm trying to grok that

[] = id ++ = .

in the context of Hughes lists.

they are also known as "difference lists", and also used at type String in the Prelude as "ShowS", to help avoid quadratic behavior when making complicated Strings.

Sometimes I believed that I understand this reason, but then again I do not understand. I see that left-associative (++) like in ((a0 ++ a1) ++ a2) ++ a3 would cause quadratic time. But (++) is right-associative and 'concat' is 'foldr'. They should not scan the leading lists more than once. Also http://en.wikipedia.org/wiki/Difference_list doesn't answer this question. Where exactly is the problem?

On Thu, 3 Jan 2008, Achim Schneider wrote:

Henning Thielemann wrote:

...

Sometimes I believed that I understand this reason, but then again I do not understand. I see that left-associative (++) like in ((a0 ++ a1) ++ a2) ++ a3 would cause quadratic time. But (++) is right-associative and 'concat' is 'foldr'. They should not scan the leading lists more than once. Also http://en.wikipedia.org/wiki/Difference_list doesn't answer this question. Where exactly is the problem?

| The shows functions return a function that prepends the output String | to an existing String. This allows constant-time concatenation of | results using function composition.

How is "constant-time concatenation" meant? If I process all list elements, it will need linear time. If I do not touch any element, I will need no time due to lazy evaluation. As far as I know, lazy evaluation is implemented by returning a union of a routine generating the actual value and the value, if it was already computed. Thus, calling (++) returns a function internally.

I figure it's (constant vs. linear) vs. (linear vs. quadratic), for more involved examples.

I can't see it. If I consider (x++y) but I do not evaluate any element of (x++y) or only the first element, then this will need constant time. If I evaluate the first n elements I need n computation time units. How is (.) on difference lists faster than (++) here?

Henning Thielemann wrote:

I can't see it. If I consider (x++y) but I do not evaluate any element of (x++y) or only the first element, then this will need constant time. If I evaluate the first n elements I need n computation time units. How is (.) on difference lists faster than (++) here?

That's a very good question. Basically, the problem is: how to specify the time complexity of an operation under lazy evaluation? You argue that (++) is constant time in the sense that evaluating (x ++ y) to WHNF is O(1) when x and y are already in WHNF. Same for (.). This is indeed correct but apparently fails to explain why (.) is any better than (++). Help! Of course, this very paradox shows that just looking at WHNF is not enough. The next best description is to pretend that our language is strict and to consider full normal form x in NF, y in NF --> (x++y) evaluates to NF in O(length x) time Even when x and y are not in normal form, we know that evaluating the expression (x ++ y) takes O(x ++ y) ~ O(length x) + O(x) + O(y) time to evaluate to NF. Here, O(e) is the time needed to bring the expression e into NF first. This approach now explains that (++) takes quadratic time when used left-associatively O((x ++ y) ++ z) ~ O(length x + length y) + O(length x) + O(x) + O(y) + O(z) instead of the expected O((x ++ y) ++ z) ~ O(x) + O(y) + O(z) or something (only up to constant factors and stuff, but you get the idea). Note that considering NFs is still only an approximation since O(head (qsort xs)) ~ O(n) + O(xs) where n = length xs instead of the expected O(head (qsort xs)) ~ O(qsort xs) ~ O(n log n) + O(xs) where n = length xs thanks to lazy evaluation. Also note that despite considering full normal forms, we can express some laziness with this by giving timings for an expression in different contexts like O(take n ys) O(head ys) instead of only O(ys). Same for parameters with something like O(const x) ~ O(1) instead of the anticipated O(const x) ~ O(x). (For lazy data structures, there are better ways to take laziness into account.)

With difference lists I write

shows L . (shows T . shows R) (shows LL . (showsLT . shows LR)) . (shows T . shows R) ((shows LLL . (shows LLT . shows LLR)) . (showsLT . shows LR)) . (shows T . shows R)

I still need to resolve three (.) until I get to the first character of the result string, but for the subsequent characters I do not need to resolve those dots. In the end, resolution of all (.) may need some time but then concatenation is performed entirely right-associative. Seems to be that this is the trick ...

So far so good, but the problem now is that analyzing (.) with full normal forms is doomed since this would mean to evaluate things under the lambda which may take less time than doing call-by-need reductions. Still, we somehow have O(x . y) ~ O(x) + O(y) which is better than O(x ++ y) but I'm not quite sure how to make this exact yet. In the end, the above O(e)s are just random doodles conjured out of the hat, I don't know a formalism for easy reasoning about time in a lazy language. Anyone any pointers? Note that the problem is already present for difference lists in strict languages. Regards, apfelmus

apfelmus wrote:

I don't know a formalism for easy reasoning about time in a lazy language. Anyone any pointers? Note that the problem is already present for difference lists in strict languages.

http://homepages.inf.ed.ac.uk/wadler/topics/strictness-analysis.html especially "strictness analysis aids time analysis". Much CPO math is involved, but I view it as: a function gives you output; if you know how much of the output you use, you can deduce how much work the function goes through.

On Wed, 9 Jan 2008, apfelmus wrote:

So, difference lists are no "eierlegende wollmilchsau" either.

LEO's forum suggests 'swiss army knife' as translation. :-)

Achim Schneider wrote:

Henning Thielemann wrote:

...

apfelmus wrote:

...

So, difference lists are no "eierlegende wollmilchsau" either.

...

LEO's forum suggests 'swiss army knife' as translation. :-)

But you really need one with 5 differently-sized blades plus three spezialized carving blades, an USB stick, microscope, 13 kinds of torx, imbus etc drivers each, a tv set (analogue/digital) with unfoldable touchscreen, at least 3-band GSM and WiFi connectivity, hydraulic car jack and chain saw to award it with the term egg-laying woolmilkpig.

But even such knives still can't lay eggs :( Regards, apfelmus

ajb@spamcop.net wrote:

G'day all.

Quoting Achim Schneider :

...

But you really need one with 5 differently-sized blades plus three spezialized carving blades, an USB stick, microscope, 13 kinds of torx, imbus etc drivers each, a tv set (analogue/digital) with unfoldable touchscreen, at least 3-band GSM and WiFi connectivity, hydraulic car jack and chain saw to award it with the term egg-laying woolmilkpig.

So a better translation into British engineering language might be "Heath Robinson"?

Not really. To give you the perfect cs example, take a look at emacs: eight megabytes and continuous swapping, a whole OS with any app and library you could ever dream of, but not one decent editor. See, on the one hand that beast is every farmer's dream, but then you can't butcher the pig 'cos you want to have its milk, wool and eggs.. http://catb.org/jargon/html/C/creeping-featuritis.html is the associated plague. Outlook reminds me of it, too: I spend half a paid hour configuring it, changing everything, from default message format to quote behaviour and similar. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.

Am Donnerstag, 3. Januar 2008 14:48 schrieb Henning Thielemann:

On Thu, 3 Jan 2008, Isaac Dupree wrote:

...

Achim Schneider wrote:

...

Achim Schneider wrote:

...

[...]

I'm trying to grok that

[] = id ++ = .

in the context of Hughes lists.

they are also known as "difference lists", and also used at type String in the Prelude as "ShowS", to help avoid quadratic behavior when making complicated Strings.

Sometimes I believed that I understand this reason, but then again I do not understand. I see that left-associative (++) like in ((a0 ++ a1) ++ a2) ++ a3 would cause quadratic time. But (++) is right-associative and 'concat' is 'foldr'. They should not scan the leading lists more than once. Also http://en.wikipedia.org/wiki/Difference_list doesn't answer this question. Where exactly is the problem?

Show a binary tree inorder? L-T-R gives (show L) ++ (show T ++ (show R)) gives ((show LL) ++ (showLT ++ (show LR))) ++ (show T ++ (show R)) gives (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) etc. If the tree is large, you end up with a pretty large left association for the left subtree. True, there's lot of right association, too, but bad enough, I think. Cheers, Daniel

On 3 Jan 2008, at 4:49 AM, Isaac Dupree wrote:

Achim Schneider wrote:

...

Achim Schneider wrote:

...

[...] I'm trying to grok that [] = id ++ = . in the context of Hughes lists.

they are also known as "difference lists", and also used at type String in the Prelude as "ShowS", to help avoid quadratic behavior when making complicated Strings. the [a]->[a] is not an ordinary function -- it's expected not to examine its argument, just to use it exactly once (is there a formal way to say that?)

f xn = f [] ++ xn is the first thing off the top of my head. OTOH, examining your argument (while, strictly speaking unsafe) is pretty darn cool: f [] = "foo" f (c:s) | isAlphaNum c = "foo "++c:s | otherwise = "foo"++c:s Token prepend. jcc

Isaac Dupree wrote:

Achim Schneider wrote:

...

http://www.cs.nott.ac.uk/~gmh/wrapper.pdf

on page 6, stronger vs weaker seemed backwards to me... isn't (wrap ◦ unwrap = idA) a stronger condition than (wrap ◦ unwrap ◦ body = body), because it tells you more, and is true in fewer cases? (which is also why you want to assume (wrap ◦ unwrap = idA) when you can, because it's the most useful one for subsequent program transformation)

Ah, thanks you say that, I have been asking myself if that was just me, having things backward. In my book, stronger => weaker, too. Cheers Ben