Haskell Language => 型代数

型代数の自然数

ハスケル型と自然数の間の接続を描くことができます。この接続は、すべてのタイプに住民の数を割り当てることができます。

有限組合型

有限型の場合、コンストラクタの数に基づいて、すべての数値に自然な型を割り当てることができます。例えば：

type Color = Red | Yellow | Green

3となる。 Boolタイプは2です。

type Bool = True | False

同型異性までの一意性

複数の型が単一の数値に対応することがわかりましたが、この場合は同形になります。これは、2つのタイプを結びつける、その構成がアイデンティティである、1組の変態fとgが存在することを意味する。

f :: a -> b
g :: b -> a

f . g == id == g . f

この場合、型は同形であると言います。私たちは代数的である限り、代数では2つの型が等しいと考えます。

例えば、2番目の表現の2つの異なる表現は、単純に同形である：

type Bit  = I    | O
type Bool = True | False

bitValue :: Bit -> Bool
bitValue I = True
bitValue O = False

booleanBit :: Bool -> Bit
booleanBit True  = I
booleanBit False = O

bitValue . booleanBit == id == booleanBit . bitValueを見ることができるからbitValue . booleanBit == id == booleanBit . bitValue

1とゼロ

数字1の表現は明らかに1つのコンストラクタしか持たない型です。ハスケルでは、この型は標準的にUnit ()と呼ばれるtype ()です。 1つのコンストラクタのみを持つ他のすべての型は、 ()と同形です。

そして、 0の表現はコンストラクタなしの型になります。これは、 Data.Void定義されているHaskellのVoid型Data.Void 。これは、データコンストラクタではなく、無人型と同等です。

data Void

加算と乗算

加算と乗算は、このタイプの代数では等価です。 タグ付きの共用体および製品タイプに対応しています。

data Sum a b = A a | B b
data Prod a b = Prod a b

すべての型の住人数が代数演算にどのように対応しているかを見ることができます。

同様に、 Eitherと(,)を加算と乗算の型コンストラクタとして使用できます。それらは以前定義された型と同型である：

type Sum' a b = Either a b
type Prod' a b = (a,b)

加算と乗算の期待される結果の後に同型性までの型代数が続く。例えば、1 + 2、2 + 1、3の同型写像を見ることができます。 1 + 2 = 3 = 2 + 1となる。

data Color = Red | Green | Blue

f :: Sum () Bool -> Color
f (Left ())     = Red
f (Right True)  = Green
f (Right False) = Blue

g :: Color -> Sum () Bool
g Red   = Left ()
g Green = Right True
g Blue  = Right False

f' :: Sum Bool () -> Color
f' (Right ())   = Red
f' (Left True)  = Green
f' (Left False) = Blue

g' :: Color -> Sum Bool ()
g' Red   = Right ()
g' Green = Left True
g' Blue  = Left False

加算と乗算の規則

commutativity、associativity、distributivityの一般的な規則は有効です。なぜなら、以下のタイプの間には同型異形が存在するからです。

-- Commutativity
Sum a b           <=> Sum b a
Prod a b          <=> Prod b a
-- Associativity
Sum (Sum a b) c   <=> Sum a (Sum b c)
Prod (Prod a b) c <=> Prod a (Prod b c)
-- Distributivity
Prod a (Sum b c)  <=> Sum (Prod a b) (Prod a c)

再帰型

これは、リストが[]ように1つの値だけを含むことができるタイプであると見なすと意味があります。 [x]ようにタイプaすべての値。 [x,y]ようにa型の2つの値。等々。私たちがそこから得るべきリストの理論的定義は次のようになります：

-- Not working Haskell code!
data List a = Nil
            | One a
            | Two a a
            | Three a a a 
            ...

木

たとえば、バイナリツリーでも同じことができます。これらを次のように定義すると、

data Tree a = Empty | Node a (Tree a) (Tree a)

次の式が得られます。

ツリー（a）= 1 + a *ツリー（a）*ツリー（a）

同じ置換を何度も繰り返すと、次のシーケンスが得られます。

ツリー（a）= 1 + a + 2（a * a）+5（a * a * a）+ 14（a * a * a * a）+ ...

ここで得られる係数はカタロニア数列に対応し、n番目のカタロニア数は正確にn個のノードを有する可能なバイナリツリーの数である。

デリバティブ

タイプの派生物は、その1つのタイプのコンテキストのタイプのタイプです。これは、可能なあらゆる点で型変数を消して結果を合計すると得られる型です。

一例として、トリプルタイプ(a,a,a)をとり、それを導出して

data OneHoleContextsOfTriple = (a,a,()) | (a,(),a) | ((),a,a)

これは、通常の派生定義と一貫しています。

d / da（a * a * a）= 3 * a * a

このトピックの詳細は、この記事で読むことができます。

関数

関数は代数の指数として見ることができます。私たちが見ることができるように、我々はタイプ取る場合、 a n個のインスタンスと型とb m個のインスタンスと、タイプa -> b 、n個のインスタンスのパワーにメートルを持っています。

例として、 Bool -> Boolは(Bool,Bool)と同型であり、2 * 2 =2²です。

iso1 :: (Bool -> Bool) -> (Bool,Bool)
iso1 f = (f True,f False)

iso2 :: (Bool,Bool) -> (Bool -> Bool)
iso2 (x,y) = (\p -> if p then x else y)

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

Haskell Language
型代数

サーチ…