# 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.