[m-dev.] HO List args: fold and unfold

[Ralph Becket]

doug.auclair at logicaltypes.com, Tuesday, 14 March 2006:
> EX1:
> 
> I've used it to generate power-sets (used so interestingly in Ciao
> Prolog to represent dependency graphs):
> 
> power_set(List, AllSubsets) :-
>   setof(Perm, permute(List, Perm), Perms),
>   replace(phi(L0, L1, unfold(psi(X, X = []), i, lambda([_|T], T), L0, L1)),
>           Perms, [], Bag).
> 
> where replace/4 is simply map/3 from ZF set theory.  The phi/3 term
> is a lambda/2-equivalent, giving the user a handle to the output,
> psi/2 is an HO boolean and i/0 is the i combinator (\x.x, or id from
> module std_util).

I have to say, I find that definition of power_set very hard to
understand, even given your explanation.  Is it any more efficient than

power_set(Xs) = solutions(subset(Xs)).

subset([],       []      ).
subset([X | Xs], [X | Ys]) :- subset(Xs, Ys).
subset([_ | Xs], Ys      ) :- subset(Xs, Ys).

It doesn't seem to be any longer.

> EX2:
> 
> Since Mercury already has ../2, this example shows I implemented
> it for Quintus Prolog:
> 
> '..'(CoutList, X, Y) :- unfold(psi(A, A > Y), i, "`+1", X, CountList).

versus

	X .. Y = ( if X =< Y then [X | (X + 1) .. Y] else [] ).

Again, I find the unfold version quite hard to understand.

> where the binary-prefix back-tick is the application operator for
> Combinatory Logic (see http://homepages.cwi.nl/~tromp/cl/lazy-k.html).
> This example could benefit from sections:
> 
> ... unfold((>Y), i, (+1), X, CountList).
> 
> EX3:
> 
> I've also used unfold to, well, unfold an integer to a list of 
> (usually binary) digits (but I've also used other bases, such as 10):
> 
> unfold(psi(X, X =< 0), lambda(Y, Y /\ 1), lambda(Z, Z >> 1), Num, Bits)

versus

	map(func(Num, I) = (X /\ (1 << I)) >> I, 0..31)

> It was this example, while writing a one-dimensional cellular automata
> engine that I became stymied on series/3.  This example here could
> also be entirely rewritten with sections:
> 
> unfold((=< 0), (/\ 1), (>> 1), Num, Bits)

Okay, that's shorter.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------