implementation module Data.Foldable

from StdFunc import o, id, flip
from StdMisc import abort
import Control.Applicative
from Control.Monad import class Monad(..), >>=
from Data.List import instance Semigroup [a], instance Monoid [a], instance Foldable []
import Data.Monoid
import Data.Maybe
import StdClass
from StdOverloaded import class < (..)
from StdBool import not

instance Foldable (Const m)
where
	foldMap _ _ = mempty
	fold x = foldMap id x
	foldr f z t = appEndo (foldMap (Endo o f) t) z
	foldr` f z0 xs = foldl f` id xs z0
	where
		f` k x z = k (f x z)
	foldl f z t = appEndo (getDual (foldMap (Dual o Endo o flip f) t)) z
	foldl` f z0 xs = foldr f` id xs z0
	where
		f` x k z = k (f z x)
	foldr1 f xs = fromMaybe (abort "foldr1: empty structure\n") (foldr mf ?None xs)
	where
		mf x ?None = ?Just x
		mf x (?Just y) = ?Just (f x y)
	foldl1 f xs = fromMaybe (abort "foldl1: empty structure\n") (foldl mf ?None xs)
	where
		mf ?None y = ?Just y
		mf (?Just x) y = ?Just (f x y)

foldrM :: (a b -> m b) b !(t a) -> m b | Foldable t & Monad m
foldrM f z0 xs = foldl f` pure xs z0
  where f` k x z = f x z >>= k

foldlM :: (b a -> m b) b !(t a) -> m b | Foldable t & Monad m
foldlM f z0 xs = foldr f` pure xs z0
  where f` x k z = f z x >>= k

traverse_ :: (a -> f b) !(t a) -> f () | Foldable t & *> f
traverse_ f x = foldr ((*>) o f) (pure ()) x

mapM_ :: (a -> m b) !(t a) -> m () | Foldable t & Monad m
mapM_ f x = foldr ((\ma mb -> ma >>= \_ -> mb) o f) (pure ()) x

sequenceA_ :: !(t (f a)) -> f () | Foldable t & *> f
sequenceA_ x = foldr (*>) (pure ()) x

concat :: !(t [a]) -> [a] | Foldable t
concat x = fold x

concatMap :: (a -> [b]) !(t a) -> [b] | Foldable t
concatMap f x = foldMap f x

and :: !(t Bool) -> Bool | Foldable t
and x = getAll (foldMap All x)

or :: !(t Bool) -> Bool | Foldable t
or x = getAny (foldMap Any x)

any :: (a -> Bool) !(t a) -> Bool | Foldable t
any p x = getAny (foldMap (Any o p) x)

all :: (a -> Bool) !(t a) -> Bool | Foldable t
all p x = getAll (foldMap (All o p) x)

sum :: !(t a) -> a | Foldable t & + a & zero a
sum x = getSum (foldMap Sum x)

product :: !(t a) -> a | Foldable t & * a & one a
product x = getProduct (foldMap Product x)

maximum :: !(t a) -> a | Foldable t & Ord a
maximum x = foldr1 max x

maximumBy :: (a a -> Bool) !(t a) -> a | Foldable t
maximumBy cmp x = foldr1 max` x
  where max` x y = if (cmp x y) y x

minimum :: !(t a) -> a | Foldable t & Ord a
minimum x = foldr1 min x

minimumBy :: (a a -> Bool) !(t a) -> a | Foldable t
minimumBy cmp x = foldr1 min` x
  where min` x y = if (cmp x y) x y

elem :: a !(t a) -> Bool | Foldable t & == a
elem x y = any (\z -> x == z) y

notElem ::  a !(t a) -> Bool | Foldable t & == a
notElem x y = not (elem x y)

find :: (a -> Bool) !(t a) -> ?a | Foldable t
find p x = listToMaybe (concatMap (\x -> if (p x) [x] []) x)
