каноническая реализация картезианского произведения двух типов есть
Pair a b = (a , b)
столь же каноническая реализация тегированной суммы двух типов есть
Either a b = Left a | Right b
применяемые раздельно, произведение и сумма используются в разных структурах данных, но реальная их мощь проявляется при комбинировании:
a * (b + c) = a * b + a * cLHS соответствует типу
(a , Either b c)
Either (a , b) (a , c)
эта адская смесь называется "полукольцом". это не "полное кольцо", поскольку отсутствует операция обращения (принципиально невозможная на типах)
теперь - обобщим:
0 Void 1 () a + b Either a b = Left a | Right b a * b Pair a b = (a , b) a * 1 (a , ()) 1 * a (() , a) 2 = 1 + 1 data Bool = True | False 1 + a data Maybe = Nothing | Just a 1 + a Either () a a + 1 Either a () a + 1 data Maybe = Just a | Nothing a + 0 Either a Void = Left a | Y Void 0 + a Either Void a = Y Void | Right a a * 0 = 0 (a , Void) = Void -- uninhabited 1 + a * x data List a = Nil | a :: List a
и для булевой алгебры:
false Void true () a || b Either a b = Left a | Right b a && b Pair a b = (a , b)
решение уравнений на символах - это алгебра и именно поэтому такие типы данных называются алгебраическими
тип данных a -> b называют "экспоненциальным" и обозначают ba. такая нотация имеет смысл
функция из типа Bool может принимать только один из двух аргументов: либо True либо False. все возможные функции Bool -> Int составляют множество пар (Int,Int) общее число которых |Int|²
а сколько значений может представить картеж из 256 переменных типа Bool? в точности 2^256, но это и есть число всевозможных функций Char -> Bool
точно таким же образом можно подсчитать число всевозможных функций Bool -> Char как 256²
и так далее
таким образом экспоненциальная нотация имеет прямой смысл
обобщим для экспонент:
a^0 = 1 Void -> a = () 1^a = 1 a -> () = () a^1 = a () -> a = a a^(b+c) = a^b | a^c fun : Either b c -> a fun x = case x of Left b => ... Right c => ... (a^b)^c = a^(b,c) fun : b -> c -> a fun : b -> (c -> a) fun : (b , c) -> a (a,b)^c = (a^c , b^c) fun : c -> (a , b) fun : c -> ((c -> a) , (c -> b))
функторы :
data K a x = K a data I x = I x data Sum p q x = L (p x) | R (q x) data Prod p q x = P (p x) (q x) instance Functor (K a) where fmap f (K x) = K x instance Functor I where fmap f (I x) = I (f x) instance (Functor p, Functor q) => Functor (Sum p q) where fmap f (L p) = L (fmap f p) fmap f (R q) = R (fmap f q) instance (Functor p, Functor q) => Functor (Prod p q) where fmap f (P p q) = P (fmap f p) (fmap f q)
бифункторы :
import Data.Bifunctor data K a x y = K a data Fst x y = Fst x data Snd x y = Snd y data (Sum p q) x y = L (p x y) | R (q x y) data (Prod p q) x y = P (p x y) (q x y) instance Bifunctor (K a) where bimap f g (K x) = K x instance Bifunctor Fst where bimap f g (Fst x) = Fst (f x) instance Bifunctor Snd where bimap f g (Snd y) = Snd (g y) instance (Bifunctor p, Bifunctor q) => Bifunctor (Sum p q) where bimap f g (L p) = L (bimap f g p) bimap f g (R q) = R (bimap f g q) instance (Bifunctor p, Bifunctor q) => Bifunctor (Prod p q) where bimap f g (P p q) = P (bimap f g p) (bimap f g q)
а также перечислимый тип, как частный случай суммы
#include <stdio.h> #define NUM 10 int main (int argc , char* argv[] , char* env[]) { enum color { RED = 1 , GREEN = 3 , YELLOW = 2 , BLACK = NUM } ; union { char* message ; int count ; } x ; struct { int field1 // signed int ; char* field2 ; float field3 ; double field4 ; long double field5 ; long field6 // long int ; short field7 // short int ; signed int field8 // int ; unsigned int field9 ; } z ; x.message = "hello world!" ; puts (x.message) ; x.count = 42 ; printf ("%d\n" , x.count) ; x.count = GREEN ; printf ("%d\n" , x.count) ; z.field1 = 0 ; z.field2 = "aaa" ; z.field3 = 34.5 ; z.field4 = 45.6 ; z.field5 = 34.8 ; z.field6 = 1 ; z.field7 = 2 ; z.field8 = 8 ; z.field9 = 1 ; printf ("%f\n" , z.field4) ; return 0 ; } // gcc hello.c && valgrind --leak-check=full ./a.out
даже уже только с этими структурами данных можно свернуть горы