{-|

Module      : MyFilter
Description : Implement filter using a fold
Copyright   : © Frank Jung, 2020
License     : GPL-3

Filter a list using fold. In the Prelude,
<https://hackage.haskell.org/package/base/docs/Prelude.html#v:filter filter>
is defined as a recursive function:

@
  filter :: (a -> Bool) -> [a] -> [a]
  filter _pred []    = []
  filter pred (x:xs)
    | pred x         = x : filter pred xs
    | otherwise      = filter pred xs
@

-}

module MyFilter (myFilter) where

-- | Filter a list using foldr.
myFilter :: (Foldable t, Ord a) => (a -> Bool) -> t a -> [a]
myFilter :: forall (t :: * -> *) a.
(Foldable t, Ord a) =>
(a -> Bool) -> t a -> [a]
myFilter a -> Bool
p = (a -> [a] -> [a]) -> [a] -> t a -> [a]
forall a b. (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
x [a]
z -> if a -> Bool
p a
x then a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
z else [a]
z) []