-- Our own formulation of cons lists
data List a = Nil
| Cons a (List a)
deriving (Show)
-- Haskell's builtin type [a] and List a are isomorphic:
-- toList . fromList = id
-- and fromList . toList = id
toList :: [a] -> List a
toList [] = Nil
toList (x:xs) = Cons x (toList xs)
fromList :: List a -> [a]
fromList Nil = []
fromList (Cons x xs) = x:fromList xs
-- The family of well-known list functions (combinators) can be
-- reformulated for List a ...
mapList :: (a -> b) -> List a -> List b
mapList f Nil = Nil
mapList f (Cons x xs) = Cons (f x) (mapList f xs)
-- ... but this quickly becomes tedious
filterList :: (a -> Bool) -> List a -> List a
filterList _ Nil = Nil
filterList p (Cons x xs) | p x = Cons x (filterList p xs)
| otherwise = filterList p xs
-- Use the isomorphism between [a] and List a
-- to save work when defining functions g over List a:
--
-- fromList
-- List a -------------→ [a]
-- | |
-- g | . | f
-- 🠃 🠃
-- List b ←------------- [b]
-- toList
liftList :: ([a] -> [b]) -> List a -> List b
liftList f = toList . f . fromList
-- The definition of functions over type List now is easier/more uniform:
mapList' :: (a -> b) -> List a -> List b
mapList' f = liftList (map f)
filterList' :: (a -> Bool) -> List a -> List a
filterList' p = liftList (filter p)
main :: IO ()
main = print $ fromList $ filterList' (> 3) $ mapList' (+1) $ toList [1..5]