Why Recursive Functions

• Simpler to define
• Many functions can be naturally defined in terms of themselves
• Properties can be proved by induction

Examples

fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)

product :: Num a => [a] -> a
product []     = 1

product (n:ns) = n * product ns

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

zip :: [a] -> [b] -> [(a, b)]
zip (x:xs) (y:ys) = [(x, y)] ++ zip xs ys
zip _ _ = []

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

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

qsort :: Ord a => [a] -> [a]
qsort [] = []

qsort (x:xs) =
 qsort smaller ++ [x] ++ qsort larger
    where

        smaller = [a | a <- xs, a <= x]
        larger  = [b | b <- xs, b > x]

concat :: [[a]] -> [a]
concat xxs = [x | xs <- xxs, x <- xs]

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x < y     = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

msort :: Ord a => [a] -> [a]
msort xs
    | length xs <= 1 = xs
    | otherwise      = msort xs = merge (msort l) (msort r)
        where (l, r) = splitAt (length xs `div` 2) xs