Search code examples
pattern-matchingrascal

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?

Solution

  • 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.