Is "List" specially handled in Haskell's pattern matching?

19
votes

I am a newbie in Haskell and hope this question is not silly.

I have seen so much example that when I am having a list, I am able to match and bind "composition element" of the list to individual variable:

listSizeDesc :: [a] -> String
listSizeDesc [] = "Emtpy"
listSizeDesc (x:xs) = "Something inside"

However, I tried to do something like:

foo :: Int -> String
foo 0 = "Zero"
foo (n - 1) = "next number is " ++ show n

It doesn't work.

It seems to me that both (n-1) and (x:xs) describe how the argument is "created" and bind the "component" to an argument. Is the way List matched specially designed for ease of recursion? Coz it seems to me this matching / argument-binding logic doesn't apply to other functions except (:).

5
haskellpattern-matching
Definitely not a stupid question. This is my understanding as a fellow newbie: lists are not "special". Pattern matching works with : because : is a type constructor for lists. It works type constructors but not for general functions. How this work is explained quite well here on WikiBooks – Paolo Falabella
There is no such thing as a silly question, as long as it is well asked. – hugomg
@PaoloFalabella: Just to avoid confusion: The proper term here is “data constructor”. A “type constructor” would be, for example, Maybe. – Joachim Breitner
@JoachimBreitner thanks. I can't edit my comment and can only upvote your comment to try and make it more visible. – Paolo Falabella

5 Answers

18
votes

The problem you're encountering is that pattern matching only works with data constructors. A data constructor is in essence very simple; it just takes data values and groups them together in some sort of structure. For example, data Foo = Bar a b simply takes two pieces of data and groups them together under the Foo label. The (:) function you use in your first example is more than just a function; it's a data constructor. It constructs a new list by adding the left argument to the right argument.

Now, pattern matching is merely doing the opposite of this process. It deconstructs a datatype. When you write (x:xs) in your pattern, you're extracting the two pieces of data that the constructor originally stitched together. So all pattern matching does is extract the data that a constructor previously stitched together.

There is one exception: n+k patterns. In Haskell98, you were allowed to use patterns of the form (n+k). This was sort of an arbitrary exception and it was recently removed. If you'd like, you can still use it if you include the NPlusKPatterns language pragma.

14
votes

The list type is "Sum type" with a constructor, something like:

data List a =
     cons a (List a)
   | nil

You first example is a pattern match on a datatype (with syntactic sugar for :).

Your second example is a pattern match on integers, which are not a datatypye definition. On integer, there is no pattern using your syntax. You may write your example with:

foo :: Int -> String
foo 0 = "Zero"
foo n = "next number is " ++ show (n+1)

On a side note if you encode integers with datatypes like:

data Nat = Zero | Succ Nat deriving (Show)

Then you can use your pattern match as you wanted initially.

foo :: Nat -> String
foo Zero = "Zero"
foo n@Succ(p) = "next number is " ++ show(n)

Here the pattern Succ(p) plays the role of n-1.

5
votes

There are already some great answers, so I won't bother with the main question. This is not the best use of it, but what you were trying to do can sort of be accomplished with view patterns.

{-# LANGUAGE ViewPatterns #-}

foo :: Int -> String
foo 0 = "Zero"
foo (pred -> n) = "Next number is " ++ show n
4
votes

Just to put it as simply as possible:
A list literally is a series of concatenations. A number could be equivalent to the result of an arithmetic operation. The difference is that the result of a : b is simply a : b.

In more detail:

Lists and (:) aren't a special case at all. Let's make our own:

data List2 a = End               -- equivalent of "[]"
             | Cat a (List2 a)   -- non-infix ":"
  deriving (Show)

So [1, 2, 3], which == (1 : (2 : (3 : []))), would be written as: 

a = Cat 1 (Cat 2 (Cat 3 End))

Just like pattern-matching (x:xs), we can pattern-match List2:

newTail End = End
newTail (Cat _ x) = x

Test it:

*Main> tail [1,2,3]
[2,3]
*Main> newTail a
Cat 2 (Cat 3 End)
3
votes
moo :: Int -> String
moo 0 = "Zero"
moo n = "next number is " ++ show (n + 1)

n - 1 is an ordinary function application, not a pattern. An exception used to be made for + and this might be the model you are going by. You can write something like 

goo :: Int -> String
goo 0 = "Zero"
goo (n+1)  = "previous number is " ++ show n

in hugs ; you still can do this with the ghc, if you include the pragma 

{-#LANGUAGE NPlusKPatterns#-}