Copyright	(c) 2020-2021 Emily Pillmore
License	BSD-3-Clause
Maintainer	Emily Pillmore <emilypi@cohomolo.gy>
Stability	Experimental
Portability	CPP, RankNTypes, TypeApplications
Safe Haskell	Safe
Language	Haskell2010

Data.Wedge

Contents

Datatypes
- Type synonyms
Combinators

Description

This module contains the definition for the Wedge datatype. In practice, this type is isomorphic to Maybe (Either a b) - the type with two possibly non-exclusive values and an empty case.

Synopsis

data Wedge a b
- = Nowhere
- | Here a
- | There b
type (∨) a b = Wedge a b
quotWedge :: Either (Maybe a) (Maybe b) -> Wedge a b
wedgeLeft :: Maybe a -> Wedge a b
wedgeRight :: Maybe b -> Wedge a b
fromWedge :: Wedge a b -> Maybe (Either a b)
toWedge :: Maybe (Either a b) -> Wedge a b
isHere :: Wedge a b -> Bool
isThere :: Wedge a b -> Bool
isNowhere :: Wedge a b -> Bool
wedge :: c -> (a -> c) -> (b -> c) -> Wedge a b -> c
heres :: Foldable f => f (Wedge a b) -> [a]
theres :: Foldable f => f (Wedge a b) -> [b]
filterHeres :: Foldable f => f (Wedge a b) -> [Wedge a b]
filterTheres :: Foldable f => f (Wedge a b) -> [Wedge a b]
filterNowheres :: Foldable f => f (Wedge a b) -> [Wedge a b]
foldHeres :: Foldable f => (a -> m -> m) -> m -> f (Wedge a b) -> m
foldTheres :: Foldable f => (b -> m -> m) -> m -> f (Wedge a b) -> m
gatherWedges :: Wedge [a] [b] -> [Wedge a b]
unfoldr :: Alternative f => (b -> Wedge a b) -> b -> f a
unfoldrM :: (Monad m, Alternative f) => (b -> m (Wedge a b)) -> b -> m (f a)
iterateUntil :: Alternative f => (b -> Wedge a b) -> b -> f a
iterateUntilM :: Monad m => Alternative f => (b -> m (Wedge a b)) -> b -> m (f a)
accumUntil :: Alternative f => Monoid b => (b -> Wedge a b) -> f a
accumUntilM :: Monad m => Alternative f => Monoid b => (b -> m (Wedge a b)) -> m (f a)
partitionWedges :: Foldable t => Alternative f => t (Wedge a b) -> (f a, f b)
mapWedges :: Traversable t => Alternative f => (a -> Wedge b c) -> t a -> (f b, f c)
distributeWedge :: Wedge (a, b) c -> (Wedge a c, Wedge b c)
codistributeWedge :: Either (Wedge a c) (Wedge b c) -> Wedge (Either a b) c
reassocLR :: Wedge (Wedge a b) c -> Wedge a (Wedge b c)
reassocRL :: Wedge a (Wedge b c) -> Wedge (Wedge a b) c
swapWedge :: Wedge a b -> Wedge b a

Datatypes

Categorically, the Wedge datatype represents the coproduct (like, Either) in the category Hask* of pointed Hask types, called a wedge sum. The category Hask* consists of Hask types affixed with a dedicated base point along with an object. In Hask, this is equivalent to 1 + a, also known as Maybe a. Because we can conflate basepoints of different types (there is only one Nothing type), the wedge sum can be viewed as the type 1 + a + b, or Maybe (Either a b) in Hask.

Pictorially, one can visualize this as:

Wedge:
                  a
                  |
Nowhere +-------+
                  |
                  b

The fact that we can think about Wedge as a coproduct gives us some reasoning power about how a Wedge will interact with the product in Hask*, called Can. Namely, we know that a product of a type and a coproduct, a * (b + c), is equivalent to (a * b) + (a * c). Additionally, we may derive other facts about its associativity, distributivity, commutativity, and many more. As an exercise, think of something Either can do. Now do it with Wedge!

