[Haskell-cafe] Reference for technique wanted

[Richard O'Keefe]

On 1/11/2010, at 10:37 PM, Claus Reinke wrote:
> 
> Interesting discussion. I still think it is the same idea,
> namely to represent not-yet-known list tails by variables,
> embedded into two different kinds of languages.
> 
>   \rest->start++rest
>   [start|rest]\rest        -- '\' is an infix constructor

Savvy Prolog programmers wouldn't *DREAM* of
using an infix constructor here.  The art of doing list
differences well in Prolog is to think of a list difference
as a RELATIONSHIP between TWO terms, not as a single data
structure.  (The same is true for the queue example I mentioned.
Keeping the length, the front, and the back as separate arguments
gives usefully better performance.)

> 
> The differences arise from the different handling of
> variables and scoping in those languages:
> 
> - functional languages: explicit, local scopes, variables
>   are bound by injecting values from outside the scope
>   (applying the binding construct to values); scoped
>   expressions can be copied, allowing multiple
>   instantiations of variables
> 
> - logic languages: implicit, global scopes, variables
>   are bound by finding possible values inside the scope

Eh?  The scope of *identifiers* is strictly LOCAL in Prolog.
Logic *variables* don't *have* scope.

> So, yes, the realization of the idea is different, as are the
> language frameworks, and the junk in the representations,
> but the idea is the same.

In an extremely vague and not obviously useful sense.
This is rather like saying that association lists and hash
tables are both implementations of the "finite map" idea,
so we might as well call them by the same name.

The algorithmic and observability properties of the two approaches
are very different.

Since there already is a DList implementation for Haskell,
I decided to write one for SML.  It was very frustrating,
because while everything is possible, almost nothing is easy.
Many of the functions degenerated into

	fun foo x ... = fromList (List.foo (toList x) ...)

and this included head and tail.  Afterwards, looking at
Data.DList to find out what clever trick I had missed, I was
glumly pleased to find out there wasn't one:  head and tail are
O(size of list) in Data.DList too.

The bottom line for anything that's supposed to make concatenation
fast is that it ought to be able to make singleton and ++ fast.
So I tried a test case.

datatype tree = LEAF of int | FORK of (tree * tree);

For SML/NJ I used a full binary tree of depth 22;
for MLton  I used a full binary tree of depth 25.

SML/NJ MLton
 0.899 0.244	boring old plain list
 5.481 1.244	build a "raum" using raums
 8.186 1.380	build a raum then convert it to a list
12.581 4.449	build a "dlist" using dlists
16.209 5.096    build a dlist then convert it to a list

Times were measured on an Intel Core 2 Duo Mac running
Mac OS X 10.6.4, SSML/NJ v110.70 [built: Wed Jun 17 16:24:00 2009]
MLton MLTONVERSION (built Mon Jun 15 11:10:01 CDT 2009 on fenrir.uchicago.edu)

Building a list using dlists is 16 (SML/NJ) or 20 (MLton) times
slower than using a plain list.

Caveat:  because raums handle reverse in O(1) time as well as
concatenation, for a fair comparison I made dlists do the same,
so
	type 'x dlist = bool -> 'x list -> 'x list

	fun fromList xs flag tail =
	    if flag then xs @ tail else List.revAppend(xs, tail)


fun list_flatten t = 
    let fun flat (LEAF x) ys = x :: ys
          | flat (FORK(a,b)) ys = flat a (flat b ys)
     in flat t []
    end

fun raum_flat (LEAF x)    = Raum.singleton x
  | raum_flat (FORK(a,b)) = Raum.cat (raum_flat a) (raum_flat b)

fun raum_flatten t = Raum.toList (raum_flat t)

fun dlist_flat (LEAF x)    = DList.singleton x
  | dlist_flat (FORK(a,b)) = DList.cat (dlist_flat a) (dlist_flat b)

fun dlist_flatten t = DList.toList (dlist_flat t)

> To close the circle: I understand that difference lists in
> Prolog might have been a declarative translation of
> in-place updating in Lisp lists:-)

It seems unlikely.  Prolog was born as a grammar formalism
(metamorphosis grammars) and the idea of a non-terminal as
a relation between a (starting point, end point) pair owes
nothing to Lisp.

I mean, do you call parser combinators in Haskell "a
declarative translation of in-place updating in Lisp lists"?
>