3 Pattern Issues

3.1 Irrefutable Patterns

Issues: Haskell provides a notation that can be used to explicitly mark a pattern match as irrefutable, i.e. even if the pattern doesn't match a value, the evaluation will proceed as if it had matched. Here is a contrived but illustrative example of an irrefutable pattern:

  dup xxs@(~(x:xs))
    | xxs == [] = []
    | otherwise = x:xxs

In dup the pattern x:xs will match the empty list because it has been marked as irrefutable. Normally this pattern would not match the empty list since it represents a list with a head x and a tail xs.

Solution: Clean doesn't have any equivalent notation, however we note that Clean does support ``let'' expressions which, in the Haskell'98 report, are defined using irrefutable patterns. The implicit irrefutable nature of let expressions is shown in the code below which is valid under both languages (but for the syntax of ``if''):

  dup' xxs = let (x:xs) = xxs in
    if xxs == [] then [] else x:xxs

The ``let'' expression is lazy: it will only evaluate the pattern if it needs to. This describes exactly the semantics of irrefutable patterns which motivates the following translation.

References: See trIrrPat in TrPat.lhs.

Example Translation:

Original Source	After this Translation
dup xxs@(~(x:xs)) | xxs == [] = [] | otherwise = x:xxs	dup xxs=:v | xxs == [] = let (x:xs) = v in [] | otherwise = let (x:xs) = v in x:xxs

General Translation

$${\cal T}_{exp}\llbracket\texttt{case $e_0$\ of $p$\ -> $e_1$}\rrbracket = \left[\hspace{-1.7mm}\left[ \begin{array}{ll} \texttt{case $e... ...n$\ = $x_n$\ in $e_1$} \end{array}\right]\hspace{-1.7mm}\right]$$

Where $p_0$ to $p_n$ are all the irrefutable patterns in $p$ and $x_0$ to $x_n$ are unique variable names that do not occur free in $e_1$ . $p'$ is like $p$ except that sub-patterns $p_0$ to $p_n$ have been replaced with the variables $x_0$ to $x_n$ .

3.2 Successor Patterns

Issues: Here is an example of a successor pattern used in the recursive definition of the function take n xs which returns the first n items of the list xs:

  take (n+1) (x:xs) = x : take n xs

Here n+1 is the successor pattern. Since Clean doesn't support successor patterns we will have to derive a translation. To do this we consider the precise semantics of successor patterns as stated in the Haskell'98 report.

``Matching an n+k pattern (where $n$ is a variable and $k$ is a positive integer literal) against a value $v$ [sic] succeeds if $x \geq k$ , resulting in the binding of $n$ to $x - k$ , and fails otherwise.'' - Haskell'98 Report[#!Hs98!#]

Solution: Firstly we note that the pattern match only succeeds if the value being matched $x$ is greater than or equal to the integer constant $k$ . This can be achieved by guarding the pattern match with the appropriate condition (i.e. $x \geq k$ ). Secondly the successor variable $n$ must be bound to the value being matched minus the $k$ . This can be achieved trivially using a ``let'' expression.

Example Translation

Original Source	After this Translation
take (n+1) (x:xs) = x : take n xs	take v (x:xs) | (v >= 1) = let n = v - 1 in x : take n xs

General Translation

$${\cal T}_{exp}\llbracket\texttt{case $v$\ of $p$\ -> $e$}\rrbracket = \left[\hspace{-1.7mm}\left[ \begin{array}{ll} \texttt{case $v... ... $x_n$\ - $k_n$\ in e} \end{array}\right]\hspace{-1.7mm}\right]$$

Where $p'$ is like $p$ except that all successor patterns in $p$ have been replaced by the unique variables $x_0$ to $x_n$ (which do no occur free in $e$ ), and $n_0$ to $n_n$ and $k_0$ to $k_n$ are the corresponding successor variables and constants respectively.

3.3 As-Patterns

Issues: As-patterns have a slightly different syntax in Clean. In addition, Clean doesn't allow as-patterns in pattern bindings. The latter issue is dealt with in the next section.

References: See HsPat instance of Pretty in ClPretty.lhs.

Example Translation:

Original Source	After this Translation
dup xxs@(x:xs) = x:xxs	dup xxs=:(x:xs) = x:xxs

General Translation:

$${\cal T}_{pat}\llbracket\texttt{$n$@$p$}\rrbracket = \llbracket\texttt{$n$=:$p$}\rrbracket$$

3.4 Pattern Bindings

Issues: There are several issues regarding pattern bindings:

• Clean's pattern bindings can't contain as-patterns.
• In Clean, top-level pattern bindings are not allowed.
• In Clean, pattern bindings can't be guarded nor contain a local where clause on the right-hand-side.
• In Clean a pattern binding must not contain any 0-arity data constructors.
• In Clean, pattern bindings aren't allowed a type-signature.

