How does haskell break a list in a pattern for head function

user_8243326 0
Viewed 266

While learning haskell I couldn't understand how haskell was automatically able to match a pattern where the head of a list is extracted.

head' :: [a] -> a  
head' [] = error "Can't find head in an Empty list!" 
-- How does haskell break the list into x(first) and xs(rest)? 
head' (x:xs) = x

I had read that [1,2,3] is syntactical sugar for 1:2:3:[]. So : is a function that takes any argument and add to the right hand argument? And how does the list explode backward into two variables head and rest? [1,2,3] --> (x:xs)??

colon_operator :: a -> [a]
-- not sure how the function would look

Sorry if I couldn't explain my question concisely, I am not that great at haskell.

pattern-matching haskell
2 Answers

Caveat lector: this is a zeroth approximation, and wrong in many ways, but at least it's a zeroth approximation!

Using pseudocode, when you call [] or :, a new data structure is created. Here's how you might write the structure in an imperative language:

structure {
    int constructor
    ptr head
    ptr tail
} list

When you write empty = [], that allocates a new list, and populates it this way:

empty = alloc(list)
empty.constructor = 0 // 0 means we used [] to construct this

The head and tail pointers are left uninitialized, because they aren't used. When you write not_empty = 3 : [4], that allocates a new list, and populates it this way:

// three is a pointer to 3
// four is a pointer to [4]
not_empty = alloc(list)
not_empty.constructor = 1 // 1 means we used : to construct this
not_empty.head = three
not_empty.tail = four

Now, when you pattern match on a list, that corresponds to checking the constructor field. So if you write, say:

case not_empty of
    [] -> 7
    x:xs -> 20 + x

Then what happens imperatively is something like this:

if not_empty.constructor == 0
    return 7
elseif not_empty.constructor == 1
    return 20 + dereference(not_empty.head)
endif

(Similarly, if you had mentioned xs, it would dereference the tail pointer.)

Between constructing list structures and pattern matching on them, you now know the basic building blocks used to build every function on lists! At the most basic level, those are the only two list-y things you can do.

user_7916040

[1,2,3] is syntactical sugar for 1:[2,3], which is ...

... (x:xs) where x = 1 and xs = [2,3].

So there's no "backward" "explosion" nay destructuring here.

Each : has two fields to it. That's it.

user_8498910
Related