[Haskell-cafe] Reference for technique wanted

[Claus Reinke]

> I haven't the faintest idea what SML is doing with the third
> version, but clearly it shouldn't.  

Those numbers are worrying, not just because of the third
version - should doubling the tree size have such a large effect?

> I find your report that GHC doesn't do as well with the third 
> version as the first two somewhat reassuring.

Well, I reported it as a performance bug;-) Also because 
GHC 6.12.3 had the second version as fast as the first while
GHC 7.1.x had the second version as slow as the third. You
can find my code in the ticket:

http://hackage.haskell.org/trac/ghc/ticket/4474

> The difference makes me wonder whether there might be
> performance consequences of the point-free style in more cases.

It would be good to know what is going on, as those
code transformations are not unusual, and I like to be
aware of any major performance trade-offs involved.
 
>> I'd still call both patterns difference lists,
> 
> I have been shouting about how bad a name "difference list" is
> in >Prolog< for about 20 years.  

Ah, when you put it like this, I agree completely. The name
focusses on the wrong part of the idea, or rather on the
junk in one particular, explanatory representation of the idea.

> It really is much more useful in Prolog
> to think of list differences as a kind of *relationship*, because
> then you are able to think "hey, why just two ends?  Why can't I
> pass around *several* references into the same list?

Names have power - if you want to get rid of one as well
established as "difference lists", you'll have to replace it 
with another. How about 

    "incomplete data structures"? 

That is already used in connection with more general 
applications of logic variables, and it focusses on half of 
the interesting bit of the idea (the other part  being how 
one completes the structures).

Then logic programmers can think of logic variables,
functional programmers can think of parameterised
structures, operational semanticists can think of contexts
with hole filling, denotational semanticists can think of
partially defined structures, and so on..

Claus