[Haskell-cafe] Reference for technique wanted

[Richard O'Keefe]

On 4/11/2010, at 10:56 PM, Claus Reinke wrote:
> Even in your SML code, the "boring old plain lists" seemed to be list_flatten, which uses difference lists in disguise, and won
> your little test, right? Using Haskell notation:
> 
> flat (LEAF x) ys = x : ys
> flat (FORK(a,b)) ys = flat a (flat b ys)

Measured time:
    0.902 seconds (2**22 leaves)
    2.716 seconds (2**23 leaves)
> -->
> flat (LEAF x)  = \ys->x : ys
> flat (FORK(a,b)) = \ys->flat a (flat b ys)

Measured time:
    0.980 seconds (2**22 leaves)
    7.999 seconds (2**23 leaves)
> -->
> flat (LEAF x)  = (x :)
> flat (FORK(a,b)) = flat a . flat b

Measured time:
   10.189 seconds (2**22 leaves)
  163.184 seconds (2**23 leaves)

In all cases, the final result was a list, not a function.
I was actually expecting the first and second versions to
be the same code.

You have shown very clearly how someone trying to write the
first version in a point-free style would have rediscovered
the list-as-function hack.

I haven't the faintest idea what SML is doing with the third
version, but clearly it shouldn't.  I find your report that
GHC doesn't do as well with the third version as the first
two somewhat reassuring.

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

> 
> As in Prolog, it is often better not to make the structure
> explicit,

If that's a reference to DCGs, they *hide* the difference pair,
but the data structure is still *there*.  

> 
>> The practical consequence of this is that calling both techniques by
>> the same name is going to mislead people familiar with one kind of
>> language when they use the other:  logic programmers will wrongly
>> expect dlists to be practically useful in functional languags,
>> functional programmers will expect them to be impractical in logic
>> programming languages.
> 
> I do tend to expect a little more insight from Haskellers, but
> perhaps you're right.

Yes, but I don't believe the original poster (whose messages you
have not seen) *is* a Haskeller.
> 
> 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.  The problem is that it suggests
that you should think about list differences *as a kind of list*,
which in turn suggests passing around both ends in a single
data structure like your Xs0\Xs.  But doing so turns over a lot
of extra storage and negates much of the performance advantage
of list differences.  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?

Here's a grammar for a**n b**n c**n.

abc(N, ABC) :-
    abc(N, ABC, BC, BC, C, C).

abc(0, ABC, ABC, BC, BC, []).
abc(s(N), [a|ABC1], ABC, [b|BC1], BC, [c|C1]) :-
    abc(N, ABC1, ABC, BC1, BC, C1).

Example:
?- abc(N, ABC).
N = 0,
ABC = [] ;
N = s(0),
ABC = [a, b, c] ;
N = s(s(0)),
ABC = [a, a, b, b, c, c] ;
N = s(s(s(0))),
ABC = [a, a, a, b, b, b, c, c, c] ;
N = s(s(s(s(0)))),
ABC = [a, a, a, a, b, b, b, b, c|...] ;
...
?- abc(N, [a,a,a,a,b,b,b,b,c,c,c,c]).
N = s(s(s(s(0)))) .

?- abc(N, [a,a,a,a,b,b,b,c,c,c,c]).
false.

?- abc(N, [a,a,a,a,b,b,b,b,c,c,c,c,c]).
false.

You eventually realise that in Prolog there is no difference
between list differences and accumulator passing.

If you want to call accumulator passing and higher order
functions by the same name, feel free, just don't expect me
to regard it as illuminating.

> because it can be
> useful to know about the connections,

I've been using Prolog since 1979 and Haskell since, ooh, Haskell 1.3,
but I've never found it useful to know about the connection, and I
plan to forget it as soon as I can.

> but if you could suggest
> text for the DList documentation that warns of the differences,
> and of performance pitfalls, I'm sure the package author would
> be happy to add such improvements.

I've just been marking a software engineering exam in which I asked
the students to comment, with supporting detail, on
	If it hasn't been tested, it doesn't work.
	If it hasn't been ported, it isn't portable.
Let me add one other:
	If it hasn't been measured, it's slower.

Before suggesting changes to any package, it might be worth asking
the question "can we find any examples where this KIND of transformation
DOES pay off"? (compared with other more elementary approaches).

> 
> If we ever get per-package wikis for hackage, you could add such comments yourself.
> 
> Claus
> 
>