Ninety-Nine Haskell Problems: #6

-- Ninety-Nine Haskell Problems: Problem 6: find out whether a list is
-- a palindrome.

-- Displaying results

main :: IO ()
main = do
  printResult l0
  printResult l1
  printResult l2
  printResult l3
  printResult l4
  printResult l5

printResult :: Eq a => [a] -> IO ()
printResult list = do
  mapM_ (putStr . formatter) $ zip [1 ..] $ funcList <*> [list]
  putStrLn ""

formatter :: (Show a) => (Int, a) -> String
formatter (x, y) = show x ++ ") " ++ show y ++ "; "

funcList :: Eq a => [[a] -> Bool]
funcList = [one, two, three, four, five, six, seven, eight]

-- Test lists

l0 :: [()]
l0 = []

l1 :: [Int]
l1 = [1,2,3]

l2 :: String
l2 = "madamimadam"

l3 :: [Int]
l3 = [1,2,4,8,16,8,4,2,1]

l4 :: [Bool]
l4 = [True, False, False, True]

l5 :: [Float]
l5 = [1.1]

-- palindrome detection functions definitions
-- efficiency is measured in ticks; test list size: 2,000,000 values;
-- optimization -Odph

-- 103,02
one :: Eq a => [a] -> Bool
one list = list == reverse list

-- 103,037
two :: Eq a => [a] -> Bool
two list = list == foldl (flip (:)) [] list

-- 149,995
three :: Eq a => [a] -> Bool
three [] = True
three [_] = True
three list =
  let
    reversedList = snd reversedAndMeasured
    listLength = fst reversedAndMeasured
    reversedAndMeasured = reverseAndMeasure list
    reverseAndMeasure =
      foldl (\(n, xs) x -> (n + 1, x:xs)) (0, []) :: [a] -> (Int, [a])
    compareFirstHalves ol rl ll = aux ol rl (ll `div` 2 - 1) 0 True
      where
        aux (o:os) (r:rs) mi ci bool
          | o /= r = False
          | ci > mi = bool
          | otherwise = aux os rs mi (ci + 1) bool
  in
    compareFirstHalves list reversedList listLength

-- 109,917
four :: Eq a => [a] -> Bool
four list =
  let
  fullLength = length list
  firstHalf = div fullLength 2
  firstHalfAdjusted = fullLength - firstHalf
  in
  reverse (take firstHalf list) == drop firstHalfAdjusted list

-- 401200
five :: Eq a => [a] -> Bool
five [] = True
five [_] = True
five list
  | head list == last list = five $ (init . tail) list
  | otherwise = False

-- 218500
six :: Eq a => [a] -> Bool
six [] = True
six list = let
  listLength = length list
  maxIndex = listLength - 1
  middleIndex = listLength `div` 2 - 1
  in
  aux list middleIndex 0 maxIndex True
  where
    aux lst mdi mni mxi bv
      | mni > mdi = bv
      | (lst !! mni) /= (lst !! mxi) = False
      | otherwise = aux lst mdi (mni + 1) (mxi - 1) bv

-- 224,016
seven :: Eq a => [a] -> Bool
seven [] = True
seven [_] = True
seven list = let
  listLength = length list
  listHalfLength = div listLength 2
  reversedList = reverse list
  in
  take listHalfLength list == take listHalfLength reversedList

-- 204,1
eight :: Eq a => [a] -> Bool
eight [] = True
eight [_] = True
eight list = let
  countAndReverse c a [] = (c, a)
  countAndReverse c a (x:xs) = countAndReverse (c + 1) (x:a) xs
  countedAndReversed = countAndReverse 0 [] list
  listLength = fst countedAndReversed
  reversedList = snd countedAndReversed
  listHalfLength = listLength `div` 2
  in
  take listHalfLength list == take listHalfLength reversedList

-- 1) True; 2) True; 3) True; 4) True; 5) True; 6) True; 7) True; 8) True;
-- 1) False; 2) False; 3) False; 4) False; 5) False; 6) False; 7) False; 8) False;
-- 1) True; 2) True; 3) True; 4) True; 5) True; 6) True; 7) True; 8) True;
-- 1) True; 2) True; 3) True; 4) True; 5) True; 6) True; 7) True; 8) True;
-- 1) True; 2) True; 3) True; 4) True; 5) True; 6) True; 7) True; 8) True;
-- 1) True; 2) True; 3) True; 4) True; 5) True; 6) True; 7) True; 8) True;