{-|

Module      : MyReverse
Description : Implement reverse using left and right folds
Copyright   : © Frank Jung, 2020
License     : GPL-3

Reverse a list using `foldl` and `foldr`.

-}

module MyReverse (myRevl, myRevr, myRevRec) where

import           Control.Arrow ((>>>))

-- | Reverse a list using `foldl`.
myRevl :: [a] -> [a]
myRevl :: forall a. [a] -> [a]
myRevl = ([a] -> a -> [a]) -> [a] -> [a] -> [a]
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl [a] -> a -> [a]
forall a. [a] -> a -> [a]
revOp []

-- | Reverse a list using `foldr`.
-- This is the best performing version.
--
-- This pointfree form is the same as:
--
-- > myRevr xs = foldr (\ x acc -> (x :) >>> acc) id xs []
myRevr :: [a] -> [a]
myRevr :: forall a. [a] -> [a]
myRevr = ([a] -> [a] -> [a]) -> [a] -> [a] -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> ([a] -> [a]) -> [a] -> [a])
-> ([a] -> [a]) -> [a] -> [a] -> [a]
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
(>>>) (([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a])
-> (a -> [a] -> [a]) -> a -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (:)) [a] -> [a]
forall a. a -> a
id) []

-- | Reverse using recursion and reverse operation.
myRevRec :: [a] -> [a]
myRevRec :: forall a. [a] -> [a]
myRevRec = ([a] -> a -> [a]) -> [a] -> [a] -> [a]
forall b a. (b -> a -> b) -> b -> [a] -> b
rev [a] -> a -> [a]
forall a. [a] -> a -> [a]
revOp []
  where
    rev :: (t -> t -> t) -> t -> [t] -> t
rev t -> t -> t
_ t
acc []      = t
acc
    rev t -> t -> t
op t
acc (t
x:[t]
xs) = (t -> t -> t) -> t -> [t] -> t
rev t -> t -> t
op (t
acc t -> t -> t
`op` t
x) [t]
xs

-- | Operation to place element at the beginning of a list.
-- Same as:
--
-- > revOp xs x = x : xs
revOp :: [a] -> a -> [a]
revOp :: forall a. [a] -> a -> [a]
revOp = (a -> [a] -> [a]) -> [a] -> a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)