CODEWITHSUNDEEP
listhaskellpattern-matching
Slow Harry
Slow Harry

Reputation: 1897

How does pattern matching works with lists

I just start learning haskell and pattern matching. I just don't understand how it implemented, is the [] and (x:_) evaluates to the different type and the function implementations for this pattern recognized because of polymorphism, or I just wrong and there is another technique used. 

head' :: [a] -> a  
head' [] = error "Can't call head on an empty list, dummy!"  
head' (x:_) = x

Or lets consider this pattern matching function:

tell :: (Show a) => [a] -> String  
tell [] = "The list is empty"  
tell (x:[]) = "The list has one element: " ++ show x  
tell (x:y:[]) = "The list has two elements: " ++ show x ++ " and " ++ show y  
tell (x:y:_) = "This list is long. The first two elements are: " ++ show x ++ " and " ++ show y

I think I wrong because each list with different number of elements can't have deferent type. Can you explain me how haskell knows which pattern is correct for some function implementation? I understand how it works logically but not deep. Explain it to me please.

Upvotes: 2

Views: 409

Answers (2)

Stephen Diehl
Stephen Diehl

Reputation: 8409

There's a bit of a level of indirection between the syntax in Haskell and the implementation at runtime. The list syntax that you see in most source is actually a bit of sugar for what is actually a fairly regular data type. The following two lines are equivalent:

data List a = Nil | Cons a (List a)
data [a] = [] | a : [a]  -- pseudocode

So when you type in [a,b,c] this translates into the internal representation as (a : (b : (c : []))).

The pattern matching you'll see at the top level bindings in are also a bit of syntactic sugar ( sans some minor details ) for case statements which deconstruct the data types onto the right hand side of the case of the pattern match. The _ symbol is a builtin for the wildcard pattern which matches any expression ( so long as the pattern is well-typed ) but does add a variable to the RHS scope.

head :: [a] -> a
head x = case x of
  (a : _) -> a

I think I wrong because each list with different number of elements can't have deferent type. Can you explain me how haskell knows which pattern is correct for some function implementation?

So to answer your question [] and (x:_) are both of the same type (namely [a] or List a in our example above). The list datatype is also recursive so all recursive combinations of Cons'ing values of type a have the same type, namely [a].

When the compiler typechecks the case statement it runs along each of the LHS columns and ensures that all the types are equivalent or can be made equivalent using a process called unification. The same is done on the right hand side of the cases.

Haskell "knows" which pattern is correct by trying each branch sequentially and unpacking the matched value to see if it has the same number of cons elements as the pattern and then proceeding to the branch which does, or failing with a pattern match error if none match. The same process is done for any pattern matching on data types, not just lists.

Upvotes: 6

Itay Maman
Itay Maman

Reputation: 30723

There are two separate sets of checks:

in compile time (before the program is run) the compiler simply checks that the types of the cases conform to the function's signature and that the calls to the function conform to the function's signature.

In runtime, when we have access to the actual input, a similar, but different, set of checks is executed: these checks take the * actual* input (not its type) at hand and determine which of the cases matches it.

So, to answer your question: the decision is made in compile time where we have not only the type but also the actual value.

Upvotes: 1

Related Questions