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