Recursive definitions of few standard prelude functions

One thing I like about functional programming is the ease with which one can re-create built-in functions. Rewriting library functions on your own aids in understanding and reduces the feeling that library functions are any special. In that spirit, let's write few definitions from standard prelude on our own:

and

Decide if all logical values in a list are True:

and :: [Bool] -> Bool
and [] = True
and (x:xs) = x && and xs

First, we write the signature saying that and is a function that maps a Bool list to a single Bool value. If the list is empty, then the result is True, otherwise, it is value of head && applying and recursively to the tail of the list.

concat

Concatenate a list of lists:

concat :: [[a]] -> [a]
concat [] = []
concat ([]:xss) = concat xss
concat ((x:xs):xss) = x : concat (xs:xss)

So, concat is a function that maps list of lists of any type to a single list of such type. It results in an empty list for an empty list. If the head is an empty list, head is thrown out and concat is applied recursively to the tail of the list. Otherwise, each element of sub-list is consed to recursively applying concat to list containing the tail of list that is being processed and rest of the lists.

replicate

Produce a list with n identical elements:

replicate :: Int -> a -> [a]
replicate 0 x = []
replicate n x = x : replicate (n-1) x

replicate takes an integer and another argument of any type and produces a list of such type. For zero replications, it produces an empty list. For positive integers, x is consed to result of recursively applying replicate n-1 times to the input value.

!!

Select nth element of a list:

(!!) :: [a] -> Int -> a
[] !! _ = error "index too large"
(x:xs) !! 0 = x
(x:xs) !! n = xs !! (n-1)

So, !! is a function that maps a list of any type and an integer to a single value of such type. Applying !! to an empty list results in an error. For a non-empty list, $0^{th}$ index results in head of the list. For non-zero index, the function is recursively applied to the tail of the list asking for $(n-1)^{th}$ value.

elem

Decide if a value is an element of a list:

elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem e (x:xs) | x == e = True
              | otherwise = elem e xs

elem maps a value of any type that is an instance of Eq class and a list of such values to a single Bool value. Probing for any value in a empty list results in False. Otherwise, if the head matches the value then the result is True and if not, elem is recursively applied to the tail of the list.