Example Translation:

Original Source	After this Translation
fib :: [Int] fib@(1:tfib) = 1 : 1 : [a + b | (a, b) <- zip fib tfib]	x = 1 : 1 : [a + b | (a, b) <- zip fib tfib] fib :: [Int] fib = case x of fib=:(1:tfib) -> fib tfib = case x of fib=:(1:tfib) -> tfib

General Translation:

$${\cal T}_{decl}\llbracket\texttt{$p$\ = $e$}\rrbracket = \left[\hspace{-1.7mm}\left[ \begin{array}{ll} \texttt{$x$\ = ... ...$x$\ of $p$\ -> $x_n$} \end{array}\right]\hspace{-1.7mm}\right]$$

Where $x_0$ to $x_n$ are all the variables present in the pattern $p$ . $x$ is a new variable that does not clash with any other names in scope.

3.5 Prefixed Operators in Patterns

Issues: Under both Haskell and Clean constructors are just functions and so infix constructors can be used in a prefix form by wrapping them in parentheses. However, whereas Haskell extends this notation to patterns (as illustrated by the following example), Clean does not:

  head ((:) x y) = x           -- Valid in Haskell but not Clean

Example Translation:

Original Source	After this Translation
head ((:) x y) = x	head (x : y) = x

General Translation:

$${\cal T}_{pat}\llbracket\texttt{($op$) $e_0$\ $e_1$}\rrbracket = \llbracket\texttt{($e_0$\ $op$\ $e_1$)}\rrbracket$$

3.6 Backticked Constructors in Patterns

Issues: Clean doesn't allow constructors to be enclosed in backticks to signify infix usage as in Haskell.

Solution: For each binary constructor, a infix macro is defined which can be used to replace the backticked usage of the constructor in any given pattern.

Example Translation:

Original Source	After this Translation
infixr 5 `Cons` data List a = Nil | Cons a (List a) head (x `Cons` xs) = x	data List a = Nil | Cons a (List a) (I_Cons) infixr 5 (I_Cons) :== Cons head (x I_Cons xs) = x

General Translation

$${\cal T}_{decl}\llbracket\texttt{data $t$\ $xs$\ = $cs$}\rrbracket{s} = \left[\hspace{-1.7mm}\left[ \begin{array}{ll} \texttt{data $t... ...tt{($Ic_n$) :== $c_n$} \end{array}\right]\hspace{-1.7mm}\right]$$

Where $c_0$ to $c_n$ are the binary constructors in $cs$ and $assoc_0$ /$prec_0$ to $assoc_n$ /$prec_n$ are the associativity and precedence of these constructors as stated in the symbol table $s$ . The name $I$ is some unique prefix which ensures that the macro doesn't clash with any other names in scope.

3.7 Numeric Literals in Patterns

Issues: Numeric literals in Haskell are overloaded, meaning, for instance, that the literal 0 could represent an Int, Integer, Float or Double (or any other member of the Num class). In Clean the literal 0 is an Int and 0.0 is a Real. The following definition, valid in both Haskell and Clean, of the power function highlights the incompatibility:

  power x 0 = 1
  power x n = x * power x (n-1)

In Haskell, power's type is:

  power :: (Num a, Num b) => a -> b -> a

But in Clean its type is:

  power :: Int Int -> Int

Solution: Integer literals in expressions can be overloaded by passing them to the function Prelude.fromInteger. However, integer literals in patterns need to be moved accross into a guard before they can be passed to the overloading function. Since numeric literals are moved into a guard, so too must negative numeric literals (i.e. those preceeded with a unary minus).

Example Translation:

Original Source	After this Translation
power x 0 = 1 power x n = x * power x (n-1)	power x v | v == (Prelude.fromInteger 0) = 1 power x n = x * power x (n-1)
f (-1) = 1 f x = x	f v | v == (Prelude.negate (Prelude.fromInteger 0)) = 1 f x = x

General Translation:

$${\cal T}_{exp}\llbracket\texttt{case $e_0$\ of $p$\ -> $e_1$}\rrbracket = \left[\hspace{-1.7mm}\left[ \begin{array}{ll} \texttt{case $e... ...teger $n_n$\ -> $e_1$} \end{array}\right]\hspace{-1.7mm}\right]$$

Where $n_0$ to $n_n$ are all the integer literals in $p$ and $v_0$ to $v_n$ are unique variable names that do not occur free in $e_1$ . $p'$ is like $p$ except that its integer literals $n_0$ to $n_n$ have been replaced with the variables $v_0$ to $v_n$ . The variable fromInteger points to the fromInteger member of the Prelude's Num class.