Haskell Cheatsheet

scratchpad.hs

dup :: [a] -> [a]
dup []           = []
dup [x]          = [x]
dup (x : y : xs) = x : y : y : dup xs

dup xs = concat [ replicate (if odd i then 1 else 2) n | (i, n) <- zip [1 ..] xs ]

last :: [a] -> a 
last xs = head $ drop (length xs - 1) xs

last []           = error "calling last on empty list"
last (x     : []) = x
last (x : y : xs) = last (y : xs)

last = foldl (flip const) undefined

isLeapYear :: Int -> Bool
isLeapYear year 
  | year `mod` 4 /= 0   = False
  | year `mod` 400 == 0 = True
  | otherwise           = year `mod` 100 /= 0

pairs :: [a] -> [(a, a)]
pairs xs = zip xs (tail xs)

sorted :: Ord a => [a] -> Bool
sorted xs = and [ x <= y | (x, y) <- pairs xs ]

filterByIndex :: (Int -> Bool) -> [a] -> [a]
filterByIndex p xs = [ j | (i, j) <- zip [0 ..] xs, p i ]

digits :: Int -> [Int]
digits 0 = []
digits x = x `mod` 10 : digits (x `div` 10)

countOccurrence :: Int -> Int -> Int
countOccurrence n x = length $ filter (== n) $ digits x

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 ]

merge :: [Int] -> [Int] -> [Int]
merge [] ys = ys
merge xs [] = xs
merge l@(x : xs) r@(y : ys) 
  | x < y     = x : merge xs r
  | otherwise = y : merge l ys

msort :: [Int] -> [Int]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort l) (msort r)
  where (l, r) = splitAt (length xs `div` 2) xs
  

numBST :: Int -> Int
numBST n = bsts !! n
where
  bsts = [ bst n `mod` (10 ^ 9 + 7) | n <- [0 ..] ]
  bst 0 = 1
  bst 1 = 1
  bst n = sum [ (bsts !! (i - 1) * bsts !! (n - i)) `mod` (10 ^ 9 + 7) | i <- [1 .. n] ]

unzip :: [(a, b)] -> ([a], [b])
unzip = foldr (\(x, y) (xs, ys) -> (x : xs, y : ys)) ([], [])

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

length :: [a] -> Int
length = foldr (const (+ 1)) 0

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x acc -> if p x then x : acc else acc) []