是什么让 Haskell 中的两个类型表达式等价？

Question

所以有人问我这 3 个类型表达式在 Haskell 中是否等价：

τ1 = (a -> a) -> (a -> a -> a)
τ2 = a -> a -> ((a -> a) -> a)
τ3 = a -> a -> (a -> (a -> a))

如果我去掉括号我就剩下这个

τ1 = (a -> a) -> a -> a -> a
τ2 = a -> a -> (a -> a) -> a
τ3 = a -> a -> a -> a -> a

所以对我来说很明显它们彼此不同。但是，根据问题，这两个答案是错误的：

τ1 !≡ τ2 !≡ τ3 !≡ τ1
τ1 !≡ τ2 ≡ τ3

所以我在这里有点困惑，正确答案是什么？为什么？

Answer 1

我同意你的评价。这三种类型都不同，您已正确简化它们。如果您认为提供的答案与您的不一致，您确定您正在阅读问题和答案吗？

Answer 2

确实，由于您提到的原因，它们都是不同的。

我们甚至可以要求GHC确认。（下面，我选择了a ~ Int来获得一个封闭类型。）

> import Data.Type.Equality
> type T1 a = (a -> a) -> (a -> a -> a)
> type T2 a = a -> a -> ((a -> a) -> a)
> type T3 a = a -> a -> (a -> (a -> a))
> :kind! T1 Int == T2 Int
T1 Int == T2 Int :: Bool
= 'False
> :kind! T1 Int == T3 Int
T1 Int == T3 Int :: Bool
= 'False
> :kind! T2 Int == T3 Int
T2 Int == T3 Int :: Bool
= 'False

Answer 3

三种类型...

type T1 a = (a -> a) -> (a -> a -> a)
type T2 a = a -> a -> ((a -> a) -> a)
type T3 a = a -> a -> (a -> (a -> a))

...确实是不同的。但是，T1 和 T2 是等价的 ，因为 它们之间存在同构，这相当于改变参数的顺序：

GHCi> :info T1
type T1 a = (a -> a) -> a -> a -> a
    -- Defined at <interactive>:12:1
GHCi> :info T2
type T2 a = a -> a -> (a -> a) -> a
    -- Defined at <interactive>:13:1

GHCi> :t flip
flip :: (a -> b -> c) -> b -> a -> c
GHCi> :t (flip .)
(flip .) :: (a1 -> a2 -> b -> c) -> a1 -> b -> a2 -> c

GHCi> f = (flip .) . flip
GHCi> :t f :: T1 a -> T2 a
f :: T1 a -> T2 a :: T1 a -> T2 a
GHCi> g = flip . (flip .)
GHCi> :t g :: T2 a -> T1 a
g :: T2 a -> T1 a :: T2 a -> T1 a

然后我们可以证明 f 和 g 是相反的（即 g . f = id 和 f . g = id）：

f . g
(flip .) . flip . flip . (flip .)
(flip .) . (flip .) -- flip . flip = id
id -- (flip .) . (flip .) = \h -> \x -> flip (flip (h x)) = \h -> \x -> h x = id

g . f
flip . (flip .) . (flip .) . flip
flip . flip 
id

是什么让 Haskell 中的两个类型表达式等价？

What makes two type expressions in Haskell equivalent?

haskell

types

equivalence