абстрактные типы данных

каноническая реализация картезианского произведения двух типов есть

  Pair a b = (a , b) 

столь же каноническая реализация тегированной суммы двух типов есть

 
  Either a b = Left a | Right b 

применяемые раздельно, произведение и сумма используются в разных структурах данных, но реальная их мощь проявляется при комбинировании:

  a * (b + c) = a * b + a * c 
LHS соответствует типу       (a , Either b c)
RHS соответствует типу       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))

Haskell

функторы :

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)

ANSI C структура как произведение типов, и ANSI C юнион - как сумма типов

а также перечислимый тип, как частный случай суммы

#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 

даже уже только с этими структурами данных можно свернуть горы