packages feed

constrained (empty) → 0.1

raw patch · 6 files changed

+1585/−0 lines, 6 filesdep +base

Dependencies added: base

Files

+ LICENSE view
@@ -0,0 +1,26 @@+Copyright (c) 2019 Sergey Vinokurov++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright+   notice, this list of conditions and the following disclaimer in the+   documentation and/or other materials provided with the distribution.++This software is provided by the copyright holders and contributors+"as is" and any express or implied warranties, including, but not+limited to, the implied warranties of merchantability and fitness for+a particular purpose are disclaimed. In no event shall the authors or+contributors be liable for any direct, indirect, incidental, special,+exemplary, or consequential damages (including, but not limited to,+procurement of substitute goods or services; loss of use, data, or+profits; or business interruption) however caused and on any theory of+liability, whether in contract, strict liability, or tort (including+negligence or otherwise) arising in any way out of the use of this+software, even if advised of the possibility of such damage.
+ constrained.cabal view
@@ -0,0 +1,63 @@+cabal-version:+  2.0+name:+  constrained+version:+  0.1+synopsis:+  Generalization of standard Functor, Foldable, and Traversable classes+description:+  This package generalizes familiar 'Functor', 'Foldable' and 'Traversable'+  for the case when a functorial type of kind Type -> Type imposes certain constraints+  on what can be put in. E.g. 'Set' can only deal with types that are an instance of 'Ord'+  and therefore cannot be made an instance of 'Functor'. But it can be made+  an instance of a constrained functor with a similar interface that this+  package provides.+license:+  BSD2+license-file:+  LICENSE+author:+  Sergey Vinokurov+maintainer:+  Sergey Vinokurov <serg.foo@gmail.com>+tested-with:+  GHC == 8.2.2, GHC == 8.4.4, GHC == 8.6.5, GHC == 8.8.1+category: Data++build-type:+  Simple++library+  exposed-modules:+    Data.Constrained+    Data.Foldable.Constrained+    Data.Functor.Constrained+    Data.Traversable.Constrained+  hs-source-dirs:+    src+  build-depends:+    -- -- 7.4.1 instroduced ConstraintKind - base 4.5+    -- base >= 4.5+    -- 4.8 introduced extra functions in Foldable+    base >= 4.8 && < 5+  default-language:+    Haskell2010+  ghc-options:+    -Wall+    -fwarn-name-shadowing+    -fno-warn-type-defaults+  if impl(ghc >= 8.0)+    ghc-options:+      -Wall-missed-specialisations+      -Wcompat+      -Whi-shadowing+      -Widentities+      -Wincomplete-record-updates+      -Wincomplete-uni-patterns+      -Wmissing-exported-signatures+  if impl(ghc >= 8.2)+    ghc-options:+      -Wcpp-undef+      -Wmissing-home-modules+      -Wunbanged-strict-patterns
+ src/Data/Constrained.hs view
@@ -0,0 +1,122 @@+----------------------------------------------------------------------------+-- |+-- Module      :  Data.Constrained+-- Copyright   :  (c) Sergey Vinokurov 2019+-- License     :  BSD-2 (see LICENSE)+-- Maintainer  :  sergey@debian+----------------------------------------------------------------------------++{-# LANGUAGE CPP                     #-}+{-# LANGUAGE ConstraintKinds         #-}+{-# LANGUAGE FlexibleInstances       #-}+{-# LANGUAGE MultiParamTypeClasses   #-}+{-# LANGUAGE PolyKinds               #-}+{-# LANGUAGE TypeFamilies            #-}+{-# LANGUAGE UndecidableInstances    #-}+{-# LANGUAGE UndecidableSuperClasses #-}++module Data.Constrained+  ( Constrained(..)+  , NoConstraints+  , UnionConstraints+  , ComposeConstraints+  ) where++import Control.Applicative (ZipList(..))+import Data.Functor.Compose (Compose(..))+import Data.Functor.Const (Const(..))+import Data.Functor.Identity (Identity(..))+import Data.Functor.Product (Product(..))+import Data.Functor.Sum (Sum(..))+import Data.Kind+import Data.List.NonEmpty (NonEmpty(..))+import qualified Data.Monoid as Monoid+import qualified Data.Semigroup as Semigroup++-- | Specification of constrains that a functor might impose on its elements.+-- For example, sets typically require that their elements are ordered and+-- unboxed vectors require elements to have an instance of special class+-- that allows them to be packed in memory.+--+-- NB The 'Constraints' type family is associated with a typeclass in+-- order to improve type inference. Whenever a typeclass constraint+-- will be present, instance is guaranteed to exist and typechecker is+-- going to take advantage of that.+class Constrained (f :: k2 -> k1) where+  type Constraints (f :: k2 -> k1) :: k2 -> Constraint++-- | Used to specify values for 'Constraints' type family to indicate+-- absence of any constraints (i.e. empty 'Constraint').+class NoConstraints (a :: k)+instance NoConstraints a++-- | Combine constraints of two functors together to form a bigger set+-- of constraints.+class (Constraints f a, Constraints g a) => UnionConstraints (f :: k1 -> k2) (g :: k1 -> k2) (a :: k1)+instance (Constraints f a, Constraints g a) => UnionConstraints f g a++-- | Combine constraints for a case when one functors contains the other one.+class (Constraints f (g a), Constraints g a) => ComposeConstraints (f :: k2 -> k1) (g :: k3 -> k2) (a :: k3)+instance (Constraints f (g a), Constraints g a) => ComposeConstraints f g a++instance Constrained [] where+  type Constraints [] = NoConstraints++instance Constrained NonEmpty where+  type Constraints NonEmpty = NoConstraints++instance Constrained Identity where+  type Constraints Identity = NoConstraints++instance Constrained ((,) a) where+  type Constraints ((,) a) = NoConstraints++instance Constrained Maybe where+  type Constraints Maybe = NoConstraints++instance Constrained (Either a) where+  type Constraints (Either a) = NoConstraints++instance Constrained (Const a) where+  type Constraints (Const a) = NoConstraints++instance Constrained ZipList where+  type Constraints ZipList = NoConstraints++instance Constrained Semigroup.Min where+  type Constraints Semigroup.Min = NoConstraints++instance Constrained Semigroup.Max where+  type Constraints Semigroup.Max = NoConstraints++instance Constrained Semigroup.First where+  type Constraints Semigroup.First = NoConstraints++instance Constrained Semigroup.Last where+  type Constraints Semigroup.Last = NoConstraints++instance Constrained Semigroup.Dual where+  type Constraints Semigroup.Dual = NoConstraints++instance Constrained Semigroup.Sum where+  type Constraints Semigroup.Sum = NoConstraints++instance Constrained Semigroup.Product where+  type Constraints Semigroup.Product = NoConstraints++#if MIN_VERSION_base(4,12,0)+instance Constrained f => Constrained (Monoid.Ap f) where+  type Constraints (Monoid.Ap f) = Constraints f+#endif++instance Constrained f => Constrained (Monoid.Alt f) where+  type Constraints (Monoid.Alt f) = Constraints f++instance (Constrained f, Constrained g) => Constrained (Compose f g) where+  type Constraints (Compose f g) = ComposeConstraints f g++instance (Constrained f, Constrained g) => Constrained (Product f g) where+  type Constraints (Product f g) = UnionConstraints f g++instance (Constrained f, Constrained g) => Constrained (Sum f g) where+  type Constraints (Sum f g) = UnionConstraints f g
+ src/Data/Foldable/Constrained.hs view
@@ -0,0 +1,1063 @@+----------------------------------------------------------------------------+-- |+-- Module      :  Data.Foldable.Constrained+-- Copyright   :  (c) Sergey Vinokurov 2019+-- License     :  BSD-2 (see LICENSE)+-- Maintainer  :  sergey@debian+----------------------------------------------------------------------------++{-# LANGUAGE BangPatterns        #-}+{-# LANGUAGE CPP                 #-}+{-# LANGUAGE InstanceSigs        #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeFamilies        #-}++module Data.Foldable.Constrained+  ( CFoldable(..)+  , cfoldrM+  , cfoldlM+  , ctraverse_+  , cfor_+  , cmapM_+  , cforM_+  , csequenceA_+  , csequence_+  , casum+  , cmsum+  , cconcat+  , cconcatMap+  , cand+  , cor+  , cany+  , call+  , cmaximumBy+  , cminimumBy+  , cnotElem+  , cfind+  , module Data.Constrained+  ) where++import Prelude+  (Bool(..), id, (.), Int, Eq(..), Num(..), ($), ($!), flip, errorWithoutStackTrace, not)++import Control.Applicative+import Control.Monad hiding (mapM_)+import Data.Coerce+import Data.Either+import qualified Data.Foldable as F+import Data.Functor.Compose (Compose(..))+import Data.Functor.Identity (Identity(..))+import Data.Functor.Product as Product+import Data.Functor.Sum as Sum+import Data.List.NonEmpty (NonEmpty(..))+import Data.Maybe+import Data.Monoid+import qualified Data.Monoid as Monoid+import Data.Ord+import Data.Semigroup (Max(..), Min(..), Option(..))+import qualified Data.Semigroup as Semigroup+import GHC.Base (build)++import Data.Constrained (Constrained(..))++-- | Like 'Data.Foldable.Foldable' but allows elements to have constraints on them.+-- Laws are the same.+class Constrained f => CFoldable f where+  {-# MINIMAL cfoldMap | cfoldr #-}++  -- | Combine the elements of a structure using a monoid.+  cfold :: (Monoid m, Constraints f m) => f m -> m+  cfold = cfoldMap id+  {-# INLINABLE cfold #-}++  -- | Map each element of the structure to a monoid,+  -- and combine the results.+  cfoldMap :: (Monoid m, Constraints f a) => (a -> m) -> f a -> m+  cfoldMap f = cfoldr (mappend . f) mempty+  -- This INLINE allows more list functions to fuse. See Trac #9848.+  {-# INLINE cfoldMap #-}++  -- | Right-associative fold of a structure.+  --+  -- In the case of lists, 'cfoldr', when applied to a binary operator, a+  -- starting value (typically the right-identity of the operator), and a+  -- list, reduces the list using the binary operator, from right to left:+  --+  -- > cfoldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)+  --+  -- Note that, since the head of the resulting expression is produced by+  -- an application of the operator to the first element of the list,+  -- 'cfoldr' can produce a terminating expression from an infinite list.+  --+  -- For a general 'CFoldable' structure this should be semantically identical+  -- to,+  --+  -- @cfoldr f z = 'List.foldr' f z . 'ctoList'@+  --+  cfoldr :: Constraints f a => (a -> b -> b) -> b -> f a -> b+  cfoldr f z t = appEndo (cfoldMap (Endo . f) t) z++  -- | Right-associative fold of a structure, but with strict application of+  -- the operator.+  --+  cfoldr' :: Constraints f a => (a -> b -> b) -> b -> f a -> b+  cfoldr' f z0 xs = cfoldl f' id xs z0+    where+      f' k x z = k $! f x z++  -- | Left-associative fold of a structure.+  --+  -- In the case of lists, 'cfoldl', when applied to a binary+  -- operator, a starting value (typically the left-identity of the operator),+  -- and a list, reduces the list using the binary operator, from left to+  -- right:+  --+  -- > cfoldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn+  --+  -- Note that to produce the outermost application of the operator the+  -- entire input list must be traversed. This means that 'cfoldl'' will+  -- diverge if given an infinite list.+  --+  -- Also note that if you want an efficient left-fold, you probably want to+  -- use 'cfoldl'' instead of 'cfoldl'. The reason for this is that latter does+  -- not force the "inner" results (e.g. @z `f` x1@ in the above example)+  -- before applying them to the operator (e.g. to @(`f` x2)@). This results+  -- in a thunk chain @O(n)@ elements long, which then must be evaluated from+  -- the outside-in.+  --+  -- For a general 'CFoldable' structure this should be semantically identical+  -- to,+  --+  -- @cfoldl f z = 'List.foldl' f z . 'ctoList'@+  --+  cfoldl :: Constraints f a => (b -> a -> b) -> b -> f a -> b+  cfoldl f z t = appEndo (getDual (cfoldMap (Dual . Endo . flip f) t)) z+  -- There's no point mucking around with coercions here,+  -- because flip forces us to build a new function anyway.++  -- | Left-associative fold of a structure but with strict application of+  -- the operator.+  --+  -- This ensures that each step of the fold is forced to weak head normal+  -- form before being applied, avoiding the collection of thunks that would+  -- otherwise occur. This is often what you want to strictly reduce a finite+  -- list to a single, monolithic result (e.g. 'clength').+  --+  -- For a general 'CFoldable' structure this should be semantically identical+  -- to,+  --+  -- @cfoldl f z = 'List.foldl'' f z . 'ctoList'@+  --+  cfoldl' :: Constraints f a => (b -> a -> b) -> b -> f a -> b+  cfoldl' f z0 xs = cfoldr f' id xs z0+    where+      f' x k z = k $! f z x++  -- | A variant of 'cfoldr' that has no base case,+  -- and thus may only be applied to non-empty structures.+  --+  -- @'cfoldr1' f = 'List.foldr1' f . 'ctoList'@+  cfoldr1 :: Constraints f a => (a -> a -> a) -> f a -> a+  cfoldr1 f xs =+    fromMaybe (errorWithoutStackTrace "foldr1: empty structure")+      (cfoldr mf Nothing xs)+    where+      mf x m = Just $ case m of+        Nothing -> x+        Just y  -> f x y++  -- | A variant of 'cfoldl' that has no base case,+  -- and thus may only be applied to non-empty structures.+  --+  -- @'cfoldl1' f = 'List.foldl1' f . 'ctoList'@+  cfoldl1 :: Constraints f a => (a -> a -> a) -> f a -> a+  cfoldl1 f xs =+    fromMaybe (errorWithoutStackTrace "foldl1: empty structure")+      (cfoldl mf Nothing xs)+    where+      mf m y = Just $ case m of+        Nothing -> y+        Just x  -> f x y++  -- | List of elements of a structure, from left to right.+  ctoList :: Constraints f a => f a -> [a]+  ctoList t = build (\ c n -> cfoldr c n t)+  {-# INLINE ctoList #-}++  -- | Test whether the structure is empty. The default implementation is+  -- optimized for structures that are similar to cons-lists, because there+  -- is no general way to do better.+  cnull :: Constraints f a => f a -> Bool+  cnull = cfoldr (\_ _ -> False) True+  {-# INLINE cnull #-}++  -- | Returns the size/length of a finite structure as an 'Int'.  The+  -- default implementation is optimized for structures that are similar to+  -- cons-lists, because there is no general way to do better.+  clength :: Constraints f a => f a -> Int+  clength = cfoldl' (\c _ -> c + 1) 0++  -- | Does the element occur in the structure?+  celem :: (Eq a, Constraints f a) => a -> f a -> Bool+  celem = cany . (==)+  {-# INLINE celem #-}++  -- | The largest element of a non-empty structure.+  cmaximum :: forall a. (Ord a, Constraints f a) => f a -> a+  cmaximum+    = maybe (errorWithoutStackTrace "maximum: empty structure") getMax+    . getOption+    . cfoldMap (Option . Just . Max)+  {-# INLINABLE cmaximum #-}++  -- | The least element of a non-empty structure.+  cminimum :: forall a. (Ord a, Constraints f a) => f a -> a+  cminimum+    = maybe (errorWithoutStackTrace "maximum: empty structure") getMin+    . getOption+    . cfoldMap (Option . Just . Min)+  {-# INLINABLE cminimum #-}++  -- | The 'csum' function computes the sum of the numbers of a structure.+  csum :: (Num a, Constraints f a) => f a -> a+  csum = getSum . cfoldMap Sum+  {-# INLINABLE csum #-}++  -- | The 'cproduct' function computes the product of the numbers of a+  -- structure.+  cproduct :: (Num a, Constraints f a) => f a -> a+  cproduct = getProduct . cfoldMap Product+  {-# INLINABLE cproduct #-}+++-- | Monadic fold over the elements of a structure,+-- associating to the right, i.e. from right to left.+cfoldrM :: (CFoldable f, Monad m, Constraints f a) => (a -> b -> m b) -> b -> f a -> m b+cfoldrM f z0 xs = cfoldl f' return xs z0+  where+    f' k x z = f x z >>= k++-- | Monadic fold over the elements of a structure,+-- associating to the left, i.e. from left to right.+cfoldlM :: (CFoldable f, Monad m, Constraints f a) => (b -> a -> m b) -> b -> f a -> m b+cfoldlM f z0 xs = cfoldr f' return xs z0+  where+    f' x k z = f z x >>= k++-- | Map each element of a structure to an action, evaluate these+-- actions from left to right, and ignore the results. For a version+-- that doesn't ignore the results see 'Data.Traversable.traverse'.+ctraverse_ :: (CFoldable f, Applicative f, Constraints f a) => (a -> f b) -> f a -> f ()+ctraverse_ f = cfoldr ((*>) . f) (pure ())++-- | 'cfor_' is 'ctraverse_' with its arguments flipped. For a version+-- that doesn't ignore the results see 'Data.Traversable.Constrained.cfor'.+--+-- >>> for_ [1..4] print+-- 1+-- 2+-- 3+-- 4+cfor_ :: (CFoldable f, Applicative f, Constraints f a) => f a -> (a -> f b) -> f ()+{-# INLINE cfor_ #-}+cfor_ = flip ctraverse_++-- | Map each element of a structure to a monadic action, evaluate+-- these actions from left to right, and ignore the results. For a+-- version that doesn't ignore the results see+-- 'Data.Traversable.mapM'.+cmapM_ :: (CFoldable f, Monad m, Constraints f a) => (a -> m b) -> f a -> m ()+cmapM_ f = cfoldr ((>>) . f) (return ())++-- | 'cforM_' is 'cmapM_' with its arguments flipped. For a version that+-- doesn't ignore the results see 'Data.Traversable.forM'.+cforM_ :: (CFoldable f, Monad m, Constraints f a) => f a -> (a -> m b) -> m ()+{-# INLINE cforM_ #-}+cforM_ = flip cmapM_++-- | Evaluate each action in the structure from left to right, and+-- ignore the results. For a version that doesn't ignore the results+-- see 'Data.Traversable.sequenceA'.+csequenceA_ :: (CFoldable f, Applicative m, Constraints f (m a)) => f (m a) -> m ()+csequenceA_ = cfoldr (*>) (pure ())++-- | Evaluate each monadic action in the structure from left to right,+-- and ignore the results. For a version that doesn't ignore the+-- results see 'Data.Traversable.sequence'.+csequence_ :: (CFoldable f, Monad m, Constraints f a, Constraints f (m a)) => f (m a) -> m ()+csequence_ = cfoldr (>>) (return ())++-- | The sum of a collection of actions, generalizing 'Data.Foldable.concat'.+--+-- asum [Just "Hello", Nothing, Just "World"]+-- Just "Hello"+casum :: (CFoldable f, Alternative m, Constraints f (m a)) => f (m a) -> m a+{-# INLINE casum #-}+casum = cfoldr (<|>) empty++-- | The sum of a collection of actions, generalizing 'Data.Foldable.concat'.+cmsum :: (CFoldable f, MonadPlus m, Constraints f (m a)) => f (m a) -> m a+{-# INLINE cmsum #-}+cmsum = casum++-- | The concatenation of all the elements of a container of lists.+cconcat :: (CFoldable f, Constraints f [a]) => f [a] -> [a]+cconcat xs = build (\c n -> cfoldr (\x y -> cfoldr c y x) n xs)+{-# INLINE cconcat #-}++-- | Map a function over all the elements of a container and concatenate+-- the resulting lists.+cconcatMap :: (CFoldable f, Constraints f a) => (a -> [b]) -> f a -> [b]+cconcatMap f xs = build (\c n -> cfoldr (\x b -> cfoldr c b (f x)) n xs)+{-# INLINE cconcatMap #-}++-- These use foldr rather than cfoldMap to avoid repeated concatenation.++-- | 'cand' returns the conjunction of a container of Bools.  For the+-- result to be 'True', the container must be finite; 'False', however,+-- results from a 'False' value finitely far from the left end.+cand :: (CFoldable f, Constraints f Bool) => f Bool -> Bool+cand = getAll . cfoldMap All++-- | 'cor' returns the disjunction of a container of Bools.  For the+-- result to be 'False', the container must be finite; 'True', however,+-- results from a 'True' value finitely far from the left end.+cor :: (CFoldable f, Constraints f Bool) => f Bool -> Bool+cor = getAny . cfoldMap Any++-- | Determines whether any element of the structure satisfies the predicate.+cany :: (CFoldable f, Constraints f a) => (a -> Bool) -> f a -> Bool+cany p = getAny . cfoldMap (Any . p)++-- | Determines whether all elements of the structure satisfy the predicate.+call :: (CFoldable f, Constraints f a) => (a -> Bool) -> f a -> Bool+call p = getAll . cfoldMap (All . p)++-- | The largest element of a non-empty structure with respect to the+-- given comparison function.++-- See Note [maximumBy/minimumBy space usage]+cmaximumBy :: (CFoldable f, Constraints f a) => (a -> a -> Ordering) -> f a -> a+cmaximumBy cmp = cfoldl1 max'+  where+    max' x y = case cmp x y of+      GT -> x+      _  -> y++-- | The least element of a non-empty structure with respect to the+-- given comparison function.++-- See Note [maximumBy/minimumBy space usage]+cminimumBy :: (CFoldable f, Constraints f a) => (a -> a -> Ordering) -> f a -> a+cminimumBy cmp = cfoldl1 min'+  where+    min' x y = case cmp x y of+     GT -> y+     _  -> x++-- | 'cnotElem' is the negation of 'celem'.+cnotElem :: (CFoldable f, Eq a, Constraints f a) => a -> f a -> Bool+cnotElem x = not . celem x++-- | The 'cfind' function takes a predicate and a structure and returns+-- the leftmost element of the structure matching the predicate, or+-- 'Nothing' if there is no such element.+cfind :: (CFoldable f, Constraints f a) => (a -> Bool) -> f a -> Maybe a+cfind p = getFirst . cfoldMap (\ x -> First (if p x then Just x else Nothing))++{-+Note [maximumBy/minimumBy space usage]+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+When the type signatures of maximumBy and minimumBy were generalized to work+over any Foldable instance (instead of just lists), they were defined using+foldr1. This was problematic for space usage, as the semantics of maximumBy+and minimumBy essentially require that they examine every element of the+data structure. Using foldr1 to examine every element results in space usage+proportional to the size of the data structure. For the common case of lists,+this could be particularly bad (see Trac #10830).++For the common case of lists, switching the implementations of maximumBy and+minimumBy to foldl1 solves the issue, as GHC's strictness analysis can then+make these functions only use O(1) stack space. It is perhaps not the optimal+way to fix this problem, as there are other conceivable data structures+(besides lists) which might benefit from specialized implementations for+maximumBy and minimumBy (see+https://ghc.haskell.org/trac/ghc/ticket/10830#comment:26 for a further+discussion). But using foldl1 is at least always better than using foldr1, so+GHC has chosen to adopt that approach for now.+-}+++instance CFoldable [] where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable NonEmpty where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable Identity where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable ((,) a) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable Maybe where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable (Either a) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable (Const a) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable ZipList where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable Semigroup.Min where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product+++instance CFoldable Semigroup.Max where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product+++instance CFoldable Semigroup.First where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product+++instance CFoldable Semigroup.Last where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product+++instance CFoldable Semigroup.Dual where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product+++instance CFoldable Semigroup.Sum where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++instance CFoldable Semigroup.Product where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold    = F.fold+  cfoldMap = F.foldMap+  cfoldr   = F.foldr+  cfoldr'  = F.foldr'+  cfoldl   = F.foldl+  cfoldl'  = F.foldl'+  cfoldr1  = F.foldr1+  cfoldl1  = F.foldl1+  ctoList  = F.toList+  cnull    = F.null+  clength  = F.length+  celem    = F.elem+  cmaximum = F.maximum+  cminimum = F.minimum+  csum     = F.sum+  cproduct = F.product++#if MIN_VERSION_base(4,12,0)+instance CFoldable f => CFoldable (Monoid.Ap f) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold :: forall a. (Monoid a, Constraints (Monoid.Ap f) a) => Monoid.Ap f a -> a+  cfold = coerce (cfold :: f a -> a)+  cfoldMap :: forall a b. (Monoid b, Constraints (Monoid.Ap f) a) => (a -> b) -> Monoid.Ap f a -> b+  cfoldMap = coerce (cfoldMap :: (a -> b) -> f a -> b)+  cfoldr :: forall a b. Constraints (Monoid.Ap f) a => (a -> b -> b) -> b -> Monoid.Ap f a -> b+  cfoldr = coerce (cfoldr :: (a -> b -> b) -> b -> f a -> b)+  cfoldr' :: forall a b. Constraints (Monoid.Ap f) a => (a -> b -> b) -> b -> Monoid.Ap f a -> b+  cfoldr' = coerce (cfoldr' :: (a -> b -> b) -> b -> f a -> b)+  cfoldl :: forall a b. Constraints (Monoid.Ap f) a => (b -> a -> b) -> b -> Monoid.Ap f a -> b+  cfoldl = coerce (cfoldl :: (b -> a -> b) -> b -> f a -> b)+  cfoldl' :: forall a b. Constraints (Monoid.Ap f) a => (b -> a -> b) -> b -> Monoid.Ap f a -> b+  cfoldl' = coerce (cfoldl' :: (b -> a -> b) -> b -> f a -> b)+  cfoldr1 :: forall a. Constraints (Monoid.Ap f) a => (a -> a -> a) -> Monoid.Ap f a -> a+  cfoldr1 = coerce (cfoldr1 :: (a -> a -> a) -> f a -> a)+  cfoldl1 :: forall a. Constraints (Monoid.Ap f) a => (a -> a -> a) -> Monoid.Ap f a -> a+  cfoldl1 = coerce (cfoldl1 :: (a -> a -> a) -> f a -> a)+  ctoList :: forall a. Constraints (Monoid.Ap f) a => Monoid.Ap f a -> [a]+  ctoList = coerce (ctoList :: f a -> [a])+  cnull :: forall a. Constraints (Monoid.Ap f) a => Monoid.Ap f a -> Bool+  cnull = coerce (cnull :: f a -> Bool)+  clength :: forall a. Constraints (Monoid.Ap f) a => Monoid.Ap f a -> Int+  clength = coerce (clength :: f a -> Int)+  celem :: forall a. (Eq a, Constraints (Monoid.Ap f) a) => a -> Monoid.Ap f a -> Bool+  celem = coerce (celem :: a -> f a -> Bool)+  cmaximum :: forall a. (Ord a, Constraints (Monoid.Ap f) a) => Monoid.Ap f a -> a+  cmaximum = coerce (cmaximum :: f a -> a)+  cminimum :: forall a. (Ord a, Constraints (Monoid.Ap f) a) => Monoid.Ap f a -> a+  cminimum = coerce (cminimum :: f a -> a)+  csum :: forall a. (Num a, Constraints (Monoid.Ap f) a) => Monoid.Ap f a -> a+  csum = coerce (csum :: f a -> a)+  cproduct :: forall a. (Num a, Constraints (Monoid.Ap f) a) => Monoid.Ap f a -> a+  cproduct = coerce (cproduct :: f a -> a)+#endif++instance CFoldable f => CFoldable (Monoid.Alt f) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  {-# INLINE ctoList  #-}+  {-# INLINE cnull    #-}+  {-# INLINE clength  #-}+  {-# INLINE celem    #-}+  {-# INLINE cmaximum #-}+  {-# INLINE cminimum #-}+  {-# INLINE csum     #-}+  {-# INLINE cproduct #-}+  cfold :: forall a. (Monoid a, Constraints (Monoid.Alt f) a) => Monoid.Alt f a -> a+  cfold = coerce (cfold :: f a -> a)+  cfoldMap :: forall a b. (Monoid b, Constraints (Monoid.Alt f) a) => (a -> b) -> Monoid.Alt f a -> b+  cfoldMap = coerce (cfoldMap :: (a -> b) -> f a -> b)+  cfoldr :: forall a b. Constraints (Monoid.Alt f) a => (a -> b -> b) -> b -> Monoid.Alt f a -> b+  cfoldr = coerce (cfoldr :: (a -> b -> b) -> b -> f a -> b)+  cfoldr' :: forall a b. Constraints (Monoid.Alt f) a => (a -> b -> b) -> b -> Monoid.Alt f a -> b+  cfoldr' = coerce (cfoldr' :: (a -> b -> b) -> b -> f a -> b)+  cfoldl :: forall a b. Constraints (Monoid.Alt f) a => (b -> a -> b) -> b -> Monoid.Alt f a -> b+  cfoldl = coerce (cfoldl :: (b -> a -> b) -> b -> f a -> b)+  cfoldl' :: forall a b. Constraints (Monoid.Alt f) a => (b -> a -> b) -> b -> Monoid.Alt f a -> b+  cfoldl' = coerce (cfoldl' :: (b -> a -> b) -> b -> f a -> b)+  cfoldr1 :: forall a. Constraints (Monoid.Alt f) a => (a -> a -> a) -> Monoid.Alt f a -> a+  cfoldr1 = coerce (cfoldr1 :: (a -> a -> a) -> f a -> a)+  cfoldl1 :: forall a. Constraints (Monoid.Alt f) a => (a -> a -> a) -> Monoid.Alt f a -> a+  cfoldl1 = coerce (cfoldl1 :: (a -> a -> a) -> f a -> a)+  ctoList :: forall a. Constraints (Monoid.Alt f) a => Monoid.Alt f a -> [a]+  ctoList = coerce (ctoList :: f a -> [a])+  cnull :: forall a. Constraints (Monoid.Alt f) a => Monoid.Alt f a -> Bool+  cnull = coerce (cnull :: f a -> Bool)+  clength :: forall a. Constraints (Monoid.Alt f) a => Monoid.Alt f a -> Int+  clength = coerce (clength :: f a -> Int)+  celem :: forall a. (Eq a, Constraints (Monoid.Alt f) a) => a -> Monoid.Alt f a -> Bool+  celem = coerce (celem :: a -> f a -> Bool)+  cmaximum :: forall a. (Ord a, Constraints (Monoid.Alt f) a) => Monoid.Alt f a -> a+  cmaximum = coerce (cmaximum :: f a -> a)+  cminimum :: forall a. (Ord a, Constraints (Monoid.Alt f) a) => Monoid.Alt f a -> a+  cminimum = coerce (cminimum :: f a -> a)+  csum :: forall a. (Num a, Constraints (Monoid.Alt f) a) => Monoid.Alt f a -> a+  csum = coerce (csum :: f a -> a)+  cproduct :: forall a. (Num a, Constraints (Monoid.Alt f) a) => Monoid.Alt f a -> a+  cproduct = coerce (cproduct :: f a -> a)++instance (CFoldable f, CFoldable g) => CFoldable (Compose f g) where+  {-# INLINABLE cfold    #-}+  {-# INLINABLE cfoldMap #-}+  {-# INLINABLE cfoldr   #-}+  cfold      = cfoldMap cfold . getCompose+  cfoldMap f = cfoldMap (cfoldMap f) . getCompose+  cfoldr f z = cfoldr (\ga acc -> cfoldr f acc ga) z . getCompose++instance (CFoldable f, CFoldable g) => CFoldable (Product.Product f g) where+  {-# INLINABLE cfold    #-}+  {-# INLINABLE cfoldMap #-}+  {-# INLINABLE cfoldr   #-}+  {-# INLINABLE cfoldr'  #-}+  {-# INLINABLE cfoldl   #-}+  {-# INLINABLE cfoldl'  #-}+  {-# INLINABLE cfoldr1  #-}+  {-# INLINABLE cfoldl1  #-}+  cfold       (Pair x y) = cfold x <> cfold y+  cfoldMap f  (Pair x y) = cfoldMap f x <> cfoldMap f y+  cfoldr f z  (Pair x y) = cfoldr f (cfoldr f z y) x+  cfoldr' f z (Pair x y) = cfoldr' f y' x+    where+      !y' = cfoldr' f z y+  cfoldl f z  (Pair x y) = cfoldl f (cfoldl f z y) x+  cfoldl' f z (Pair x y) = cfoldl' f x' x+    where+      !x' = cfoldl' f z y+  cfoldr1 f   (Pair x y) = cfoldl1 f x `f` cfoldl1 f y+  cfoldl1 f   (Pair x y) = cfoldr1 f y `f` cfoldr1 f x++instance (CFoldable f, CFoldable g) => CFoldable (Sum.Sum f g) where+  {-# INLINE cfold    #-}+  {-# INLINE cfoldMap #-}+  {-# INLINE cfoldr   #-}+  {-# INLINE cfoldr'  #-}+  {-# INLINE cfoldl   #-}+  {-# INLINE cfoldl'  #-}+  {-# INLINE cfoldr1  #-}+  {-# INLINE cfoldl1  #-}+  cfold       (InL x) = cfold x+  cfold       (InR y) = cfold y+  cfoldMap f  (InL x) = cfoldMap f x+  cfoldMap f  (InR y) = cfoldMap f y+  cfoldr f z  (InL x) = cfoldr f z x+  cfoldr f z  (InR y) = cfoldr f z y+  cfoldr' f z (InL x) = cfoldr' f z x+  cfoldr' f z (InR y) = cfoldr' f z y+  cfoldl f z  (InL x) = cfoldl f z x+  cfoldl f z  (InR y) = cfoldl f z y+  cfoldl' f z (InL x) = cfoldl' f z x+  cfoldl' f z (InR y) = cfoldl' f z y+  cfoldr1 f   (InL x) = cfoldr1 f x+  cfoldr1 f   (InR y) = cfoldr1 f y+  cfoldl1 f   (InL x) = cfoldl1 f x+  cfoldl1 f   (InR y) = cfoldl1 f y
+ src/Data/Functor/Constrained.hs view
@@ -0,0 +1,154 @@+----------------------------------------------------------------------------+-- |+-- Module      :  Data.Functor.Constrained+-- Copyright   :  (c) Sergey Vinokurov 2019+-- License     :  BSD-2 (see LICENSE)+-- Maintainer  :  sergey@debian+----------------------------------------------------------------------------++{-# LANGUAGE CPP                 #-}+{-# LANGUAGE DefaultSignatures   #-}+{-# LANGUAGE InstanceSigs        #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeFamilies        #-}++module Data.Functor.Constrained+  ( CFunctor(..)+  , module Data.Constrained+  ) where++import Control.Applicative (ZipList(..))+import Data.Coerce+import Data.Functor.Compose (Compose(..))+import Data.Functor.Const (Const(..))+import Data.Functor.Identity (Identity(..))+import Data.Functor.Product (Product(..))+import Data.Functor.Sum (Sum(..))+import Data.List.NonEmpty (NonEmpty(..))+import qualified Data.Monoid as Monoid+import qualified Data.Semigroup as Semigroup++import Data.Constrained (Constrained(..), NoConstraints)++-- | Like 'Functor' but allows elements to have constraints on them.+-- Laws are the same:+--+-- > cmap id      == id+-- > cmap (f . g) == cmap f . cmap g+class Constrained f => CFunctor f where+  cmap :: (Constraints f a, Constraints f b) => (a -> b) -> f a -> f b++  {-# INLINE cmap_ #-}+  cmap_ :: (Constraints f a, Constraints f b) => a -> f b -> f a+  cmap_ = cmap . const++  {-# INLINE cmap #-}+  default cmap+    :: (Functor f, Constraints f a, Constraints f b)+    => (a -> b)+    -> f a+    -> f b+  cmap = fmap++instance CFunctor [] where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor NonEmpty where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Identity where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor ((,) a) where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Maybe where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor (Either a) where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor (Const a) where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor ZipList where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Min where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Max where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.First where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Last where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Dual where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Sum where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++instance CFunctor Semigroup.Product where+  {-# INLINE cmap_ #-}+  cmap_ = (<$)++#if MIN_VERSION_base(4,12,0)+instance CFunctor f => CFunctor (Monoid.Ap f) where+  {-# INLINE cmap #-}+  {-# INLINE cmap_ #-}+  cmap+    :: forall a b. (Constraints (Monoid.Ap f) a, Constraints (Monoid.Ap f) b)+    => (a -> b) -> Monoid.Ap f a -> Monoid.Ap f b+  cmap = coerce (cmap :: (a -> b) -> f a -> f b)++  cmap_+    :: forall a b. (Constraints (Monoid.Ap f) a, Constraints (Monoid.Ap f) b)+    => a -> Monoid.Ap f b -> Monoid.Ap f a+  cmap_ = coerce (cmap_ :: a -> f b -> f a)+#endif++instance CFunctor f => CFunctor (Monoid.Alt f) where+  {-# INLINE cmap #-}+  {-# INLINE cmap_ #-}+  cmap+    :: forall a b. (Constraints (Monoid.Alt f) a, Constraints (Monoid.Alt f) b)+    => (a -> b) -> Monoid.Alt f a -> Monoid.Alt f b+  cmap = coerce (cmap :: (a -> b) -> f a -> f b)++  cmap_+    :: forall a b. (Constraints (Monoid.Alt f) a, Constraints (Monoid.Alt f) b)+    => a -> Monoid.Alt f b -> Monoid.Alt f a+  cmap_ = coerce (cmap_ :: a -> f b -> f+   a)+++instance (CFunctor f, CFunctor g) => CFunctor (Compose f g) where+  {-# INLINE cmap #-}+  cmap f (Compose x) = Compose (cmap (cmap f) x)++instance (CFunctor f, CFunctor g) => CFunctor (Product f g) where+  {-# INLINE cmap #-}+  cmap f (Pair x y) = Pair (cmap f x) (cmap f y)++instance (CFunctor f, CFunctor g) => CFunctor (Sum f g) where+  {-# INLINE cmap #-}+  cmap f (InL x) = InL (cmap f x)+  cmap f (InR y) = InR (cmap f y)
+ src/Data/Traversable/Constrained.hs view
@@ -0,0 +1,157 @@+----------------------------------------------------------------------------+-- |+-- Module      :  Data.Traversable.Constrained+-- Copyright   :  (c) Sergey Vinokurov 2019+-- License     :  BSD-2 (see LICENSE)+-- Maintainer  :  sergey@debian+----------------------------------------------------------------------------++{-# LANGUAGE CPP                  #-}+{-# LANGUAGE ConstraintKinds      #-}+{-# LANGUAGE DefaultSignatures    #-}+{-# LANGUAGE FlexibleContexts     #-}+{-# LANGUAGE FlexibleInstances    #-}+{-# LANGUAGE KindSignatures       #-}+{-# LANGUAGE TypeFamilies         #-}+{-# LANGUAGE UndecidableInstances #-}++module Data.Traversable.Constrained+  ( CTraversable(..)+  , cfor+  , module Data.Constrained+  ) where++import Control.Applicative (ZipList(..))+import Data.Functor.Compose (Compose(..))+import Data.Functor.Const (Const(..))+import Data.Functor.Identity (Identity(..))+import Data.Functor.Product as Product+import Data.Functor.Sum (Sum(..))+import Data.List.NonEmpty (NonEmpty(..))+import qualified Data.Monoid as Monoid+import qualified Data.Semigroup as Semigroup++import Data.Constrained (Constrained(..))+import Data.Foldable.Constrained+import Data.Functor.Constrained++-- | Like 'Traversable' but allows elements to have constraints on them.+-- Laws are the same:+--+-- > ctraverse pure == pure+-- > ctraverse (f <=< g) == ctraverse f <=< ctraverse g+--+-- NB There's no aplicative version because Vectors from the+-- http://hackage.haskell.org/package/vector package only support+-- monadic traversals. Since they're one of the main motivation for+-- this package, 'Applicative' version of traversals will not exist.+class (CFunctor f, CFoldable f) => CTraversable f where+  ctraverse+    :: (Constraints f a, Constraints f b, Monad m)+    => (a -> m b) -> f a -> m (f b)++  {-# INLINE csequence #-}+  csequence+    :: (Constraints f a, Constraints f (m a), Monad m)+    => f (m a) -> m (f a)+  csequence = ctraverse id++  {-# INLINE ctraverse #-}+  default ctraverse+    :: (Constraints f a, Constraints f b, Monad m, Traversable f)+    => (a -> m b) -> f a -> m (f b)+  ctraverse = traverse++instance CTraversable [] where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable NonEmpty where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Identity where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable ((,) a) where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Maybe where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable (Either a) where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable (Const a) where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable ZipList where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Min where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Max where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.First where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Last where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Dual where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Sum where+  {-# INLINE csequence #-}+  csequence = sequenceA++instance CTraversable Semigroup.Product where+  {-# INLINE csequence #-}+  csequence = sequenceA++#if MIN_VERSION_base(4,12,0)+instance CTraversable f => CTraversable (Monoid.Ap f) where+  {-# INLINE ctraverse #-}+  {-# INLINE csequence #-}+  ctraverse f = fmap Monoid.Ap . ctraverse f . Monoid.getAp+  csequence = fmap Monoid.Ap . csequence . Monoid.getAp+#endif++instance CTraversable f => CTraversable (Monoid.Alt f) where+  {-# INLINE ctraverse #-}+  {-# INLINE csequence #-}+  ctraverse f = fmap Monoid.Alt . ctraverse f . Monoid.getAlt+  csequence = fmap Monoid.Alt . csequence . Monoid.getAlt++instance (CTraversable f, CTraversable g) => CTraversable (Compose f g) where+  {-# INLINABLE ctraverse #-}+  ctraverse f = fmap Compose . ctraverse (ctraverse f) . getCompose++instance (CTraversable f, CTraversable g) => CTraversable (Product f g) where+  {-# INLINABLE ctraverse #-}+  ctraverse f (Pair x y) = Pair <$> ctraverse f x <*> ctraverse f y++instance (CTraversable f, CTraversable g) => CTraversable (Sum f g) where+  {-# INLINABLE ctraverse #-}+  ctraverse f (InL x) = InL <$> ctraverse f x+  ctraverse f (InR y) = InR <$> ctraverse f y++{-# INLINE cfor #-}+-- | 'ctraverse' with araguments flipped.+cfor+  :: (CTraversable f, Constraints f a, Constraints f b, Monad m)+  => f a -> (a -> m b) -> m (f b)+cfor = flip ctraverse