CODEWITHSUNDEEP
haskelldesign-patterns
Mark Karpov
Mark Karpov

Reputation: 7599

One interesting pattern

I'm solving 99 Haskell Probems. I've successfully solved problem No. 21, and when I opened solution page, the following solution was proposed:

Insert an element at a given position into a list.

insertAt :: a -> [a] -> Int -> [a]
insertAt x xs (n+1) = let (ys,zs) = split xs n in ys++x:zs

I found pattern (n + 1) interesting, because it seems to be an elegant way to convert 1-based argument of insertAt into 0-based argument of split (it's function from previous exercises, essentially the same as splitAt). The problem is that GHC did not find this pattern that elegant, in fact it says:

Parse error in pattern: n + 1

I don't think that the guy who wrote the answer was dumb and I would like to know if this kind of patterns is legal in Haskell, and if it is, how to fix the solution.

Upvotes: 6

Views: 187

Answers (3)

Jonathan Cast
Jonathan Cast

Reputation: 4635

The problem with n+k patterns goes back to a design decision in Haskell, to distinguish between constructors and variables in patterns by the first character of their names. If you go back to ML, a common function definition might look like (using Haskell syntax)

map f nil = nil
map f (x:xn) = f x : map f xn

As you can see, syntactically there's no difference between f and nil on the LHS of the first line, but they have different roles; f is a variable that needs to be bound to the first argument to map while nil is a constructor that needs to be matched against the second. Now, ML makes this distinction by looking each variable up in the surrounding scope, and assuming names are variables when the look-up fails. So nil is recognized as a constructor when the lookup fails. But consider what happens when there's a typo in the pattern:

map f niil = nil

(two is in niil). niil isn't a constructor name in scope, so it gets treated as a variable, and the definition is silently interpreted incorrectly.

Haskell's solution to this problem is to require constructor names to begin with uppercase letters, and variable names to begin with lowercase letters. And, for infix operators / constructors, constructor names must begin with : while operator names may not begin with :. This also helps distinguish between deconstructing bindings:

x:xn = ...

is clearly a deconstructing binding, because you can't define a function named :, while

n - m = ...

is clearly a function definition, because - can't be a constructor name.

But allowing n+k patterns, like n+1, means that + is both a valid function name, and something that works like a constructor in patterns. Now

n + 1 = ...

is ambiguous again; it could be part of the definition of a function named (+), or it could be a deconstructing pattern match definition of n. In Haskell 98, this ambiguity was solved by declaring

n + 1 = ...

a function definition, and

(n + 1) = ...

a deconstructing binding. But that obviously was never a satisfactory solution.

Upvotes: 6

rampion
rampion

Reputation: 89093

Note that you can now use view patterns instead of n+1.

For example:

{-# LANGUAGE ViewPatterns #-}
module Temp where
import Data.List (splitAt)

split :: [a] -> Int -> ([a], [a])
split = flip splitAt

insertAt :: a -> [a] -> Int -> [a] 
insertAt x xs (subtract 1 -> n) = let (ys,zs) = split xs n in ys++x:zs

Upvotes: 1

C. Quilley
C. Quilley

Reputation: 1059

I believe it has been removed from the language, and so was likely around when the author of 99 Haskell Problems wrote that solution, but it is no longer in Haskell.

Upvotes: 12

Related Questions