{-# 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)