证明 Haskell 镜头库中声明的类型等效性

Question

type Getting b a b  = (b -> Const b b) -> (a -> Const b a)

-- ... equivalent to: (b ->       b  ) -> (a ->       b  )

-- ... equivalent to:                     (a ->       b  )

问题：为什么(b -> b) -> (a -> b)等同于(a -> b)？

Answer 1

类型表示 "You give me a b -> b and an a, and I'll give you a b." 具有该类型的函数可以用它的 b -> b 做什么？两个选项：

完全忽略该函数
将其应用于 b

如何获得 b 以应用该函数？您使用 a 生成一个。所以无论哪种方式，它都必须完成 a -> b.

的工作

这里有一些代码可以证明（编辑：不完全）同构。

in :: ((b -> b) -> a -> b) -> (a -> b)
in f x = f id x

out :: (a -> b) -> ((b -> b) -> a -> b)
out f g x = g (f x)

Answer 2

教程对此不是很准确。这是 Getting 的完整定义：

type Getting r s a = (a -> Const r a) -> s -> Const r s

剥离 newtype 噪声，

Getting r s a ~= (a -> r) -> s -> r

你应该从中得到的有趣的同构如下：

(forall r. Getting r s a) ~= s -> a

在现已删除的评论中，chi 指出这是 Yoneda lemma.

的特例

同构由

见证

fromGetting :: Getting a s a -> (s -> a)
fromGetting g = getConst . g Const
           -- ~= g id

-- Note that the type of fromGetting is a harmless generalization of
-- fromGetting :: (forall r. Getting r s a) -> (s -> a)

toGetting :: (s -> a) -> Getting r s a
toGetting f g = Const . getConst . g . f
           -- ~= g . f

-- Note that you can read the signature of toGetting as
-- toGetting :: (s -> a) -> (forall r. Getting r s a)

fromGetting 和 toGetting 都没有 rank-2 类型，但是要描述同构， forall 是必不可少的。为什么这是同构？

一方面很简单：忽略 Const 噪声，

  fromGetting (toGetting f)
= toGetting f id
= id . f
= f

另一边比较棘手。

  toGetting (fromGetting f)
= toGetting (f id)
= \g -> toGetting (f id) g
= \g -> g . f id

为什么这等同于 f？ forall 是这里的关键：

f :: forall r. Getting r s a
  -- forall r. (a -> r) -> s -> r

f 无法生成 r，除非将传递的函数（我们称之为 p）应用于 a 类型的值。除了 p 和 s 类型的值外，它什么也没有给出。所以 f 除了从 s 中提取 a 并将 p 应用于结果之外，实际上什么也做不了。即f p必须"factor"组成两个函数：

f p = p . h

所以

g . f id = g . (id . h) = g . h = f g

证明 Haskell 镜头库中声明的类型等效性

Justifying a Type Equivalency Asserted in Haskell Lens Library

haskell

haskell-lens