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

[doug.auclair at logicaltypes.com]

Dear Ralph, thank you for responding; you wrote:

>> vs:   ``b+`w* which is shorter and clearer than either example
>                        ^^^^^^^
>Sorry, I can't agree with you on that point!

Heh!  So, I suppose you are not a combinatory ornithologist, then.
(cf. /To Mock a Mockingbird/, Smullyan)

>> There.
>Sure, it can be done and it may be done.  But at the moment we're too
>busy to give proper consideration to the idea!

But I do appreciate you taking time to respond to my posts. Thank you.

[...]

>I wonder whether adding operator sections a la Haskell might not achieve
>90% of what you want for 1% of the syntax?  We've certainly considered
>the idea in the past.

Interesting idea, that, and there are some places that I could (and do)
use sections (my combinator library gives that to me for free), but
actually I find myself composing functions with functions more often
than reducing the HO term to a section with some ground arguments ...

>> >unfold(P, A0) = ( if P(A0, X, A) then [X | unfold(P, A)] else [] ).
>> Sweet!  So is this function going into module list?
>I'm not convinced I've got the interface quite right.  Would you care to
>provide some examples of how it would be useful to you?

K. Given than my version of unfold is different
(http://www.cotilliongroup.com/man/list-utils-man.html#pred-unfold)

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).

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).

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)

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)

Sincerely,
Doug Auclair

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------