-- 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)
filterList :: (a -> Bool) -> List a -> List a
filterList p Nil = Nil
fiterList p (Cons x xs)
| p x = Cons x (filterList p xs)
| otherwise = filterList p xs
-- lift any list-processing function g' to obtain
-- a function over our List type
liftList :: ([a] -> [b]) -> (List a -> List b)
liftList g' = toList . g' . fromList
mapList' :: (a -> b) -> List a -> List b
mapList' f xs = liftList (map f) xs
filterList' :: (a -> Bool) -> List a -> List a
filterList' p xs = liftList (filter p) xs
main :: IO ()
main = print $ mapList' (\x -> x + 42) $ toList [1..5]