Linked List Exercise

LL.hs

-- Linked List
data LL a = Empty | Cons a (LL a)

instance (Show a) => Show (LL a) where
  show Empty = "[]"
  show (Cons a l) = (show a) ++ ":" ++ (show l)


nth :: LL a -> Int -> a
nth (Cons a _) 0 = a
nth (Cons _ l) n = nth l (n-1)

nthFromLast :: LL a -> Int -> a
nthFromLast l n = nth l (len l - n - 1)

len :: LL a -> Int
len Empty = 0
len (Cons _ l) = 1 + len l

partition :: (Ord a) => LL a -> a -> (LL a, LL a)
partition Empty _ = (Empty, Empty)
partition (Cons a l) b =
  let (x, y) = partition l b
  in if a < b then (Cons a x, y) else (x, Cons a y)

isPalindrome :: (Eq a) => LL a -> Bool
isPalindrome l = drome l (len l `div` 2) where
  drome :: (Eq a) => LL a -> Int -> Bool
  drome Empty _ = True
  drome l k = (nth l k) == (nthFromLast l k)


-- Tests
l = Cons 3 (Cons 2 (Cons 1 (Cons 0 Empty)))
p@(x,y) = partition l 2

main :: IO ()
main = do
  putStrLn $ show $ nth l 0
  putStrLn $ show $ nthFromLast l 0
  putStrLn $ show l
  putStrLn $ show x
  putStrLn $ show y
  putStrLn $ show $ isPalindrome (Cons 'm' (Cons 'o' (Cons 'm' Empty)))