{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeOperators #-}
module Data.Traversable (
Traversable(..),
for,
forM,
mapAccumL,
mapAccumR,
fmapDefault,
foldMapDefault,
) where
import Control.Applicative ( Const(..), ZipList(..) )
import Data.Coerce
import Data.Either ( Either(..) )
import Data.Foldable ( Foldable )
import Data.Functor
import Data.Functor.Identity ( Identity(..) )
import Data.Functor.Utils ( StateL(..), StateR(..) )
import Data.Monoid ( Dual(..), Sum(..), Product(..),
First(..), Last(..), Alt(..), Ap(..) )
import Data.Ord ( Down(..) )
import Data.Proxy ( Proxy(..) )
import GHC.Arr
import GHC.Base ( Applicative(..), Monad(..), Monoid, Maybe(..), NonEmpty(..),
($), (.), id, flip )
import GHC.Generics
import qualified GHC.List as List ( foldr )
class (Functor t, Foldable t) => Traversable t where
{-# MINIMAL traverse | sequenceA #-}
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
{-# INLINE traverse #-}
traverse f :: a -> f b
f = t (f b) -> f (t b)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA (t (f b) -> f (t b)) -> (t a -> t (f b)) -> t a -> f (t b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> t a -> t (f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> f b
f
sequenceA :: Applicative f => t (f a) -> f (t a)
{-# INLINE sequenceA #-}
sequenceA = (f a -> f a) -> t (f a) -> f (t a)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse f a -> f a
forall a. a -> a
id
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
{-# INLINE mapM #-}
mapM = (a -> m b) -> t a -> m (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse
sequence :: Monad m => t (m a) -> m (t a)
{-# INLINE sequence #-}
sequence = t (m a) -> m (t a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA
instance Traversable Maybe where
traverse :: (a -> f b) -> Maybe a -> f (Maybe b)
traverse _ Nothing = Maybe b -> f (Maybe b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe b
forall a. Maybe a
Nothing
traverse f :: a -> f b
f (Just x :: a
x) = b -> Maybe b
forall a. a -> Maybe a
Just (b -> Maybe b) -> f b -> f (Maybe b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x
instance Traversable [] where
{-# INLINE traverse #-}
traverse :: (a -> f b) -> [a] -> f [b]
traverse f :: a -> f b
f = (a -> f [b] -> f [b]) -> f [b] -> [a] -> f [b]
forall a b. (a -> b -> b) -> b -> [a] -> b
List.foldr a -> f [b] -> f [b]
cons_f ([b] -> f [b]
forall (f :: * -> *) a. Applicative f => a -> f a
pure [])
where cons_f :: a -> f [b] -> f [b]
cons_f x :: a
x ys :: f [b]
ys = (b -> [b] -> [b]) -> f b -> f [b] -> f [b]
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (:) (a -> f b
f a
x) f [b]
ys
instance Traversable NonEmpty where
traverse :: (a -> f b) -> NonEmpty a -> f (NonEmpty b)
traverse f :: a -> f b
f ~(a :: a
a :| as :: [a]
as) = (b -> [b] -> NonEmpty b) -> f b -> f [b] -> f (NonEmpty b)
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
(:|) (a -> f b
f a
a) ((a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f [a]
as)
instance Traversable (Either a) where
traverse :: (a -> f b) -> Either a a -> f (Either a b)
traverse _ (Left x :: a
x) = Either a b -> f (Either a b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Either a b
forall a b. a -> Either a b
Left a
x)
traverse f :: a -> f b
f (Right y :: a
y) = b -> Either a b
forall a b. b -> Either a b
Right (b -> Either a b) -> f b -> f (Either a b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
y
instance Traversable ((,) a) where
traverse :: (a -> f b) -> (a, a) -> f (a, b)
traverse f :: a -> f b
f (x :: a
x, y :: a
y) = (,) a
x (b -> (a, b)) -> f b -> f (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
y
instance Ix i => Traversable (Array i) where
traverse :: (a -> f b) -> Array i a -> f (Array i b)
traverse f :: a -> f b
f arr :: Array i a
arr = (i, i) -> [b] -> Array i b
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Array i a -> (i, i)
forall i e. Array i e -> (i, i)
bounds Array i a
arr) ([b] -> Array i b) -> f [b] -> f (Array i b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
`fmap` (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f (Array i a -> [a]
forall i e. Array i e -> [e]
elems Array i a
arr)
instance Traversable Proxy where
traverse :: (a -> f b) -> Proxy a -> f (Proxy b)
traverse _ _ = Proxy b -> f (Proxy b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy b
forall k (t :: k). Proxy t
Proxy
{-# INLINE traverse #-}
sequenceA :: Proxy (f a) -> f (Proxy a)
sequenceA _ = Proxy a -> f (Proxy a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy a
forall k (t :: k). Proxy t
Proxy
{-# INLINE sequenceA #-}
mapM :: (a -> m b) -> Proxy a -> m (Proxy b)
mapM _ _ = Proxy b -> m (Proxy b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy b
forall k (t :: k). Proxy t
Proxy
{-# INLINE mapM #-}
sequence :: Proxy (m a) -> m (Proxy a)
sequence _ = Proxy a -> m (Proxy a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Proxy a
forall k (t :: k). Proxy t
Proxy
{-# INLINE sequence #-}
instance Traversable (Const m) where
traverse :: (a -> f b) -> Const m a -> f (Const m b)
traverse _ (Const m :: m
m) = Const m b -> f (Const m b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Const m b -> f (Const m b)) -> Const m b -> f (Const m b)
forall a b. (a -> b) -> a -> b
$ m -> Const m b
forall k a (b :: k). a -> Const a b
Const m
m
instance Traversable Dual where
traverse :: (a -> f b) -> Dual a -> f (Dual b)
traverse f :: a -> f b
f (Dual x :: a
x) = b -> Dual b
forall a. a -> Dual a
Dual (b -> Dual b) -> f b -> f (Dual b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x
instance Traversable Sum where
traverse :: (a -> f b) -> Sum a -> f (Sum b)
traverse f :: a -> f b
f (Sum x :: a
x) = b -> Sum b
forall a. a -> Sum a
Sum (b -> Sum b) -> f b -> f (Sum b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x
instance Traversable Product where
traverse :: (a -> f b) -> Product a -> f (Product b)
traverse f :: a -> f b
f (Product x :: a
x) = b -> Product b
forall a. a -> Product a
Product (b -> Product b) -> f b -> f (Product b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
x
instance Traversable First where
traverse :: (a -> f b) -> First a -> f (First b)
traverse f :: a -> f b
f (First x :: Maybe a
x) = Maybe b -> First b
forall a. Maybe a -> First a
First (Maybe b -> First b) -> f (Maybe b) -> f (First b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Maybe a
x
instance Traversable Last where
traverse :: (a -> f b) -> Last a -> f (Last b)
traverse f :: a -> f b
f (Last x :: Maybe a
x) = Maybe b -> Last b
forall a. Maybe a -> Last a
Last (Maybe b -> Last b) -> f (Maybe b) -> f (Last b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f Maybe a
x
instance (Traversable f) => Traversable (Alt f) where
traverse :: (a -> f b) -> Alt f a -> f (Alt f b)
traverse f :: a -> f b
f (Alt x :: f a
x) = f b -> Alt f b
forall k (f :: k -> *) (a :: k). f a -> Alt f a
Alt (f b -> Alt f b) -> f (f b) -> f (Alt f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> f a -> f (f b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f f a
x
instance (Traversable f) => Traversable (Ap f) where
traverse :: (a -> f b) -> Ap f a -> f (Ap f b)
traverse f :: a -> f b
f (Ap x :: f a
x) = f b -> Ap f b
forall k (f :: k -> *) (a :: k). f a -> Ap f a
Ap (f b -> Ap f b) -> f (f b) -> f (Ap f b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> f a -> f (f b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f f a
x
instance Traversable ZipList where
traverse :: (a -> f b) -> ZipList a -> f (ZipList b)
traverse f :: a -> f b
f (ZipList x :: [a]
x) = [b] -> ZipList b
forall a. [a] -> ZipList a
ZipList ([b] -> ZipList b) -> f [b] -> f (ZipList b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f [a]
x
deriving instance Traversable Identity
instance Traversable U1 where
traverse :: (a -> f b) -> U1 a -> f (U1 b)
traverse _ _ = U1 b -> f (U1 b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 b
forall k (p :: k). U1 p
U1
{-# INLINE traverse #-}
sequenceA :: U1 (f a) -> f (U1 a)
sequenceA _ = U1 a -> f (U1 a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 a
forall k (p :: k). U1 p
U1
{-# INLINE sequenceA #-}
mapM :: (a -> m b) -> U1 a -> m (U1 b)
mapM _ _ = U1 b -> m (U1 b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 b
forall k (p :: k). U1 p
U1
{-# INLINE mapM #-}
sequence :: U1 (m a) -> m (U1 a)
sequence _ = U1 a -> m (U1 a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure U1 a
forall k (p :: k). U1 p
U1
{-# INLINE sequence #-}
deriving instance Traversable V1
deriving instance Traversable Par1
deriving instance Traversable f => Traversable (Rec1 f)
deriving instance Traversable (K1 i c)
deriving instance Traversable f => Traversable (M1 i c f)
deriving instance (Traversable f, Traversable g) => Traversable (f :+: g)
deriving instance (Traversable f, Traversable g) => Traversable (f :*: g)
deriving instance (Traversable f, Traversable g) => Traversable (f :.: g)
deriving instance Traversable UAddr
deriving instance Traversable UChar
deriving instance Traversable UDouble
deriving instance Traversable UFloat
deriving instance Traversable UInt
deriving instance Traversable UWord
deriving instance Traversable Down
for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
{-# INLINE for #-}
for :: t a -> (a -> f b) -> f (t b)
for = ((a -> f b) -> t a -> f (t b)) -> t a -> (a -> f b) -> f (t b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> f b) -> t a -> f (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
{-# INLINE forM #-}
forM :: t a -> (a -> m b) -> m (t b)
forM = ((a -> m b) -> t a -> m (t b)) -> t a -> (a -> m b) -> m (t b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (a -> m b) -> t a -> m (t b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL :: (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL f :: a -> b -> (a, c)
f s :: a
s t :: t b
t = StateL a (t c) -> a -> (a, t c)
forall s a. StateL s a -> s -> (s, a)
runStateL ((b -> StateL a c) -> t b -> StateL a (t c)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> (a, c)) -> StateL a c
forall s a. (s -> (s, a)) -> StateL s a
StateL ((a -> (a, c)) -> StateL a c)
-> (b -> a -> (a, c)) -> b -> StateL a c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> (a, c)) -> b -> a -> (a, c)
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> (a, c)
f) t b
t) a
s
mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumR :: (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumR f :: a -> b -> (a, c)
f s :: a
s t :: t b
t = StateR a (t c) -> a -> (a, t c)
forall s a. StateR s a -> s -> (s, a)
runStateR ((b -> StateR a c) -> t b -> StateR a (t c)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> (a, c)) -> StateR a c
forall s a. (s -> (s, a)) -> StateR s a
StateR ((a -> (a, c)) -> StateR a c)
-> (b -> a -> (a, c)) -> b -> StateR a c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> (a, c)) -> b -> a -> (a, c)
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> (a, c)
f) t b
t) a
s
fmapDefault :: forall t a b . Traversable t
=> (a -> b) -> t a -> t b
{-# INLINE fmapDefault #-}
fmapDefault :: (a -> b) -> t a -> t b
fmapDefault = ((a -> Identity b) -> t a -> Identity (t b))
-> (a -> b) -> t a -> t b
forall a b. Coercible a b => a -> b
coerce ((a -> Identity b) -> t a -> Identity (t b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse :: (a -> Identity b) -> t a -> Identity (t b))
foldMapDefault :: forall t m a . (Traversable t, Monoid m)
=> (a -> m) -> t a -> m
{-# INLINE foldMapDefault #-}
foldMapDefault :: (a -> m) -> t a -> m
foldMapDefault = ((a -> Const m ()) -> t a -> Const m (t ()))
-> (a -> m) -> t a -> m
forall a b. Coercible a b => a -> b
coerce ((a -> Const m ()) -> t a -> Const m (t ())
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse :: (a -> Const m ()) -> t a -> Const m (t ()))