Re: Smap: Collecting small programs

From: David Powers <>
Date: Fri, 31 Oct 2014 02:35:47 +0000

Thanks very much for this Michael,

On 31 Oct 2014, at 3:28 am, Michael Hanus <<>> wrote:

Hi David,

this is only a partial answer to all the issues you pointed out.

3/4. There are issues relating to free variables and unification models
that prevent translation from Prolog.

In principle, any *logic program* can be translated to Curry
in a straightforward manner. However, for Prolog with all its
non-logic features, it is different.

Even adding in ensureNotFree doesn’t help as all disjunctions can suspend…
I do have a working (sicstus/swipl) Prolog version of this!

Just a comment: ensureNotFree only suspends computations but can't
be used as a case distinction. Hence, you can't do a case distinction
on difference lists (similar to logic programming) so that difference
lists should only be used for producing results. For instance,
the reverse operation takes a standard list and produces a difference

revD :: [a] -> DList a
revD [] = (m#m) where m free
revD (x:xs) = appD (revD xs) (x:m # m) where m free

with difference list concatenation defined by

appD (a#b) (b#n) = (a#n)

In a similar way, you can also define quicksort with difference lists.

This is the nub of the problem. And why I zapped the differences to [].
The problem I was having came from unification with DLists in where tuples.
And yes I see that ensureNotFree doesn’t make sense in a Curry guard.
But in Prolog the blocking constructs do act as guards (delaying not failing).

My Prolog sorts are all cut/not/if/assert-free pure logic programs.
Some (notably permsort) use blocking and/or transformation (to quadratic).

I have tried two-way and three-way quicksorts in your Curry Dlist style:
viz. using the explicit call to appD to do the appending;
with fromD mapping back to a list before recursing quicksort...

This functional/generation style works but I’d still like to use a
more efficient logical/unification style (involving where patterns).


Best regards,

curry mailing list

curry mailing list
Received on Fr Okt 31 2014 - 15:37:12 CET

This archive was generated by hypermail 2.3.0 : So Sep 20 2020 - 07:15:04 CEST