    -- |
    -- Definitions of strict linked list.
    --
    -- Most basic operations like `fmap`, `filter`, `<*>`
    -- can only be implemented efficiently by producing an intermediate list in reversed order
    -- and then reversing it to the original order.
    -- These intermediate reversed functions are exposed by the API,
    -- because they very well may be useful for efficient implementations of data-structures built on top of list.
    -- E.g., the <http://hackage.haskell.org/package/deque "deque"> package exploits them heavily.
    --
    -- One useful rule of thumb would be that
    -- whenever you see that a function has a reversed counterpart,
    -- that counterpart is faster and hence if you don't care about the order or
    -- intend to reverse the list further down the line, you should give preference to that counterpart.
    --
    -- The typical `toList` and `fromList` conversions are provided by means of
    -- the `Foldable` and `IsList` instances.
    module StrictList where

    import StrictList.Prelude hiding (drop, dropWhile, reverse, take, takeWhile)

    -- |
    -- Strict linked list.
    data List a = Cons !a !(List a) | Nil
      deriving
        (List a -> List a -> Bool
    (List a -> List a -> Bool)
    -> (List a -> List a -> Bool) -> Eq (List a)
    forall a. Eq a => List a -> List a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: forall a. Eq a => List a -> List a -> Bool
    == :: List a -> List a -> Bool
    $c/= :: forall a. Eq a => List a -> List a -> Bool
    /= :: List a -> List a -> Bool
    Eq, Eq (List a)
    Eq (List a) =>
    (List a -> List a -> Ordering)
    -> (List a -> List a -> Bool)
    -> (List a -> List a -> Bool)
    -> (List a -> List a -> Bool)
    -> (List a -> List a -> Bool)
    -> (List a -> List a -> List a)
    -> (List a -> List a -> List a)
    -> Ord (List a)
    List a -> List a -> Bool
    List a -> List a -> Ordering
    List a -> List a -> List a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (List a)
    forall a. Ord a => List a -> List a -> Bool
    forall a. Ord a => List a -> List a -> Ordering
    forall a. Ord a => List a -> List a -> List a
    $ccompare :: forall a. Ord a => List a -> List a -> Ordering
    compare :: List a -> List a -> Ordering
    $c< :: forall a. Ord a => List a -> List a -> Bool
    < :: List a -> List a -> Bool
    $c<= :: forall a. Ord a => List a -> List a -> Bool
    <= :: List a -> List a -> Bool
    $c> :: forall a. Ord a => List a -> List a -> Bool
    > :: List a -> List a -> Bool
    $c>= :: forall a. Ord a => List a -> List a -> Bool
    >= :: List a -> List a -> Bool
    $cmax :: forall a. Ord a => List a -> List a -> List a
    max :: List a -> List a -> List a
    $cmin :: forall a. Ord a => List a -> List a -> List a
    min :: List a -> List a -> List a
    Ord, Int -> List a -> ShowS
    [List a] -> ShowS
    List a -> String
    (Int -> List a -> ShowS)
    -> (List a -> String) -> ([List a] -> ShowS) -> Show (List a)
    forall a. Show a => Int -> List a -> ShowS
    forall a. Show a => [List a] -> ShowS
    forall a. Show a => List a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Int -> List a -> ShowS
    showsPrec :: Int -> List a -> ShowS
    $cshow :: forall a. Show a => List a -> String
    show :: List a -> String
    $cshowList :: forall a. Show a => [List a] -> ShowS
    showList :: [List a] -> ShowS
    Show, ReadPrec [List a]
    ReadPrec (List a)
    Int -> ReadS (List a)
    ReadS [List a]
    (Int -> ReadS (List a))
    -> ReadS [List a]
    -> ReadPrec (List a)
    -> ReadPrec [List a]
    -> Read (List a)
    forall a. Read a => ReadPrec [List a]
    forall a. Read a => ReadPrec (List a)
    forall a. Read a => Int -> ReadS (List a)
    forall a. Read a => ReadS [List a]
    forall a.
    (Int -> ReadS a)
    -> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
    $creadsPrec :: forall a. Read a => Int -> ReadS (List a)
    readsPrec :: Int -> ReadS (List a)
    $creadList :: forall a. Read a => ReadS [List a]
    readList :: ReadS [List a]
    $creadPrec :: forall a. Read a => ReadPrec (List a)
    readPrec :: ReadPrec (List a)
    $creadListPrec :: forall a. Read a => ReadPrec [List a]
    readListPrec :: ReadPrec [List a]
    Read, (forall x. List a -> Rep (List a) x)
    -> (forall x. Rep (List a) x -> List a) -> Generic (List a)
    forall x. Rep (List a) x -> List a
    forall x. List a -> Rep (List a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall a x. Rep (List a) x -> List a
    forall a x. List a -> Rep (List a) x
    $cfrom :: forall a x. List a -> Rep (List a) x
    from :: forall x. List a -> Rep (List a) x
    $cto :: forall a x. Rep (List a) x -> List a
    to :: forall x. Rep (List a) x -> List a
    Generic, (forall a. List a -> Rep1 List a)
    -> (forall a. Rep1 List a -> List a) -> Generic1 List
    forall a. Rep1 List a -> List a
    forall a. List a -> Rep1 List a
    forall k (f :: k -> *).
    (forall (a :: k). f a -> Rep1 f a)
    -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
    $cfrom1 :: forall a. List a -> Rep1 List a
    from1 :: forall a. List a -> Rep1 List a
    $cto1 :: forall a. Rep1 List a -> List a
    to1 :: forall a. Rep1 List a -> List a
    Generic1, Typeable (List a)
    Typeable (List a) =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> List a -> c (List a))
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c (List a))
    -> (List a -> Constr)
    -> (List a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c (List a)))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a)))
    -> ((forall b. Data b => b -> b) -> List a -> List a)
    -> (forall r r'.
        (r -> r' -> r)
        -> r -> (forall d. Data d => d -> r') -> List a -> r)
    -> (forall r r'.
        (r' -> r -> r)
        -> r -> (forall d. Data d => d -> r') -> List a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> List a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> List a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> List a -> m (List a))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> List a -> m (List a))
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> List a -> m (List a))
    -> Data (List a)
    List a -> Constr
    List a -> DataType
    (forall b. Data b => b -> b) -> List a -> List a
    forall a. Data a => Typeable (List a)
    forall a. Data a => List a -> Constr
    forall a. Data a => List a -> DataType
    forall a.
    Data a =>
    (forall b. Data b => b -> b) -> List a -> List a
    forall a u.
    Data a =>
    Int -> (forall d. Data d => d -> u) -> List a -> u
    forall a u. Data a => (forall d. Data d => d -> u) -> List a -> [u]
    forall a r r'.
    Data a =>
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    forall a r r'.
    Data a =>
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    forall a (m :: * -> *).
    (Data a, Monad m) =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    forall a (c :: * -> *).
    Data a =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (List a)
    forall a (c :: * -> *).
    Data a =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> List a -> c (List a)
    forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (List a))
    forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a))
    forall a.
    Typeable a =>
    (forall (c :: * -> *).
     (forall d b. Data d => c (d -> b) -> d -> c b)
     -> (forall g. g -> c g) -> a -> c a)
    -> (forall (c :: * -> *).
        (forall b r. Data b => c (b -> r) -> c r)
        -> (forall r. r -> c r) -> Constr -> c a)
    -> (a -> Constr)
    -> (a -> DataType)
    -> (forall (t :: * -> *) (c :: * -> *).
        Typeable t =>
        (forall d. Data d => c (t d)) -> Maybe (c a))
    -> (forall (t :: * -> * -> *) (c :: * -> *).
        Typeable t =>
        (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
    -> ((forall b. Data b => b -> b) -> a -> a)
    -> (forall r r'.
        (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall r r'.
        (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
    -> (forall u. (forall d. Data d => d -> u) -> a -> [u])
    -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
    -> (forall (m :: * -> *).
        Monad m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> (forall (m :: * -> *).
        MonadPlus m =>
        (forall d. Data d => d -> m d) -> a -> m a)
    -> Data a
    forall u. Int -> (forall d. Data d => d -> u) -> List a -> u
    forall u. (forall d. Data d => d -> u) -> List a -> [u]
    forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (List a)
    forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> List a -> c (List a)
    forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (List a))
    forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a))
    $cgfoldl :: forall a (c :: * -> *).
    Data a =>
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> List a -> c (List a)
    gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> List a -> c (List a)
    $cgunfold :: forall a (c :: * -> *).
    Data a =>
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (List a)
    gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (List a)
    $ctoConstr :: forall a. Data a => List a -> Constr
    toConstr :: List a -> Constr
    $cdataTypeOf :: forall a. Data a => List a -> DataType
    dataTypeOf :: List a -> DataType
    $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (List a))
    dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (List a))
    $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
    (Data a, Typeable t) =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a))
    dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (List a))
    $cgmapT :: forall a.
    Data a =>
    (forall b. Data b => b -> b) -> List a -> List a
    gmapT :: (forall b. Data b => b -> b) -> List a -> List a
    $cgmapQl :: forall a r r'.
    Data a =>
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    gmapQl :: forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    $cgmapQr :: forall a r r'.
    Data a =>
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    gmapQr :: forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> List a -> r
    $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> List a -> [u]
    gmapQ :: forall u. (forall d. Data d => d -> u) -> List a -> [u]
    $cgmapQi :: forall a u.
    Data a =>
    Int -> (forall d. Data d => d -> u) -> List a -> u
    gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> List a -> u
    $cgmapM :: forall a (m :: * -> *).
    (Data a, Monad m) =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    gmapM :: forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    $cgmapMp :: forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    gmapMp :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    $cgmapMo :: forall a (m :: * -> *).
    (Data a, MonadPlus m) =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    gmapMo :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> List a -> m (List a)
    Data, Typeable)

    instance IsList (List a) where
      type Item (List a) = a
      fromList :: [Item (List a)] -> List a
    fromList = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a) -> ([a] -> List a) -> [a] -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . [a] -> List a
    forall a. [a] -> List a
    fromListReversed
      toList :: List a -> [Item (List a)]
    toList = (a -> [a] -> [a]) -> [a] -> List a -> [a]
    forall a b. (a -> b -> b) -> b -> List a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (:) []

    instance Semigroup (List a) where
      <> :: List a -> List a -> List a
    (<>) List a
    a List a
    b = case List a
    b of
        List a
    Nil -> List a
    a
        List a
    _ -> List a -> List a -> List a
    forall a. List a -> List a -> List a
    prependReversed (List a -> List a
    forall a. List a -> List a
    reverse List a
    a) List a
    b

    instance Monoid (List a) where
      mempty :: List a
    mempty = List a
    forall a. List a
    Nil
      mappend :: List a -> List a -> List a
    mappend = List a -> List a -> List a
    forall a. Semigroup a => a -> a -> a
    (<>)

    instance Functor List where
      fmap :: forall a b. (a -> b) -> List a -> List b
    fmap a -> b
    f = List b -> List b
    forall a. List a -> List a
    reverse (List b -> List b) -> (List a -> List b) -> List a -> List b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . (a -> b) -> List a -> List b
    forall a b. (a -> b) -> List a -> List b
    mapReversed a -> b
    f

    instance Foldable List where
      foldr :: forall a b. (a -> b -> b) -> b -> List a -> b
    foldr a -> b -> b
    step b
    init =
        let loop :: List a -> b
    loop = \case
              Cons a
    head List a
    tail -> a -> b -> b
    step a
    head (List a -> b
    loop List a
    tail)
              List a
    _ -> b
    init
         in List a -> b
    loop
      foldl' :: forall b a. (b -> a -> b) -> b -> List a -> b
    foldl' b -> a -> b
    step b
    init =
        let loop :: b -> List a -> b
    loop !b
    acc = \case
              Cons a
    head List a
    tail -> b -> List a -> b
    loop (b -> a -> b
    step b
    acc a
    head) List a
    tail
              List a
    _ -> b
    acc
         in b -> List a -> b
    loop b
    init

    instance Traversable List where
      sequenceA :: forall (f :: * -> *) a. Applicative f => List (f a) -> f (List a)
    sequenceA = (f a -> f (List a) -> f (List a))
    -> f (List a) -> List (f a) -> f (List a)
    forall a b. (a -> b -> b) -> b -> List a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr ((a -> List a -> List a) -> f a -> f (List a) -> f (List a)
    forall a b c. (a -> b -> c) -> f a -> f b -> f c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    liftA2 a -> List a -> List a
    forall a. a -> List a -> List a
    Cons) (List a -> f (List a)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure List a
    forall a. List a
    Nil)

    instance Apply List where
      <.> :: forall a b. List (a -> b) -> List a -> List b
    (<.>) List (a -> b)
    fList List a
    aList = List (a -> b) -> List a -> List b
    forall a b. List (a -> b) -> List a -> List b
    apReversed (List (a -> b) -> List (a -> b)
    forall a. List a -> List a
    reverse List (a -> b)
    fList) (List a -> List a
    forall a. List a -> List a
    reverse List a
    aList)

    instance Applicative List where
      pure :: forall a. a -> List a
    pure a
    a = a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    a List a
    forall a. List a
    Nil
      <*> :: forall a b. List (a -> b) -> List a -> List b
    (<*>) = List (a -> b) -> List a -> List b
    forall a b. List (a -> b) -> List a -> List b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    (<.>)

    instance Alt List where
      <!> :: forall a. List a -> List a -> List a
    (<!>) = List a -> List a -> List a
    forall a. Monoid a => a -> a -> a
    mappend

    instance Plus List where
      zero :: forall a. List a
    zero = List a
    forall a. Monoid a => a
    mempty

    instance Alternative List where
      empty :: forall a. List a
    empty = List a
    forall a. List a
    forall (f :: * -> *) a. Plus f => f a
    zero
      <|> :: forall a. List a -> List a -> List a
    (<|>) = List a -> List a -> List a
    forall a. List a -> List a -> List a
    forall (f :: * -> *) a. Alt f => f a -> f a -> f a
    (<!>)

    instance Bind List where
      >>- :: forall a b. List a -> (a -> List b) -> List b
    (>>-) List a
    ma a -> List b
    amb = List b -> List b
    forall a. List a -> List a
    reverse ((a -> List b) -> List a -> List b
    forall a b. (a -> List b) -> List a -> List b
    explodeReversed a -> List b
    amb List a
    ma)
      join :: forall a. List (List a) -> List a
    join = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a)
    -> (List (List a) -> List a) -> List (List a) -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . List (List a) -> List a
    forall a. List (List a) -> List a
    joinReversed

    instance Monad List where
      return :: forall a. a -> List a
    return = a -> List a
    forall a. a -> List a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
      >>= :: forall a b. List a -> (a -> List b) -> List b
    (>>=) = List a -> (a -> List b) -> List b
    forall a b. List a -> (a -> List b) -> List b
    forall (m :: * -> *) a b. Bind m => m a -> (a -> m b) -> m b
    (>>-)

    instance MonadPlus List where
      mzero :: forall a. List a
    mzero = List a
    forall a. List a
    forall (f :: * -> *) a. Alternative f => f a
    empty
      mplus :: forall a. List a -> List a -> List a
    mplus = List a -> List a -> List a
    forall a. List a -> List a -> List a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    (<|>)

    instance (Hashable a) => Hashable (List a)

    instance (NFData a) => NFData (List a)

    instance NFData1 List

    -- |
    -- Convert to lazy list in normal form (with all elements and spine evaluated).
    toListReversed :: List a -> [a]
    toListReversed :: forall a. List a -> [a]
    toListReversed = [a] -> List a -> [a]
    forall {a}. [a] -> List a -> [a]
    go []
      where
        go :: [a] -> List a -> [a]
    go ![a]
    outputList = \case
          Cons a
    element List a
    list -> [a] -> List a -> [a]
    go (a
    element a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    : [a]
    outputList) List a
    list
          List a
    Nil -> [a]
    outputList

    -- |
    -- Reverse the list.
    {-# INLINE reverse #-}
    reverse :: List a -> List a
    reverse :: forall a. List a -> List a
    reverse = (List a -> a -> List a) -> List a -> List a -> List a
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' ((a -> List a -> List a) -> List a -> a -> List a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip a -> List a -> List a
    forall a. a -> List a -> List a
    Cons) List a
    forall a. List a
    Nil

    -- |
    -- Leave only the specified amount of elements.
    {-# INLINE take #-}
    take :: Int -> List a -> List a
    take :: forall a. Int -> List a -> List a
    take Int
    amount = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a) -> (List a -> List a) -> List a -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . Int -> List a -> List a
    forall a. Int -> List a -> List a
    takeReversed Int
    amount

    -- |
    -- Leave only the specified amount of elements, in reverse order.
    takeReversed :: Int -> List a -> List a
    takeReversed :: forall a. Int -> List a -> List a
    takeReversed =
      let loop :: List a -> t -> List a -> List a
    loop !List a
    output !t
    amount =
            if t
    amount t -> t -> Bool
    forall a. Ord a => a -> a -> Bool
    > t
    0
              then \case
                Cons a
    head List a
    tail -> List a -> t -> List a -> List a
    loop (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    output) (t -> t
    forall a. Enum a => a -> a
    pred t
    amount) List a
    tail
                List a
    _ -> List a
    output
              else List a -> List a -> List a
    forall a b. a -> b -> a
    const List a
    output
       in List a -> Int -> List a -> List a
    forall {t} {a}.
    (Ord t, Num t, Enum t) =>
    List a -> t -> List a -> List a
    loop List a
    forall a. List a
    Nil

    -- |
    -- Leave only the elements after the specified amount of first elements.
    drop :: Int -> List a -> List a
    drop :: forall a. Int -> List a -> List a
    drop Int
    amount =
      if Int
    amount Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    0
        then \case
          Cons a
    _ List a
    tail -> Int -> List a -> List a
    forall a. Int -> List a -> List a
    drop (Int -> Int
    forall a. Enum a => a -> a
    pred Int
    amount) List a
    tail
          List a
    _ -> List a
    forall a. List a
    Nil
        else List a -> List a
    forall a. a -> a
    forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
    id

    -- |
    -- Leave only the elements satisfying the predicate.
    {-# INLINE filter #-}
    filter :: (a -> Bool) -> List a -> List a
    filter :: forall a. (a -> Bool) -> List a -> List a
    filter a -> Bool
    predicate = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a) -> (List a -> List a) -> List a -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . (a -> Bool) -> List a -> List a
    forall a. (a -> Bool) -> List a -> List a
    filterReversed a -> Bool
    predicate

    -- |
    -- Leave only the elements satisfying the predicate,
    -- producing a list in reversed order.
    filterReversed :: (a -> Bool) -> List a -> List a
    filterReversed :: forall a. (a -> Bool) -> List a -> List a
    filterReversed a -> Bool
    predicate =
      let loop :: List a -> List a -> List a
    loop !List a
    newList = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then List a -> List a -> List a
    loop (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    newList) List a
    tail
                else List a -> List a -> List a
    loop List a
    newList List a
    tail
            List a
    Nil -> List a
    newList
       in List a -> List a -> List a
    loop List a
    forall a. List a
    Nil

    -- |
    -- Leave only the first elements satisfying the predicate.
    {-# INLINE takeWhile #-}
    takeWhile :: (a -> Bool) -> List a -> List a
    takeWhile :: forall a. (a -> Bool) -> List a -> List a
    takeWhile a -> Bool
    predicate = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a) -> (List a -> List a) -> List a -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . (a -> Bool) -> List a -> List a
    forall a. (a -> Bool) -> List a -> List a
    takeWhileReversed a -> Bool
    predicate

    -- |
    -- Leave only the first elements satisfying the predicate,
    -- producing a list in reversed order.
    takeWhileReversed :: (a -> Bool) -> List a -> List a
    takeWhileReversed :: forall a. (a -> Bool) -> List a -> List a
    takeWhileReversed a -> Bool
    predicate =
      let loop :: List a -> List a -> List a
    loop !List a
    newList = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then List a -> List a -> List a
    loop (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    newList) List a
    tail
                else List a
    newList
            List a
    _ -> List a
    newList
       in List a -> List a -> List a
    loop List a
    forall a. List a
    Nil

    -- |
    -- Drop the first elements satisfying the predicate.
    dropWhile :: (a -> Bool) -> List a -> List a
    dropWhile :: forall a. (a -> Bool) -> List a -> List a
    dropWhile a -> Bool
    predicate = \case
      Cons a
    head List a
    tail ->
        if a -> Bool
    predicate a
    head
          then (a -> Bool) -> List a -> List a
    forall a. (a -> Bool) -> List a -> List a
    dropWhile a -> Bool
    predicate List a
    tail
          else a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    tail
      List a
    Nil -> List a
    forall a. List a
    Nil

    -- |
    -- An optimized version of the same predicate applied to `takeWhile` and `dropWhile`.
    -- IOW,
    --
    -- >span predicate list = (takeWhile predicate list, dropWhile predicate list)
    {-# INLINE span #-}
    span :: (a -> Bool) -> List a -> (List a, List a)
    span :: forall a. (a -> Bool) -> List a -> (List a, List a)
    span a -> Bool
    predicate = (List a -> List a) -> (List a, List a) -> (List a, List a)
    forall b c d. (b -> c) -> (b, d) -> (c, d)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first List a -> List a
    forall a. List a -> List a
    reverse ((List a, List a) -> (List a, List a))
    -> (List a -> (List a, List a)) -> List a -> (List a, List a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . (a -> Bool) -> List a -> (List a, List a)
    forall a. (a -> Bool) -> List a -> (List a, List a)
    spanReversed a -> Bool
    predicate

    -- |
    -- Same as `span`, only with the first list in reverse order.
    spanReversed :: (a -> Bool) -> List a -> (List a, List a)
    spanReversed :: forall a. (a -> Bool) -> List a -> (List a, List a)
    spanReversed a -> Bool
    predicate =
      let buildPrefix :: List a -> List a -> (List a, List a)
    buildPrefix !List a
    prefix = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then List a -> List a -> (List a, List a)
    buildPrefix (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    prefix) List a
    tail
                else (List a
    prefix, a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    tail)
            List a
    _ -> (List a
    prefix, List a
    forall a. List a
    Nil)
       in List a -> List a -> (List a, List a)
    buildPrefix List a
    forall a. List a
    Nil

    -- |
    -- An opposite version of `span`. I.e.,
    --
    -- >break predicate = span (not . predicate)
    {-# INLINE break #-}
    break :: (a -> Bool) -> List a -> (List a, List a)
    break :: forall a. (a -> Bool) -> List a -> (List a, List a)
    break a -> Bool
    predicate = (List a -> List a) -> (List a, List a) -> (List a, List a)
    forall b c d. (b -> c) -> (b, d) -> (c, d)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first List a -> List a
    forall a. List a -> List a
    reverse ((List a, List a) -> (List a, List a))
    -> (List a -> (List a, List a)) -> List a -> (List a, List a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . (a -> Bool) -> List a -> (List a, List a)
    forall a. (a -> Bool) -> List a -> (List a, List a)
    breakReversed a -> Bool
    predicate

    -- |
    -- Same as `break`, only with the first list in reverse order.
    breakReversed :: (a -> Bool) -> List a -> (List a, List a)
    breakReversed :: forall a. (a -> Bool) -> List a -> (List a, List a)
    breakReversed a -> Bool
    predicate =
      let buildPrefix :: List a -> List a -> (List a, List a)
    buildPrefix !List a
    prefix = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then (List a
    prefix, a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    tail)
                else List a -> List a -> (List a, List a)
    buildPrefix (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    prefix) List a
    tail
            List a
    _ -> (List a
    prefix, List a
    forall a. List a
    Nil)
       in List a -> List a -> (List a, List a)
    buildPrefix List a
    forall a. List a
    Nil

    -- |
    -- Same as @(`takeWhile` predicate . `reverse`)@.
    -- E.g.,
    --
    -- >>> takeWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])
    -- fromList [5,4,3]
    {-# INLINE takeWhileFromEnding #-}
    takeWhileFromEnding :: (a -> Bool) -> List a -> List a
    takeWhileFromEnding :: forall a. (a -> Bool) -> List a -> List a
    takeWhileFromEnding a -> Bool
    predicate =
      (List a -> a -> List a) -> List a -> List a -> List a
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl'
        ( \List a
    newList a
    a ->
            if a -> Bool
    predicate a
    a
              then a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    a List a
    newList
              else List a
    forall a. List a
    Nil
        )
        List a
    forall a. List a
    Nil

    -- |
    -- Same as @(`dropWhile` predicate . `reverse`)@.
    -- E.g.,
    --
    -- >>> dropWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])
    -- fromList [2,4,1]
    dropWhileFromEnding :: (a -> Bool) -> List a -> List a
    dropWhileFromEnding :: forall a. (a -> Bool) -> List a -> List a
    dropWhileFromEnding a -> Bool
    predicate =
      let loop :: List a -> List a -> List a -> List a
    loop List a
    confirmed List a
    unconfirmed = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then List a -> List a -> List a -> List a
    loop List a
    confirmed (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    unconfirmed) List a
    tail
                else
                  let !newConfirmed :: List a
    newConfirmed = a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    unconfirmed
                   in List a -> List a -> List a -> List a
    loop List a
    newConfirmed List a
    newConfirmed List a
    tail
            List a
    Nil -> List a
    confirmed
       in List a -> List a -> List a -> List a
    loop List a
    forall a. List a
    Nil List a
    forall a. List a
    Nil

    -- |
    -- Same as @(`span` predicate . `reverse`)@.
    spanFromEnding :: (a -> Bool) -> List a -> (List a, List a)
    spanFromEnding :: forall a. (a -> Bool) -> List a -> (List a, List a)
    spanFromEnding a -> Bool
    predicate =
      let loop :: List a -> List a -> List a -> List a -> (List a, List a)
    loop !List a
    confirmedPrefix !List a
    unconfirmedPrefix !List a
    suffix = \case
            Cons a
    head List a
    tail ->
              if a -> Bool
    predicate a
    head
                then List a -> List a -> List a -> List a -> (List a, List a)
    loop List a
    confirmedPrefix (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    unconfirmedPrefix) (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    suffix) List a
    tail
                else
                  let !prefix :: List a
    prefix = a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    unconfirmedPrefix
                   in List a -> List a -> List a -> List a -> (List a, List a)
    loop List a
    prefix List a
    prefix List a
    forall a. List a
    Nil List a
    tail
            List a
    Nil -> (List a
    suffix, List a
    confirmedPrefix)
       in List a -> List a -> List a -> List a -> (List a, List a)
    loop List a
    forall a. List a
    Nil List a
    forall a. List a
    Nil List a
    forall a. List a
    Nil

    -- |
    -- Pattern match on list using functions.
    --
    -- Allows to achieve all the same as `uncons` only without intermediate `Maybe`.
    --
    -- Essentially provides the same functionality as `either` for `Either` and `maybe` for `Maybe`.
    {-# INLINE match #-}
    match :: result -> (element -> List element -> result) -> List element -> result
    match :: forall result element.
    result
    -> (element -> List element -> result) -> List element -> result
    match result
    nil element -> List element -> result
    cons = \case
      Cons element
    head List element
    tail -> element -> List element -> result
    cons element
    head List element
    tail
      List element
    Nil -> result
    nil

    -- |
    -- Get the first element and the remainder of the list if it's not empty.
    {-# INLINE uncons #-}
    uncons :: List a -> Maybe (a, List a)
    uncons :: forall a. List a -> Maybe (a, List a)
    uncons = \case
      Cons a
    head List a
    tail -> (a, List a) -> Maybe (a, List a)
    forall a. a -> Maybe a
    Just (a
    head, List a
    tail)
      List a
    _ -> Maybe (a, List a)
    forall a. Maybe a
    Nothing

    -- |
    -- Get the first element, if list is not empty.
    {-# INLINE head #-}
    head :: List a -> Maybe a
    head :: forall a. List a -> Maybe a
    head = \case
      Cons a
    head List a
    _ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    head
      List a
    _ -> Maybe a
    forall a. Maybe a
    Nothing

    -- |
    -- Get the last element, if list is not empty.
    {-# INLINE last #-}
    last :: List a -> Maybe a
    last :: forall a. List a -> Maybe a
    last =
      let loop :: Maybe a -> List a -> Maybe a
    loop !Maybe a
    previous = \case
            Cons a
    head List a
    tail -> Maybe a -> List a -> Maybe a
    loop (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    head) List a
    tail
            List a
    _ -> Maybe a
    previous
       in Maybe a -> List a -> Maybe a
    forall {a}. Maybe a -> List a -> Maybe a
    loop Maybe a
    forall a. Maybe a
    Nothing

    -- |
    -- Get all elements of the list but the first one.
    {-# INLINE tail #-}
    tail :: List a -> List a
    tail :: forall a. List a -> List a
    tail = \case
      Cons a
    _ List a
    tail -> List a
    tail
      List a
    Nil -> List a
    forall a. List a
    Nil

    -- |
    -- Get all elements but the last one.
    {-# INLINE init #-}
    init :: List a -> List a
    init :: forall a. List a -> List a
    init = List a -> List a
    forall a. List a -> List a
    reverse (List a -> List a) -> (List a -> List a) -> List a -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . List a -> List a
    forall a. List a -> List a
    initReversed

    -- |
    -- Get all elements but the last one, producing the results in reverse order.
    initReversed :: List a -> List a
    initReversed :: forall a. List a -> List a
    initReversed =
      let loop :: List a -> List a -> List a -> List a
    loop !List a
    confirmed !List a
    unconfirmed = \case
            Cons a
    head List a
    tail -> List a -> List a -> List a -> List a
    loop List a
    unconfirmed (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head List a
    unconfirmed) List a
    tail
            List a
    _ -> List a
    confirmed
       in List a -> List a -> List a -> List a
    forall {a}. List a -> List a -> List a -> List a
    loop List a
    forall a. List a
    Nil List a
    forall a. List a
    Nil

    -- |
    -- Apply the functions in the left list to elements in the right one.
    {-# INLINE apZipping #-}
    apZipping :: List (a -> b) -> List a -> List b
    apZipping :: forall a b. List (a -> b) -> List a -> List b
    apZipping List (a -> b)
    left List a
    right = List (a -> b) -> List a -> List b
    forall a b. List (a -> b) -> List a -> List b
    apZippingReversed (List (a -> b) -> List (a -> b)
    forall a. List a -> List a
    reverse List (a -> b)
    left) (List a -> List a
    forall a. List a -> List a
    reverse List a
    right)

    -- |
    -- Apply the functions in the left list to elements in the right one,
    -- producing a list of results in reversed order.
    apZippingReversed :: List (a -> b) -> List a -> List b
    apZippingReversed :: forall a b. List (a -> b) -> List a -> List b
    apZippingReversed =
      let loop :: List a -> List (t -> a) -> List t -> List a
    loop List a
    bList = \case
            Cons t -> a
    f List (t -> a)
    fTail -> \case
              Cons t
    a List t
    aTail -> List a -> List (t -> a) -> List t -> List a
    loop (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons (t -> a
    f t
    a) List a
    bList) List (t -> a)
    fTail List t
    aTail
              List t
    _ -> List a
    bList
            List (t -> a)
    _ -> List a -> List t -> List a
    forall a b. a -> b -> a
    const List a
    bList
       in List b -> List (a -> b) -> List a -> List b
    forall {a} {t}. List a -> List (t -> a) -> List t -> List a
    loop List b
    forall a. List a
    Nil

    -- ** Reversed intermediate functions used in instances

    -------------------------

    -- |
    -- Construct from a lazy list in reversed order.
    {-# INLINE fromListReversed #-}
    fromListReversed :: [a] -> List a
    fromListReversed :: forall a. [a] -> List a
    fromListReversed = (List a -> a -> List a) -> List a -> [a] -> List 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 -> List a -> List a) -> List a -> a -> List a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip a -> List a -> List a
    forall a. a -> List a -> List a
    Cons) List a
    forall a. List a
    Nil

    -- |
    -- Add elements of the left list in reverse order
    -- in the beginning of the right list.
    {-# INLINE prependReversed #-}
    prependReversed :: List a -> List a -> List a
    prependReversed :: forall a. List a -> List a -> List a
    prependReversed = \case
      Cons a
    head List a
    tail -> List a -> List a -> List a
    forall a. List a -> List a -> List a
    prependReversed List a
    tail (List a -> List a) -> (List a -> List a) -> List a -> List a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    head
      List a
    Nil -> List a -> List a
    forall a. a -> a
    forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
    id

    -- |
    -- Map producing a list in reversed order.
    mapReversed :: (a -> b) -> List a -> List b
    mapReversed :: forall a b. (a -> b) -> List a -> List b
    mapReversed a -> b
    f =
      let loop :: List b -> List a -> List b
    loop !List b
    newList = \case
            Cons a
    head List a
    tail -> List b -> List a -> List b
    loop (b -> List b -> List b
    forall a. a -> List a -> List a
    Cons (a -> b
    f a
    head) List b
    newList) List a
    tail
            List a
    _ -> List b
    newList
       in List b -> List a -> List b
    loop List b
    forall a. List a
    Nil

    -- |
    -- Apply the functions in the left list to every element in the right one,
    -- producing a list of results in reversed order.
    {-# INLINE apReversed #-}
    apReversed :: List (a -> b) -> List a -> List b
    apReversed :: forall a b. List (a -> b) -> List a -> List b
    apReversed List (a -> b)
    fList List a
    aList = (List b -> (a -> b) -> List b) -> List b -> List (a -> b) -> List b
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (\List b
    z a -> b
    f -> (List b -> a -> List b) -> List b -> List a -> List b
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (\List b
    z a
    a -> b -> List b -> List b
    forall a. a -> List a -> List a
    Cons (a -> b
    f a
    a) List b
    z) List b
    z List a
    aList) List b
    forall a. List a
    Nil List (a -> b)
    fList

    -- |
    -- Use a function to produce a list of lists and then concat them sequentially,
    -- producing the results in reversed order.
    {-# INLINE explodeReversed #-}
    explodeReversed :: (a -> List b) -> List a -> List b
    explodeReversed :: forall a b. (a -> List b) -> List a -> List b
    explodeReversed a -> List b
    amb = (List b -> a -> List b) -> List b -> List a -> List b
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (\List b
    z -> (List b -> b -> List b) -> List b -> List b -> List b
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' ((b -> List b -> List b) -> List b -> b -> List b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip b -> List b -> List b
    forall a. a -> List a -> List a
    Cons) List b
    z (List b -> List b) -> (a -> List b) -> a -> List b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
    Category cat =>
    cat b c -> cat a b -> cat a c
    . a -> List b
    amb) List b
    forall a. List a
    Nil

    -- |
    -- Join (concat) producing results in reversed order.
    {-# INLINE joinReversed #-}
    joinReversed :: List (List a) -> List a
    joinReversed :: forall a. List (List a) -> List a
    joinReversed = (List a -> List a -> List a) -> List a -> List (List a) -> List a
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' ((List a -> a -> List a) -> List a -> List a -> List a
    forall b a. (b -> a -> b) -> b -> List a -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' ((a -> List a -> List a) -> List a -> a -> List a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip a -> List a -> List a
    forall a. a -> List a -> List a
    Cons)) List a
    forall a. List a
    Nil

    -- |
    -- Map and filter elements producing results in reversed order.
    {-# INLINE mapMaybeReversed #-}
    mapMaybeReversed :: (a -> Maybe b) -> List a -> List b
    mapMaybeReversed :: forall a b. (a -> Maybe b) -> List a -> List b
    mapMaybeReversed a -> Maybe b
    f = List b -> List a -> List b
    go List b
    forall a. List a
    Nil
      where
        go :: List b -> List a -> List b
    go !List b
    outputList = \case
          Cons a
    inputElement List a
    inputTail -> case a -> Maybe b
    f a
    inputElement of
            Just b
    outputElement -> List b -> List a -> List b
    go (b -> List b -> List b
    forall a. a -> List a -> List a
    Cons b
    outputElement List b
    outputList) List a
    inputTail
            Maybe b
    Nothing -> List b -> List a -> List b
    go List b
    outputList List a
    inputTail
          List a
    Nil -> List b
    outputList

    -- |
    -- Keep only the present values, reversing the order.
    catMaybesReversed :: List (Maybe a) -> List a
    catMaybesReversed :: forall a. List (Maybe a) -> List a
    catMaybesReversed = List a -> List (Maybe a) -> List a
    forall {a}. List a -> List (Maybe a) -> List a
    go List a
    forall a. List a
    Nil
      where
        go :: List a -> List (Maybe a) -> List a
    go !List a
    outputList = \case
          Cons Maybe a
    inputElement List (Maybe a)
    inputTail -> case Maybe a
    inputElement of
            Just a
    outputElement -> List a -> List (Maybe a) -> List a
    go (a -> List a -> List a
    forall a. a -> List a -> List a
    Cons a
    outputElement List a
    outputList) List (Maybe a)
    inputTail
            Maybe a
    Nothing -> List a -> List (Maybe a) -> List a
    go List a
    outputList List (Maybe a)
    inputTail
          List (Maybe a)
    Nil -> List a
    outputList