[Haskell-cafe] Reference for technique wanted

[wren ng thornton]

On 10/31/10 10:26 PM, Richard O'Keefe wrote:
> On 1/11/2010, at 2:02 PM, wren ng thornton wrote:
>> (Though I find it curious that you think the logic version is so different...)
>
> The logic programming version
>    uses a SINGLE data structure for lists and differences, so that
>    + "converting" from the difference representation to the "plain" representation
>      involves no more than binding a single (logic) variable
>    + does not involve ANY overheads compared with building a list directly
>    + can easily be traversed while still under construction,
 >    - can only be used once, after which the "hole" has *gone*.

Sure, but all of these come from the differences in how functional 
languages and logic languages define their notions of "variable".

In logic programming you're allowed to play with open terms, so the 
ability to move around difference lists before they're "complete" is the 
same as being able to manipulate any other open term. Whereas in 
functional languages you (typically) are not allowed to have open terms, 
and terms with variables in them must be guarded by lambdas which 
prohibit you looking underneath them. One benefit of lambdas is that 
they lift the names of unknown substructure up to the top of an 
expression; the difflist(xs,hole) structure is just there to give that 
same lifting of names, since otherwise we wouldn't have any way of 
knowing that xs is unground nor how to make it (more) ground[1]. The 
various other differences regarding linear usage just come down to the 
fact that difflist(xs,hole) is a closure, not a function. But there's 
nothing to prevent functionalizing it, if the logic language provides a 
mechanism for generating fresh variables.

When I look at difference lists in functional languages I see them in 
the same light: as a mechanism for manipulating open terms. The details 
of what manipulations are allowed is different (mostly because of 
function vs closure), but that's to be expected given the paradigm 
differences. But then I take the algorithmic idea of using open terms 
for fast concatenation as primary and the implementation details of what 
"open terms" are as secondary.


[1] Assuming a pure logic language, which Prolog is not.

-- 
Live well,
~wren