Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

(x:xs) pattern Haskell logic

Tags:

haskell

cons

Let's say there is a simple function:

maximum' :: (Ord a) => [a] -> a  
maximum' [] = error "maximum of empty list"  
maximum' [x] = x  
maximum' (x:xs) = max x (maximum' xs)

I understand the idea and what (x:xs) does. As it was explained in details here What do the parentheses signify in (x:xs) when pattern matching? but there is one little thing that I cannot get out of my head. Since cons: operator appends x to a list xs, why is it that x is the first element of function argument list and xs is the tail when we use (x:xs)??? as if (x:xs) calls head and tail on argument list.

like image 352
A_P Avatar asked Feb 07 '26 16:02

A_P


2 Answers

This is just an instance of the general pattern that the constructor for a type is both used to construct elements of that type and to deconstruct. If you wrote

data MyList a = Empty | Cons a (MyList a)

you'd write

maximum' :: (Ord a) => MyList a -> a  
maximum' Empty = error "maximum of empty list"  
maximum' (Cons x Empty) = x  
maximum' (Cons x xs) = max x (maximum' xs)

Except that lists are actually defined equivalently to

data [a] = [] | a:as

so, just as with other data types, : is used both to construct and to deconstruct nonempty lists.

like image 158
Louis Wasserman Avatar answered Feb 09 '26 12:02

Louis Wasserman


The cons operator doesn't append, it prepends. That is x : xs produces a list that contains x as its first element and xs as the rest. Therefore the pattern x : xs likewise matches a list with x as the first element and xs as the rest.

like image 30
sepp2k Avatar answered Feb 09 '26 10:02

sepp2k



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!