    {-# LANGUAGE
        DataKinds,
        PolyKinds,
        TypeFamilies,
        TypeOperators,
        UndecidableInstances #-}

    -- | Foldable types.
    --
    -- A minimal implementation of this interface is given by either 'FoldMap' or
    -- 'Foldr', but a default still needs to be given explicitly for the other.
    --
    -- @
    -- data MyType a = ... {- Some custom Foldable type -}
    --
    -- -- Method 1: Implement Foldr, default FoldMap.
    -- type instance 'Eval' ('Foldr' f y xs) = ... {- Explicit implementation -}
    -- type instance 'Eval' ('FoldMap' f xs) = 'FoldMapDefault_' f xs {- Default -}
    --
    -- -- Method 2: Implement FoldMap, default Foldr.
    -- type instance 'Eval' ('FoldMap' f xs) = ... {- Explicit implementation -}
    -- type instance 'Eval' ('Foldr' f y xs) = 'FoldrDefault_' f y xs {- Default -}
    -- @
    module Fcf.Class.Foldable
      ( -- * Core interface
        Foldr
      , FoldMap

        -- ** Default implementations
      , FoldMapDefault_
      , FoldrDefault_

        -- * Derived operations

        -- ** Predicates
      , And
      , Or
      , All
      , Any

        -- ** Numbers
      , Sum

        -- ** Lists
      , Concat
      , ConcatMap
      ) where

    import Fcf.Core (Exp, Eval)
    import Fcf.Combinators (Pure, Pure1, type (<=<))
    import Fcf.Data.Function (Bicomap)
    import Fcf.Class.Monoid
    import Fcf.Class.Monoid.Types (Endo(..), UnEndo)
    import Fcf.Data.Bool (type (&&), type (||))
    import Fcf.Data.Nat (Nat, type (+))

    -- $setup
    -- >>> import Fcf.Core (Eval)
    -- >>> import Fcf.Combinators (Flip, Pure)
    -- >>> import Fcf.Class.Ord (type (<))
    -- >>> import Fcf.Class.Monoid (type (.<>))
    -- >>> import Fcf.Data.Nat (type (+))
    -- >>> import Numeric.Natural

    -- | Type-level 'Data.Foldable.foldMap'.
    data FoldMap :: (a -> Exp m) -> t a -> Exp m

    -- List
    type instance Eval (FoldMap f '[]) = MEmpty
    type instance Eval (FoldMap f (x ': xs)) = Eval (f x) <> Eval (FoldMap f xs)

    -- Maybe
    type instance Eval (FoldMap f 'Nothing) = MEmpty
    type instance Eval (FoldMap f ('Just x)) = Eval (f x)

    -- Either
    type instance Eval (FoldMap f ('Left _a)) = MEmpty
    type instance Eval (FoldMap f ('Right x)) = Eval (f x)

    -- | Default implementation of 'FoldMap'.
    --
    -- === __Usage__
    --
    -- To define an instance of 'FoldMap' for a custom @MyType@ for which you already have
    -- an instance of 'Foldr':
    --
    -- @
    -- type instance 'Eval' ('FoldMap' f (xs :: MyType a)) = 'FoldMapDefault_' f xs
    -- @
    --
    -- ==== __Example__
    --
    -- >>> :kind! FoldMapDefault_ Pure [EQ, LT, GT]
    -- FoldMapDefault_ Pure [EQ, LT, GT] :: Ordering
    -- = LT
    type FoldMapDefault_ f xs = Eval (Foldr (Bicomap f Pure (.<>)) MEmpty xs)

    -- | Default implementation of 'Foldr'.
    --
    -- === __Usage__
    --
    -- To define an instance of 'Foldr' for a custom @MyType@ for which you already
    -- have an instance of 'FoldMap':
    --
    -- @
    -- type instance 'Eval' ('Foldr' f y (xs :: MyType a)) = 'FoldrDefault_' f y xs
    -- @
    --
    -- ==== __Example__
    --
    -- >>> :kind! FoldrDefault_ (.<>) EQ [EQ, LT, GT]
    -- FoldrDefault_ (.<>) EQ [EQ, LT, GT] :: Ordering
    -- = LT
    type FoldrDefault_ f y xs = Eval (UnEndo (Eval (FoldMap (Pure1 'Endo <=< Pure1 f) xs)) y)

    -- | Right fold.
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (Foldr (+) 0 [1, 2, 3, 4])
    -- Eval (Foldr (+) 0 [1, 2, 3, 4]) :: Natural
    -- = 10
    data Foldr :: (a -> b -> Exp b) -> b -> t a -> Exp b

    -- List
    type instance Eval (Foldr f y '[]) = y
    type instance Eval (Foldr f y (x ': xs)) = Eval (f x (Eval (Foldr f y xs)))

    -- Maybe
    type instance Eval (Foldr f y 'Nothing) = y
    type instance Eval (Foldr f y ('Just x)) = Eval (f x y)

    -- Either
    type instance Eval (Foldr f y ('Left _a)) = y
    type instance Eval (Foldr f y ('Right x)) = Eval (f x y)

    -- * Derived operations

    -- | Give @True@ if all of the booleans in the list are @True@.
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (And [True, True])
    -- Eval (And [True, True]) :: Bool
    -- = True
    --
    -- >>> :kind! Eval (And [True, True, False])
    -- Eval (And [True, True, False]) :: Bool
    -- = False
    data And :: t Bool -> Exp Bool
    type instance Eval (And lst) = Eval (Foldr (&&) 'True lst)

    -- | Whether all elements of the list satisfy a predicate.
    --
    -- Note: this identifier conflicts with 'Data.Monoid.All' (from "Data.Monoid").
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (All (Flip (<) 6) [0,1,2,3,4,5])
    -- Eval (All (Flip (<) 6) [0,1,2,3,4,5]) :: Bool
    -- = True
    --
    -- >>> :kind! Eval (All (Flip (<) 5) [0,1,2,3,4,5])
    -- Eval (All (Flip (<) 5) [0,1,2,3,4,5]) :: Bool
    -- = False
    data All :: (a -> Exp Bool) -> t a -> Exp Bool
    type instance Eval (All p lst) = Eval (Foldr (Bicomap p Pure (&&)) 'True lst)

    -- | Give @True@ if any of the booleans in the list are @True@.
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (Or [True, True])
    -- Eval (Or [True, True]) :: Bool
    -- = True
    --
    -- >>> :kind! Eval (Or [False, False])
    -- Eval (Or [False, False]) :: Bool
    -- = False
    data Or :: t Bool -> Exp Bool
    type instance Eval (Or lst) = Eval (Foldr (||) 'False lst)

    -- | Whether any element of the list satisfies a predicate.
    --
    -- Note: this identifier conflicts with 'Fcf.Utils.Any' (from "Fcf.Utils"),
    -- 'Data.Monoid.Any' (from "Data.Monoid"), and 'GHC.Exts.Any' (from "GHC.Exts").
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (Any (Flip (<) 5) [0,1,2,3,4,5])
    -- Eval (Any (Flip (<) 5) [0,1,2,3,4,5]) :: Bool
    -- = True
    --
    -- >>> :kind! Eval (Any (Flip (<) 0) [0,1,2,3,4,5])
    -- Eval (Any (Flip (<) 0) [0,1,2,3,4,5]) :: Bool
    -- = False
    data Any :: (a -> Exp Bool) -> t a -> Exp Bool
    type instance Eval (Any p lst) = Eval (Foldr (Bicomap p Pure (||)) 'False lst)

    -- | Sum a @Nat@-list.
    --
    -- === __Example__
    --
    -- >>> :kind! Eval (Sum '[1,2,3])
    -- Eval (Sum '[1,2,3]) :: Natural
    -- = 6
    data Sum :: t Nat -> Exp Nat
    type instance Eval (Sum ns) = Eval (Foldr (+) 0 ns)

    -- | Concatenate a collection of elements from a monoid.
    --
    -- === __Example__
    --
    -- For example, fold a list of lists.
    --
    -- > Concat :: [[a]] -> Exp [a]
    --
    -- >>> :kind! Eval (Concat ([[1,2], [3,4], [5,6]]))
    -- Eval (Concat ([[1,2], [3,4], [5,6]])) :: [Natural]
    -- = [1, 2, 3, 4, 5, 6]
    -- >>> :kind! Eval (Concat ([[Int, Maybe Int], [Maybe String, Either Double Int]]))
    -- Eval (Concat ([[Int, Maybe Int], [Maybe String, Either Double Int]])) :: [*]
    -- = [Int, Maybe Int, Maybe [Char], Either Double Int]
    --
    data Concat :: t m -> Exp m
    type instance Eval (Concat xs) = Eval (FoldMap Pure xs)

    -- | Map a function and concatenate the results.
    --
    -- This is 'FoldMap' specialized to the list monoid.
    data ConcatMap :: (a -> Exp [b]) -> t a -> Exp [b]
    type instance Eval (ConcatMap f xs) = Eval (FoldMap f xs)