Generics.SOP.NS

n-ary sums (and sums of products)

Datatypes

data NS :: (k -> *) -> [k] -> * where

An n-ary sum.

The sum is parameterized by a type constructor f and indexed by a type-level list xs. The length of the list determines the number of choices in the sum and if the i-th element of the list is of type x, then the i-th choice of the sum is of type f x.

The constructor names are chosen to resemble Peano-style natural numbers, i.e., Z is for "zero", and S is for "successor". Chaining S and Z chooses the corresponding component of the sum.

Examples:

Z         :: f x -> NS f (x ': xs)
S . Z     :: f y -> NS f (x ': y ': xs)
S . S . Z :: f z -> NS f (x ': y ': z ': xs)
...

Note that empty sums (indexed by an empty list) have no non-bottom elements.

Two common instantiations of f are the identity functor I and the constant functor K. For I, the sum becomes a direct generalization of the Either type to arbitrarily many choices. For K a, the result is a homogeneous choice type, where the contents of the type-level list are ignored, but its length specifies the number of options.

In the context of the SOP approach to generic programming, an n-ary sum describes the top-level structure of a datatype, which is a choice between all of its constructors.

Examples:

Z (I 'x')      :: NS I       '[ Char, Bool ]
S (Z (I True)) :: NS I       '[ Char, Bool ]
S (Z (I 1))    :: NS (K Int) '[ Char, Bool ]

Constructors

Z :: f x -> NS f (x ': xs)

S :: NS f xs -> NS f (x ': xs)

Instances

HSequence [k] k (NS k)

Methods

hsequence' :: (SListIN (NS k) k h xs, Applicative f) => h ((k :.: *) f g) xs -> f (h g xs)

HCollapse [k] k (NS k)

Methods

hcollapse :: SListIN (NS k) k h xs => h (K k a) xs -> CollapseTo (NS k) k h a

HAp [k] k (NS k)

Methods

hap :: Prod (NS k) k h ((k -.-> f) g) xs -> h f xs -> h g xs

All k (Compose * k Eq f) xs => Eq (NS k f xs)

Methods

(==) :: NS k f xs -> NS k f xs -> Bool

(/=) :: NS k f xs -> NS k f xs -> Bool

(All k (Compose * k Eq f) xs, All k (Compose * k Ord f) xs) => Ord (NS k f xs)

Methods

compare :: NS k f xs -> NS k f xs -> Ordering

(<) :: NS k f xs -> NS k f xs -> Bool

(<=) :: NS k f xs -> NS k f xs -> Bool

(>) :: NS k f xs -> NS k f xs -> Bool

(>=) :: NS k f xs -> NS k f xs -> Bool

max :: NS k f xs -> NS k f xs -> NS k f xs

min :: NS k f xs -> NS k f xs -> NS k f xs

All k (Compose * k Show f) xs => Show (NS k f xs)

Methods

showsPrec :: Int -> NS k f xs -> ShowS

show :: NS k f xs -> String

showList :: [NS k f xs] -> ShowS

type SListIN [k] k (NS k)

type SListIN [k] k (NS k) = SListI k

type Prod [k] k (NS k)

type Prod [k] k (NS k) = NP k

type CollapseTo [k] k (NS k) a

type CollapseTo [k] k (NS k) a = a

newtype SOP f xss

A sum of products.

This is a 'newtype' for an NS of an NP. The elements of the (inner) products are applications of the parameter f. The type SOP is indexed by the list of lists that determines the sizes of both the (outer) sum and all the (inner) products, as well as the types of all the elements of the inner products.

An SOP I reflects the structure of a normal Haskell datatype. The sum structure represents the choice between the different constructors, the product structure represents the arguments of each constructor.

Constructors

SOP (NS (NP f) xss)

Instances

HSequence [[k]] k (SOP k)

Methods

hsequence' :: (SListIN (SOP k) k h xs, Applicative f) => h ((k :.: *) f g) xs -> f (h g xs)

HCollapse [[k]] k (SOP k)

Methods

hcollapse :: SListIN (SOP k) k h xs => h (K k a) xs -> CollapseTo (SOP k) k h a

HAp [[k]] k (SOP k)

Methods

hap :: Prod (SOP k) k h ((k -.-> f) g) xs -> h f xs -> h g xs

Eq (NS [k] (NP k f) xss) => Eq (SOP k f xss)

Methods

(==) :: SOP k f xss -> SOP k f xss -> Bool

(/=) :: SOP k f xss -> SOP k f xss -> Bool

Ord (NS [k] (NP k f) xss) => Ord (SOP k f xss)

Methods

compare :: SOP k f xss -> SOP k f xss -> Ordering

(<) :: SOP k f xss -> SOP k f xss -> Bool

(<=) :: SOP k f xss -> SOP k f xss -> Bool

(>) :: SOP k f xss -> SOP k f xss -> Bool

(>=) :: SOP k f xss -> SOP k f xss -> Bool

max :: SOP k f xss -> SOP k f xss -> SOP k f xss

min :: SOP k f xss -> SOP k f xss -> SOP k f xss

Show (NS [k] (NP k f) xss) => Show (SOP k f xss)

Methods

showsPrec :: Int -> SOP k f xss -> ShowS

show :: SOP k f xss -> String

showList :: [SOP k f xss] -> ShowS

type SListIN [[k]] k (SOP k)

type SListIN [[k]] k (SOP k) = SListI2 k

type Prod [[k]] k (SOP k)

type Prod [[k]] k (SOP k) = POP k

type CollapseTo [[k]] k (SOP k) a

type CollapseTo [[k]] k (SOP k) a = [a]

unZ :: NS f '[x] -> f x

Extract the payload from a unary sum.

For larger sums, this function would be partial, so it is only provided with a rather restrictive type.

Example:

>>> unZ (Z (I 'x'))
I 'x'

Since: 0.2.2.0

unSOP :: SOP f xss -> NS (NP f) xss

Unwrap a sum of products.

Constructing sums

type Injection f xs = f -.-> K (NS f xs)

The type of injections into an n-ary sum.

If you expand the type synonyms and newtypes involved, you get

Injection f xs a = (f -.-> K (NS f xs)) a ~= f a -> K (NS f xs) a ~= f a -> NS f xs

If we pick a to be an element of xs, this indeed corresponds to an injection into the sum.

injections :: forall xs f. SListI xs => NP (Injection f xs) xs

Compute all injections into an n-ary sum.

Each element of the resulting product contains one of the injections.

shift :: Injection f xs a -> Injection f (x ': xs) a

Deprecated: Use shiftInjection instead.

Shift an injection.

Given an injection, return an injection into a sum that is one component larger.

shiftInjection :: Injection f xs a -> Injection f (x ': xs) a

Shift an injection.

Given an injection, return an injection into a sum that is one component larger.

apInjs_NP :: SListI xs => NP f xs -> [NS f xs]

Apply injections to a product.

Given a product containing all possible choices, produce a list of sums by applying each injection to the appropriate element.

Example:

>>> apInjs_NP (I 'x' :* I True :* I 2 :* Nil)
[Z (I 'x'), S (Z (I True)), S (S (Z (I 2)))]

apInjs_POP :: SListI xss => POP f xss -> [SOP f xss]

Apply injections to a product of product.

This operates on the outer product only. Given a product containing all possible choices (that are products), produce a list of sums (of products) by applying each injection to the appropriate element.

Example:

>>> apInjs_POP (POP ((I 'x' :* Nil) :* (I True :* I 2 :* Nil) :* Nil))
[SOP (Z (I 'x' :* Nil)),SOP (S (Z (I True :* (I 2 :* Nil))))]

Application

ap_NS :: NP (f -.-> g) xs -> NS f xs -> NS g xs

Specialization of hap.

ap_SOP :: POP (f -.-> g) xss -> SOP f xss -> SOP g xss

Specialization of hap.

Lifting / mapping

liftA_NS :: SListI xs => (forall a. f a -> g a) -> NS f xs -> NS g xs

Specialization of hliftA.

liftA_SOP :: All SListI xss => (forall a. f a -> g a) -> SOP f xss -> SOP g xss

Specialization of hliftA.

liftA2_NS :: SListI xs => (forall a. f a -> g a -> h a) -> NP f xs -> NS g xs -> NS h xs

Specialization of hliftA2.

liftA2_SOP :: All SListI xss => (forall a. f a -> g a -> h a) -> POP f xss -> SOP g xss -> SOP h xss

Specialization of hliftA2.

cliftA_NS :: All c xs => proxy c -> (forall a. c a => f a -> g a) -> NS f xs -> NS g xs

Specialization of hcliftA.

cliftA_SOP :: All2 c xss => proxy c -> (forall a. c a => f a -> g a) -> SOP f xss -> SOP g xss

Specialization of hcliftA.

cliftA2_NS :: All c xs => proxy c -> (forall a. c a => f a -> g a -> h a) -> NP f xs -> NS g xs -> NS h xs

Specialization of hcliftA2.

cliftA2_SOP :: All2 c xss => proxy c -> (forall a. c a => f a -> g a -> h a) -> POP f xss -> SOP g xss -> SOP h xss

Specialization of hcliftA2.

map_NS :: SListI xs => (forall a. f a -> g a) -> NS f xs -> NS g xs

Specialization of hmap, which is equivalent to hliftA.

map_SOP :: All SListI xss => (forall a. f a -> g a) -> SOP f xss -> SOP g xss

Specialization of hmap, which is equivalent to hliftA.

cmap_NS :: All c xs => proxy c -> (forall a. c a => f a -> g a) -> NS f xs -> NS g xs

Specialization of hcmap, which is equivalent to hcliftA.

cmap_SOP :: All2 c xss => proxy c -> (forall a. c a => f a -> g a) -> SOP f xss -> SOP g xss

Specialization of hcmap, which is equivalent to hcliftA.

Dealing with All c

cliftA2'_NS :: All2 c xss => proxy c -> (forall xs. All c xs => f xs -> g xs -> h xs) -> NP f xss -> NS g xss -> NS h xss

Deprecated: Use cliftA2_NS instead.

Specialization of hcliftA2'.

Collapsing

collapse_NS :: NS (K a) xs -> a

Specialization of hcollapse.

collapse_SOP :: SListI xss => SOP (K a) xss -> [a]

Specialization of hcollapse.

Sequencing

sequence'_NS :: Applicative f => NS (f :.: g) xs -> f (NS g xs)

Specialization of hsequence'.

sequence'_SOP :: (SListI xss, Applicative f) => SOP (f :.: g) xss -> f (SOP g xss)

Specialization of hsequence'.

sequence_NS :: (SListI xs, Applicative f) => NS f xs -> f (NS I xs)

Specialization of hsequence.

sequence_SOP :: (All SListI xss, Applicative f) => SOP f xss -> f (SOP I xss)

Specialization of hsequence.