Hello,
I would like to propose a language change for Curry.
Proposal:
=========
In a rigid function, only the first matching rule should be evaluated,
where rules are evaluated from top to bottom.
In order to write a rigid function with the current semantics, i.e.,
where all rules with matching left hand sides are non-deterministically
applied, the function must be annotated explicitly with
eval f nondet
Rationale:
==========
IMHO, Curry's most annoying "feature" is that all patterns on the left
hand side of a function's rules must be non-overlapping in order to
write a deterministic (rigid) function. This is annoying (and
error-prone, leading to unwanted non-determinism) in many cases
where you want to filter out only a few cases from a data structure.
Consider for instance an implementation of red-black trees (this one
comes from Chris Okasaki's excellent book [1]). The function which
re-balances a tree after an insertion has to check for paths with
colour Black-Red-Red in the tree and rotate such a tree. In Haskell
this function can be defined as follows:
data Color = R | B
data RBSet a = E | T Color (RBSet a) a (RBSet a)
balance :: Color -> RBSet a -> a -> RBSet a -> RBSet a
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b = T color a x b
If I want to translate this into a *deterministic* function in Curry,
I would have to repeat the first two rules for all possible patterns
where the argument d is not a T-node whose left or right is a T-node
with colour R. The same is true for argument a in the third and fourth
rule. Also I have to duplicate the first rule so that it applies only
to trees where the subtree c is not a T-node whose colour is R and
similarly for the other rules. Finally, instead of the last rule I
would have to enumerate all other cases not covered yet.
As this example shows, in many cases the Haskell style pattern matching
gives clearer code than in Curry. However, there are useful examples
where one wants to have a non-deterministic evaluation of a rigid
function, e.g. the non-deterministic insert function
insert x [] = []
insert x (y:ys) = x : y : ys
insert x (y:ys) = y : insert x ys
In most cases I would expect the programmer to be interested in a
deterministic evaluation of (rigid) functions, therefore I suggest to
require an annotation in the case where non-deterministic evaluation
is really intended.
Note that the proposal applies to rigid functions only. Flexible
functions should always try all their matching rules just as currently
specified in the report.
Any comments?
Wolfgang
[1] Chris Okasaki, Purely Functional Data Structures, Cambridge
University Press 1998
--
Wolfgang Lux Phone: +49-251-83-38263
Institut fuer Wirtschaftinformatik FAX: +49-251-83-38259
Universitaet Muenster Email: wlux_at_uni-muenster.de
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Mo Sep 25 2000 - 08:43:16 CEST