- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Wolfgang Lux <lux_at_helios.uni-muenster.de>

Date: Thu, 21 Sep 2000 13:30:15 +0200

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

Date: Thu, 21 Sep 2000 13:30:15 +0200

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/curryReceived on Mo Sep 25 2000 - 08:43:16 CEST

*
This archive was generated by hypermail 2.3.0
: Do Jun 20 2024 - 07:15:06 CEST
*