Re: Narrowing vs. rewriting

From: Philip Wadler <wadler_at_research.bell-labs.com>
Date: Thu, 03 Jul 1997 14:52:51 -0400

Hi Sergio,

I agree with you that your Curry program is more declarative than
my Haskell, but so what? I think you've missed my point. No example
that reduces four lines to two will be convincing, unless it scales up
to reduce forty lines to twenty, and four thousand to two thousand.
Your example seems to me too specialised to scale well. I want killer
apps, not toy apps.

A toy app can be a killer app, if it scales. The classic canoe and
cannibal problem in Prolog is typical of a wide range of search
problems, for which Prolog is a real winner. The key is to
characterise interesting families of problems at which Curry excels.

Cheers, -- P

Some more specific points:

> 1. Permute does not return a permution. Its return value must be
> processed in its entirety to use a permutation.

Not with lazy evaluation! For an example, see the eight-queens
problem in the Bird and Wadler textbook.

> 4. The efficiency depends on the implementation, but it is easy
> to argue that there is a loss of efficiency in creating the
> list of permutations and later garbage-collecting it.

Well, the work has to happen one way or the other. I'd be surprised
if the best Curry implementation could beat the best Haskell
implementation for this example.

> 5. The fact that the order in which permutations are generated
> is explict is not an advantage, but lack of abstraction and
> declarativeness. If the order were important, the program
> should not have been non-deterministic.

It depends. Consider the following sorting program: look at all
permutations of the input and pick one in ascending order. It's highly
declarative, but too inefficient for most uses. A highly declarative
approach is an advantage only where it is efficient enough, and easy
to tell that it is efficient enough.
Received on Do Jul 03 1997 - 21:54:00 CEST