Haskell Notes

Functional programming revision notes and examples.

Basic Function Definition

double :: Num a => a -> a
double x = x * 2

Pattern Matching

isEmpty :: [a] -> Bool
isEmpty [] = True
isEmpty _  = False

Recursion on Lists

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

Map

map' :: (a -> b) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = f x : map' f xs

Filter

filter' :: (a -> Bool) -> [a] -> [a]
filter' p [] = []
filter' p (x:xs)
  | p x       = x : filter' p xs
  | otherwise = filter' p xs

Foldr

sum' :: Num a => [a] -> a
sum' xs = foldr (+) 0 xs

Maybe

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x

Algebraic Data Types

data Tree a = Empty
            | Node (Tree a) a (Tree a)

Tree Recursion

treeSize :: Tree a -> Int
treeSize Empty = 0
treeSize (Node l _ r) = 1 + treeSize l + treeSize r

Useful Exam Reminders

• Start with the type signature.
• Handle the base case first.
• Use pattern matching before guards where possible.
• For lists, think about [] and x:xs.
• For trees, recurse into each subtree.
• Make sure every pattern returns the correct type.