haskell-list-implementation.hs

module List
    ( MyList
    , fromList
    , toList
    , myMap
    , myFilter
    , myFoldl
    , myReverse
    , (+++)
    )
where

data MyList a = Cons a (MyList a) | Nil  deriving (Show, Eq)

fromList :: [a] -> MyList a
fromList []       = Nil
fromList (x : xs) = Cons x $ fromList xs

toList :: MyList a -> [a]
toList Nil         = []
toList (Cons x xs) = x : toList xs

myFoldl :: (b -> a -> b) -> b -> MyList a -> b
myFoldl _ b Nil         = b
myFoldl f b (Cons a as) = myFoldl f (f b a) as

myFoldr :: (a -> b -> b) -> b -> MyList a -> b
myFoldr _ b Nil         = b
myFoldr f b (Cons a as) = f a $ myFoldr f b as

myMap :: (a -> b) -> MyList a -> MyList b
myMap f = myFoldl (\b a -> (Cons (f a) b)) Nil

myFilter :: (a -> Bool) -> MyList a -> MyList a
myFilter p = myFoldr include Nil
    where include a r = if p a then Cons a r else r

(+++) :: MyList a -> MyList a -> MyList a
Nil       +++ Nil = Nil
xs        +++ Nil = xs
Nil       +++ ys  = ys
Cons x xs +++ ys  = Cons x xs +++ ys

myReverse :: MyList a -> MyList a
myReverse Nil = Nil
myReverse xs  = myFoldl (flip Cons) Nil xs