CODEWITHSUNDEEP
pattern-matchingrascal
Rodrigo Bonifacio
Rodrigo Bonifacio

Reputation: 262

List pattern matching in Rascal

In Haskell (and quite similar in Prolog / Erlang), we can define a length function over lists as: 

length [] = 0
length (x:xs) = 1 + length xs

In Rascal, I was able to create a definition like this using:

int length([]) = 0;
int length([x,xs*]) = 1 + length(xs);

The "*" disappears on the right hand side of the recursive case of length. I know that it might exist a reason for that, but I could not figure it out. Is there a better approach for defining recursive functions over lists using pattern matching in Rascal?

Upvotes: 1

Views: 428

Answers (1)

Paul Klint
Paul Klint

Reputation: 1406

There are various aspects of your question that I want to address:

  1. Your Rascal version looks fine. Rascal has more general list pattern matching than Haskell: more than one variable can match more than one element, so each "list variable" in a list pattern has to be tagged with a * to indicate just that.

  2. We are in a transitional phase where we are moving from the postfix * to a prefix *. So the second rule can be (and in the future should be) written as:

    int length([x,*xs]) = 1 + length(xs);

  3. You may want to explore the reducer expression that can be used to write various fold-like functions:

    int length(list[int] xs) = ( 0 | it + 1 | x <- xs );

    It consists of three parts:

    • initial value (0); the built-in variable it is set to this initial value.
    • an expression that accumulates results and that may use it, here: it + 1. It has as effect it = it + 1.
    • an enumeration that produces the list elements.
  4. More general (than simply head/tail) pattern matching examples are these:
    • [*x, a] : match the element at the end of a list
    • [*x, *x] : split the list in two equal halves
    • [*a, x, *b, x, *c] : find two duplicate elements
  5. a bound list variable binds a full list which you can use like any other variable which points to a list, but if you want to splice it in on the right-hand side of the rule, you get a more symmetrical view: int length([x,*xs]) = 1 + length([*xs]);, of course this also generalizes, so this is also possible: [*xs, 2, *xs] where the * operator simply removes one layer of list nesting.

Upvotes: 2

Related Questions