Katas2.hs

data List a = Empty | Cons a (List a)


instance (Show a) => Show (List a) where
    show xs = "<" ++ show' xs ++ ">"
        where
            show' Empty = ""
            show' (Cons x Empty) = show x
            show' (Cons x xs) = show x ++ "," ++ show' xs
    


-- convert built-in list to List
toList :: [a] -> List a
toList [] = Empty
toList (x:xs) = Cons x (toList xs)


-- convert List to built-in list
fromList :: List a -> [a]
fromList Empty = []
fromList (Cons x xs) = x : (fromList xs)


head' :: List a -> a
head' (Cons x xs) = x


tail' :: List a -> List a
tail' (Cons x xs) = xs


init' :: List a -> List a
init' (Cons x Empty) = Empty
init' (Cons x xs) = Cons x (init' xs)


last' :: List a -> a
last' (Cons x Empty) = x
last' (Cons x xs) = last' xs


-- append ys to xs
append :: List a -> List a -> List a
append Empty ys = ys
append (Cons x xs) ys = Cons x (append xs ys)


len :: List a -> Int
len Empty = 0
len (Cons _ (xs)) = 1 + len xs


take' :: Int -> List a -> List a
take' n Empty = Empty
take' 0 _ = Empty
take' n (Cons x xs) = Cons x (take' (n - 1) xs)


drop' :: Int -> List a -> List a
drop' 0 xs = xs
drop' n Empty = Empty
drop' n (Cons x xs) = drop' (n - 1) xs


-- like splitAt
split :: List a -> Int -> (List a, List a)
split xs n = (take' n xs, drop' n xs)


-- insert x into ys at i
insert :: a -> Int -> List a -> List a
insert x i Empty = Cons x Empty
insert x i ys | len ys <= i = append (Cons x Empty) ys
insert x i ys =
    let (y0, y1) = split ys i
     in append (append y0 (Cons x Empty)) y1


-- delete the element at i from xs
del :: Int -> List a -> List a
del 0 (Cons x xs) = xs
del i xs =
    let (x0, x1) = split xs i
     in append x0 (del 0 x1)


-- reverse a List
rev :: List a -> List a
rev Empty = Empty
rev (Cons x xs) = append (rev xs) (Cons x Empty)