import Data.Char
factorial :: (Num a, Eq a) => a -> a
factorial 1 = 1
factorial n = n * factorial (n-1)
fibonacci :: (Num a, Eq a) => a -> a
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)
sum' :: (Num a) => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs
length' :: [a] -> Int
length' [] = 0
length' (x:xs) = 1 + length' xs
count :: (Eq a) => a -> [a] -> Int
count _ [] = 0
count x (y:ys)
| x == y = 1 + count x ys
| otherwise = count x ys
replicate' :: Int -> a -> [a]
replicate' 0 _ = []
replicate' n x = x : replicate (n-1) x
repeat' :: a -> [a]
repeat' x = x : repeat' x
take' :: Int -> [a] -> [a]
take' 0 _ = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
fibonacciSeq :: (Num a) => [a]
fibonacciSeq = 1 : 1 : next fibonacciSeq
where next (x1:x2:xs) = (x1+x2) : next (x2:xs)
-- alt: where next (x1:xs@(x2:_)) = (x1+x2) : next xs
zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys
-- try: zip' [0..100] fibonacciSeq
eliminateAdjDups :: String -> String
eliminateAdjDups (x:ys@(y:_))
| x == y = eliminateAdjDups ys
| otherwise = x : eliminateAdjDups ys
eliminateAdjDups xs = xs
quicksort :: (Ord a, Eq a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort smaller ++ [x] ++ quicksort larger
where smaller = [y | y <- xs, y <= x]
larger = [y | y <- xs, y > x]
caesar :: String -> Int -> String
caesar p 0 = p
caesar [] _ = []
caesar (p:ps) n = encrypt p : caesar ps n
where encrypt k
| isLetter k = chr ((ord (toUpper k) - ord 'A' + n) `rem` 26 + ord 'A')
| otherwise = k
makeChange :: (Num a, Ord a) => a -> [a] -> [[a]]
makeChange 0 _ = [[]]
makeChange n [] = []
makeChange n denoms@(d:ds)
| d > n = makeChange n ds
| otherwise = [d:way | way <- makeChange (n-d) denoms]
++ makeChange n ds