Proposal: Change semantics of pattern matching

From: Wolfgang Lux <>
Date: Thu, 21 Sep 2000 13:30:15 +0200


I would like to propose a language change for Curry.

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

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?

[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:
curry mailing list
Received on Mon Sep 25 2000 - 08:43:16 CEST

This archive was generated by hypermail 2.3.0 : Wed Sep 18 2019 - 07:15:04 CEST