55

だから私は型の基本的な代数的解釈を理解しています：

Either a b ~ a + b
(a, b) ~ a * b
a -> b ~ b^a
()   ~ 1
Void ~ 0 -- from Data.Void

Bool...そして、これらの関係は、のようなポリモーフィック型とは対照的に、のような具象型に当てはまりますa。また、次の同型に従ってチャーチエンコーディングを変換するだけで、ポリモーフィック型の型シグネチャを具体的な型表現に変換する方法も知っています。

(forall r . (a -> r) -> r) ~ a

だから私が持っている場合：

id :: forall a . a -> a

私はそれが意味しないことを知っていますid ~ a^a、しかしそれは実際に意味します：

id :: forall a . (() -> a) -> a
id ~ ()
   ~ 1

同様に：

pair :: forall r . (a -> b -> r) -> r
pair ~ ((a, b) -> r) - > r
     ~ (a, b)
     ~ a * b

それは私の質問に私をもたらします。このルールの「代数的」解釈とは何ですか。

(forall r . (a -> r) -> r) ~ a

すべての具体的なタイプの同型について、次のような同等の代数規則を指すことができます。

(a, (b, c)) ~ ((a, b), c)
a * (b * c) = (a * b) * c

a -> (b -> c) ~ (a, b) -> c
(c^b)^a = c^(b * a)

しかし、私は次のような代数的平等を理解していません。

(forall r . (a -> r) -> r) ~ a
4

5 に答える 5

30

This is the famous Yoneda lemma for the identity functor.

Check this post for a readable introduction, and any category theory textbook for more.

Briefly, given f :: forall r. (a -> r) -> r you can apply f id to get an a, and conversely, given x :: a you can take ($x) to get forall r. (a -> r) -> r.

These operations are mutually inverse. Proof:

Obviously ($x) id == x. I will show that

($(f id)) == f,

since functions are equal when they are equal on all arguments, let's take x :: a -> r and show that

($(f id)) x == f x i.e.

x (f id) == f x.

Since f is polymorphic, it works as a natural transformation; this is the naturality diagram for f:

               f_A
     Hom(A, A)  →  A
(x.)      ↓        ↓ x
     Hom(A, R)  →  R
               f_R

So x . f == f . (x.).

Plugging identity, (x . f) id == f x. QED

于 2012-05-05T00:42:42.937 に答える
17
于 2012-05-04T22:35:59.517 に答える
8

To (attempt to) answer the actual question (which is less interesting than the answers to the broader issues raised), the question is ill formed because of a "type error"

Either ~ (+) 
(,)    ~ (*)
(->) b ~ flip (^)
()   ~ 1
Void ~ 0

These all map types to integers, and type constructors to functions on naturals. In a sense, you have a functor from the category of types to the category of naturals. In the other direction, you "forget" stuff, since the types preserve algebraic structure while the naturals throw it away. I.e. given Either () () you can get a unique natural, but given that natural, you can get many types.

But this is different:

(forall r . (a -> r) -> r) ~ a

It maps a type to another type! It is not part of the above functor. It's just an isomorphism within the category of types. So let's give that a different symbol, <=>

Now we have

(forall r . (a -> r) -> r) <=> a

Now you note that we can not only send types to nats and arrows to arrows, but also some isomorphisms to other isomorphisms:

(a, (b, c)) <=> ((a, b), c) ~ a * (b * c) = (a * b) * c

But something subtle is going on here. In a sense, the latter isomorphism on pairs is true because the algebraic identity is true. This is to say that the "isomorphism" in the latter simply means that the two types are equivalent under the image of our functor to the nats.

The former isomorphism we need to prove directly, which is where we start to get to the underlying question -- is given our functor to the nats, what does forall r. map to? But the answer is that forall r. is neither a type, nor a meaningful arrow between types.

By introducing forall, we have moved away from first order types. There's no reason to expect that forall should fit in our above Functor, and indeed, it doesn't.

So we can explore, as others have above, why the isomorphism holds (which is itself very interesting) -- but in doing so we've abandoned the algebraic core of the question. A question which can be answered, I think, is, given the category of higher-order types and constructors as arrows between them, what is there meaningful Functor to?

Edit: So now I have another approach which shows why adding polymorphism makes things go nuts. We start by asking a simpler question -- does a given polymorphic type have zero or more than zero inhabitants? This is the type inhabitation problem, and winds up being, via Curry-Howard, a problem in modified realizability, since it's the same thing as asking if a formula in some logic is realizable in an appropriate computational model. Now as that page explains, this is decidable in the simply typed lambda calculus but is PSPACE-complete. But once we move to anything more complicated, by adding polymorphism for example and going to System F, then it goes to undecidable!

So, if we can't decide if an arbitrary type is inhabited at all, then we clearly can't decide how many inhabitants it has!

于 2012-05-07T22:38:13.260 に答える
4

興味深い質問です。完全な答えはありませんが、コメントするには長すぎました。

型署名(forall r. (a -> r) -> r)は私が言っているように表現することができます

名前を付けたいタイプの場合、を取り、生成するr関数を私に与えれば、私はあなたに。を返します。arr

これはどのタイプでも機能する必要がありますが、特定のタイプrにすることもできます。したがって、この巧妙なトリックを引き出す方法は、どこかに座って、関数にフィードし（これにより、私のために生成されます）、それをあなたに返します。aarr

しかし、私がa座っているなら、私はあなたにそれを与えることができます：

あなたが私に1を与えるなら、私はあなたにを与えるでしょうa。

これは型署名1 -> aまたは単にに対応しaます。この非公式の議論によって、私たちは

(forall r. (a -> r) -> r) ~ a

次のステップは、対応する代数式を生成することですが、代数の量が全称記号とどのように相互作用するかはわかりません。専門家を待つ必要があるかもしれません！

于 2012-05-04T18:27:28.323 に答える
4

A few links to the nLab:

Thus, in settings of category theory:

Type               | Modeled¹ as               | In category
-------------------+---------------------------+-------------
Unit               | Terminal object           | CCC
Bottom             | Initial object            |
Record             | Product                   |
Union              | Sum (coproduct)           |
Function           | Exponential               |
-------------------+---------------------------+-------------
Dependent product² | Right adjoint to pullback | LCCC
Dependent sum      | Left adjoint to pullback  |

¹) in appropriate category ─ CCC for total and non-polymorphic subset of Haskell (link), CPO for non-total traits of Haskell (link), LCCC for dependently typed languages.

²) forall quantification is a special case of dependent product:

∀(x :: *). y[x] ~ ∏(x : Set)y[x]

where Set is the universe of all small types.

于 2012-05-06T14:29:44.493 に答える