Re: permute example

From: Sergio Antoy <antoy_at_cs.pdx.edu>
Date: Thu, 3 Jul 1997 21:39:01 -0700

> > Now the example, a program to compute a permutation of a list.
> >
> > [] ++ x = x
> > (x:xs) ++ y = x:xs++y
> > permute [] = []
> > permute (x:xs) | u++v == permute xs = u++[x]++v
>
>
> I've followed the debate between Sergio and Phil on this example but I'm
> still bemused by it all. One can write permute in lots of different ways and
> one can use techniques such as lazy evaluation to efficiently produce one
> permutation. All these solutions look pretty much equally attractive to me.

Then I am not sure what was your point in repeatedly asking for
examples.

> So please can someone say exactly what it is about this example which makes
> it interesting?

It is helpful to discuss similarities and differences of Curry and
Haskell. If you could provide the Escher version we could extend
the comparison and address your initial question about narrowing.

> Also exactly what light does it throw on the narrowing vs. rewriting debate?

We know, more or less, that narrowing has a certain cost in terms
of conceptual complexity. This cost is modest, since as Michael
points out, the operational semantics are described in less than a
page, but the cost is still higher than rewriting. The cost of
computing with narrowing is probably higher than rewriting, too,
though I would guess marginally so. You asked, rightly so,
whether there is any advantage in paying these costs and asked for
convincing examples. I do not know whether this example is
convincing and/or significant until we compare it with Escher. I
argued, and Phil agreed, that the Curry program is simpler (I
would say more expressive, abstract, and declarative) of the
Haskell program. No big deal, and we agreed that there are more
important questions to address. I think that at this point I
could be more persuasive if I could compare it rather than arguing
what is interesting about it or what light does it throw on the
debate. This example in isolation has no value. It is only the
comparison between different solutions of the same problem that
may help us to make some progress and resolve whether we want to
keep narrowing in the language or throw it away. Was not this
your initial question?

Sergio
Received on Fr Jul 04 1997 - 08:41:00 CEST