data Wedge a b Source #

The Wedge data type represents values with two exclusive possibilities, and an empty case. This is a coproduct of pointed types - i.e. of Maybe values. The result is a type, 'Wedge a b', which is isomorphic to Maybe (Either a b).

Constructors

Nowhere
Here a
There b

Instances

Instances details

Bitraversable Wedge Source #
Instance details Defined in Data.Wedge Methods bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Wedge a b -> f (Wedge c d) #
Bifoldable Wedge Source #
Instance details Defined in Data.Wedge Methods bifold :: Monoid m => Wedge m m -> m # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> Wedge a b -> m # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Wedge a b -> c # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Wedge a b -> c #
Bifunctor Wedge Source #
Instance details Defined in Data.Wedge Methods bimap :: (a -> b) -> (c -> d) -> Wedge a c -> Wedge b d # first :: (a -> b) -> Wedge a c -> Wedge b c # second :: (b -> c) -> Wedge a b -> Wedge a c #
Eq2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> Wedge a c -> Wedge b d -> Bool #
Ord2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> Wedge a c -> Wedge b d -> Ordering #
Read2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftReadsPrec2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> Int -> ReadS (Wedge a b) # liftReadList2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> ReadS [Wedge a b] # liftReadPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec (Wedge a b) # liftReadListPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec [Wedge a b] #
Show2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> Wedge a b -> ShowS # liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [Wedge a b] -> ShowS #
NFData2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftRnf2 :: (a -> ()) -> (b -> ()) -> Wedge a b -> () #
Hashable2 Wedge Source #
Instance details Defined in Data.Wedge Methods liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> Wedge a b -> Int
Semigroup a => Monad (Wedge a) Source #
Instance details Defined in Data.Wedge Methods (>>=) :: Wedge a a0 -> (a0 -> Wedge a b) -> Wedge a b # (>>) :: Wedge a a0 -> Wedge a b -> Wedge a b # return :: a0 -> Wedge a a0 #
Functor (Wedge a) Source #
Instance details Defined in Data.Wedge Methods fmap :: (a0 -> b) -> Wedge a a0 -> Wedge a b # (<$) :: a0 -> Wedge a b -> Wedge a a0 #
Semigroup a => Applicative (Wedge a) Source #
Instance details Defined in Data.Wedge Methods pure :: a0 -> Wedge a a0 # (<>) :: Wedge a (a0 -> b) -> Wedge a a0 -> Wedge a b # liftA2 :: (a0 -> b -> c) -> Wedge a a0 -> Wedge a b -> Wedge a c # (>) :: Wedge a a0 -> Wedge a b -> Wedge a b # (<*) :: Wedge a a0 -> Wedge a b -> Wedge a a0 #
Foldable (Wedge a) Source #
Instance details Defined in Data.Wedge Methods fold :: Monoid m => Wedge a m -> m # foldMap :: Monoid m => (a0 -> m) -> Wedge a a0 -> m # foldMap' :: Monoid m => (a0 -> m) -> Wedge a a0 -> m # foldr :: (a0 -> b -> b) -> b -> Wedge a a0 -> b # foldr' :: (a0 -> b -> b) -> b -> Wedge a a0 -> b # foldl :: (b -> a0 -> b) -> b -> Wedge a a0 -> b # foldl' :: (b -> a0 -> b) -> b -> Wedge a a0 -> b # foldr1 :: (a0 -> a0 -> a0) -> Wedge a a0 -> a0 # foldl1 :: (a0 -> a0 -> a0) -> Wedge a a0 -> a0 # toList :: Wedge a a0 -> [a0] # null :: Wedge a a0 -> Bool # length :: Wedge a a0 -> Int # elem :: Eq a0 => a0 -> Wedge a a0 -> Bool # maximum :: Ord a0 => Wedge a a0 -> a0 # minimum :: Ord a0 => Wedge a a0 -> a0 # sum :: Num a0 => Wedge a a0 -> a0 # product :: Num a0 => Wedge a a0 -> a0 #
Traversable (Wedge a) Source #
Instance details Defined in Data.Wedge Methods traverse :: Applicative f => (a0 -> f b) -> Wedge a a0 -> f (Wedge a b) # sequenceA :: Applicative f => Wedge a (f a0) -> f (Wedge a a0) # mapM :: Monad m => (a0 -> m b) -> Wedge a a0 -> m (Wedge a b) # sequence :: Monad m => Wedge a (m a0) -> m (Wedge a a0) #
Eq a => Eq1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftEq :: (a0 -> b -> Bool) -> Wedge a a0 -> Wedge a b -> Bool #
Ord a => Ord1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftCompare :: (a0 -> b -> Ordering) -> Wedge a a0 -> Wedge a b -> Ordering #
Read a => Read1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftReadsPrec :: (Int -> ReadS a0) -> ReadS [a0] -> Int -> ReadS (Wedge a a0) # liftReadList :: (Int -> ReadS a0) -> ReadS [a0] -> ReadS [Wedge a a0] # liftReadPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec (Wedge a a0) # liftReadListPrec :: ReadPrec a0 -> ReadPrec [a0] -> ReadPrec [Wedge a a0] #
Show a => Show1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftShowsPrec :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> Int -> Wedge a a0 -> ShowS # liftShowList :: (Int -> a0 -> ShowS) -> ([a0] -> ShowS) -> [Wedge a a0] -> ShowS #
Semigroup a => MonadZip (Wedge a) Source #
Instance details Defined in Data.Wedge Methods mzip :: Wedge a a0 -> Wedge a b -> Wedge a (a0, b) # mzipWith :: (a0 -> b -> c) -> Wedge a a0 -> Wedge a b -> Wedge a c # munzip :: Wedge a (a0, b) -> (Wedge a a0, Wedge a b) #
Monoid a => Alternative (Wedge a) Source #
Instance details Defined in Data.Wedge Methods empty :: Wedge a a0 # (<\|>) :: Wedge a a0 -> Wedge a a0 -> Wedge a a0 # some :: Wedge a a0 -> Wedge a [a0] # many :: Wedge a a0 -> Wedge a [a0] #
Monoid a => MonadPlus (Wedge a) Source #
Instance details Defined in Data.Wedge Methods mzero :: Wedge a a0 # mplus :: Wedge a a0 -> Wedge a a0 -> Wedge a a0 #
NFData a => NFData1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftRnf :: (a0 -> ()) -> Wedge a a0 -> () #
Hashable a => Hashable1 (Wedge a) Source #
Instance details Defined in Data.Wedge Methods liftHashWithSalt :: (Int -> a0 -> Int) -> Int -> Wedge a a0 -> Int
Generic1 (Wedge a :: Type -> Type) Source #
Instance details Defined in Data.Wedge Associated Types type Rep1 (Wedge a) :: k -> Type # Methods from1 :: forall (a0 :: k). Wedge a a0 -> Rep1 (Wedge a) a0 # to1 :: forall (a0 :: k). Rep1 (Wedge a) a0 -> Wedge a a0 #
(Eq a, Eq b) => Eq (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods (==) :: Wedge a b -> Wedge a b -> Bool # (/=) :: Wedge a b -> Wedge a b -> Bool #
(Data a, Data b) => Data (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> Wedge a b -> c (Wedge a b) # gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Wedge a b) # toConstr :: Wedge a b -> Constr # dataTypeOf :: Wedge a b -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Wedge a b)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Wedge a b)) # gmapT :: (forall b0. Data b0 => b0 -> b0) -> Wedge a b -> Wedge a b # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Wedge a b -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Wedge a b -> r # gmapQ :: (forall d. Data d => d -> u) -> Wedge a b -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Wedge a b -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Wedge a b -> m (Wedge a b) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Wedge a b -> m (Wedge a b) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Wedge a b -> m (Wedge a b) #
(Ord a, Ord b) => Ord (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods compare :: Wedge a b -> Wedge a b -> Ordering # (<) :: Wedge a b -> Wedge a b -> Bool # (<=) :: Wedge a b -> Wedge a b -> Bool # (>) :: Wedge a b -> Wedge a b -> Bool # (>=) :: Wedge a b -> Wedge a b -> Bool # max :: Wedge a b -> Wedge a b -> Wedge a b # min :: Wedge a b -> Wedge a b -> Wedge a b #
(Read a, Read b) => Read (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods readsPrec :: Int -> ReadS (Wedge a b) # readList :: ReadS [Wedge a b] # readPrec :: ReadPrec (Wedge a b) # readListPrec :: ReadPrec [Wedge a b] #
(Show a, Show b) => Show (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods showsPrec :: Int -> Wedge a b -> ShowS # show :: Wedge a b -> String # showList :: [Wedge a b] -> ShowS #
Generic (Wedge a b) Source #
Instance details Defined in Data.Wedge Associated Types type Rep (Wedge a b) :: Type -> Type # Methods from :: Wedge a b -> Rep (Wedge a b) x # to :: Rep (Wedge a b) x -> Wedge a b #
(Semigroup a, Semigroup b) => Semigroup (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods (<>) :: Wedge a b -> Wedge a b -> Wedge a b # sconcat :: NonEmpty (Wedge a b) -> Wedge a b # stimes :: Integral b0 => b0 -> Wedge a b -> Wedge a b #
(Semigroup a, Semigroup b) => Monoid (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods mempty :: Wedge a b # mappend :: Wedge a b -> Wedge a b -> Wedge a b # mconcat :: [Wedge a b] -> Wedge a b #
(Lift a, Lift b) => Lift (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods lift :: Wedge a b -> Q Exp #
(Binary a, Binary b) => Binary (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods put :: Wedge a b -> Put # get :: Get (Wedge a b) # putList :: [Wedge a b] -> Put #
(NFData a, NFData b) => NFData (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods rnf :: Wedge a b -> () #
(Hashable a, Hashable b) => Hashable (Wedge a b) Source #
Instance details Defined in Data.Wedge Methods hashWithSalt :: Int -> Wedge a b -> Int hash :: Wedge a b -> Int
type Rep1 (Wedge a :: Type -> Type) Source #
Instance details Defined in Data.Wedge type Rep1 (Wedge a :: Type -> Type) = D1 ('MetaData "Wedge" "Data.Wedge" "smash-0.1.2-inplace" 'False) (C1 ('MetaCons "Nowhere" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "Here" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "There" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1)))
type Rep (Wedge a b) Source #
Instance details Defined in Data.Wedge type Rep (Wedge a b) = D1 ('MetaData "Wedge" "Data.Wedge" "smash-0.1.2-inplace" 'False) (C1 ('MetaCons "Nowhere" 'PrefixI 'False) (U1 :: Type -> Type) :+: (C1 ('MetaCons "Here" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "There" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 b))))

Type synonyms

type (∨) a b = Wedge a b Source #

A type operator synonym for Wedge.

Combinators

quotWedge :: Either (Maybe a) (Maybe b) -> Wedge a b Source #

Given two possible pointed types, produce a Wedge by considering the left case, the right case, and mapping their Nothing cases to Nowhere. This is a pushout of pointed types A * - B.

wedgeLeft :: Maybe a -> Wedge a b Source #

Inject a Maybe value into the Here case of a Wedge, or Nowhere if the empty case is given. This is analogous to the Left constructor for Either.

wedgeRight :: Maybe b -> Wedge a b Source #

Inject a Maybe value into the There case of a Wedge, or Nowhere if the empty case is given. This is analogous to the Right constructor for Either.

fromWedge :: Wedge a b -> Maybe (Either a b) Source #

Convert a 'Wedge a b' into a Maybe (Either a b) value.

toWedge :: Maybe (Either a b) -> Wedge a b Source #

Convert a Maybe (Either a b) value into a Wedge

isHere :: Wedge a b -> Bool Source #

Detect if a Wedge is a Here case.

isThere :: Wedge a b -> Bool Source #

Detect if a Wedge is a There case.

isNowhere :: Wedge a b -> Bool Source #

Detect if a Wedge is a Nowhere empty case.

Eliminators

wedge :: c -> (a -> c) -> (b -> c) -> Wedge a b -> c Source #

Case elimination for the Wedge datatype.

Filtering

heres :: Foldable f => f (Wedge a b) -> [a] Source #

Given a Foldable of Wedges, collect the Here cases, if any.

theres :: Foldable f => f (Wedge a b) -> [b] Source #

Given a Foldable of Wedges, collect the There cases, if any.

filterHeres :: Foldable f => f (Wedge a b) -> [Wedge a b] Source #

Filter the Here cases of a Foldable of Wedges.

filterTheres :: Foldable f => f (Wedge a b) -> [Wedge a b] Source #

Filter the There cases of a Foldable of Wedges.

filterNowheres :: Foldable f => f (Wedge a b) -> [Wedge a b] Source #

Filter the Nowhere cases of a Foldable of Wedges.

Folding and Unfolding

foldHeres :: Foldable f => (a -> m -> m) -> m -> f (Wedge a b) -> m Source #

Fold over the Here cases of a Foldable of Wedges by some accumulating function.

foldTheres :: Foldable f => (b -> m -> m) -> m -> f (Wedge a b) -> m Source #

Fold over the There cases of a Foldable of Wedges by some accumulating function.

gatherWedges :: Wedge [a] [b] -> [Wedge a b] Source #

Given a Wedge of lists, produce a list of wedges by mapping the list of as to Here values, or the list of bs to There values.

unfoldr :: Alternative f => (b -> Wedge a b) -> b -> f a Source #

Unfold from right to left into a wedge product. For a variant that accumulates in the seed instead of just updating with a new value, see accumUntil and accumUntilM.

unfoldrM :: (Monad m, Alternative f) => (b -> m (Wedge a b)) -> b -> m (f a) Source #

Unfold from right to left into a monadic computation over a wedge product

iterateUntil :: Alternative f => (b -> Wedge a b) -> b -> f a Source #

Iterate on a seed, accumulating a result. See iterateUntilM for more details.

iterateUntilM :: Monad m => Alternative f => (b -> m (Wedge a b)) -> b -> m (f a) Source #

Iterate on a seed, which may result in one of three scenarios:

The function yields a Nowhere value, which terminates the iteration.
The function yields a Here value.
The function yields a There value, which changes the seed and iteration continues with the new seed.

accumUntil :: Alternative f => Monoid b => (b -> Wedge a b) -> f a Source #

Iterate on a seed, accumulating values and monoidally updating the seed with each update.

accumUntilM :: Monad m => Alternative f => Monoid b => (b -> m (Wedge a b)) -> m (f a) Source #

Iterate on a seed, accumulating values and monoidally updating a seed within a monad.

Partitioning

partitionWedges :: Foldable t => Alternative f => t (Wedge a b) -> (f a, f b) Source #

Given a Foldable of Wedges, partition it into a tuple of alternatives their parts.

mapWedges :: Traversable t => Alternative f => (a -> Wedge b c) -> t a -> (f b, f c) Source #

Partition a structure by mapping its contents into Wedges, and folding over (<|>).

Distributivity

distributeWedge :: Wedge (a, b) c -> (Wedge a c, Wedge b c) Source #

Distribute a Wedge over a product.

codistributeWedge :: Either (Wedge a c) (Wedge b c) -> Wedge (Either a b) c Source #

Codistribute Wedges over a coproduct.

Associativity

reassocLR :: Wedge (Wedge a b) c -> Wedge a (Wedge b c) Source #

Re-associate a Wedge of Wedges from left to right.

reassocRL :: Wedge a (Wedge b c) -> Wedge (Wedge a b) c Source #

Re-associate a Wedge of Wedges from left to right.

Symmetry

swapWedge :: Wedge a b -> Wedge b a Source #

Swap the positions of the a's and the b's in a Wedge.