GMapEither 类型族示例是否真的不符合 Either 直觉？

Question

GHC 用户指南在类型族的 Data instance declarations 部分中显示了此示例：

data instance GMap (Either a b) v = GMapEither (GMap a v) (GMap b v)

我习惯于每当我们想要左值或右值时都使用 Either 类型，所以我希望 GMapEither 以某种方式提供左或右变体，但它似乎总是同时拥有：

{-# LANGUAGE TypeFamilies #-}

module Main where

import qualified Data.HashMap.Strict as H

data family GMap k :: * -> *

data instance  GMap Int Int = GMapIntInt (H.HashMap Int Int)
                            deriving (Show, Eq)

data instance  GMap String Int = GMapStringInt (H.HashMap String
                                                  Int)
                               deriving (Show, Eq)

data instance  GMap (Either a b) v = GMapEither (GMap a v)
                                                (GMap b v)

main :: IO ()
main = do
  let m = GMapIntInt H.empty
  print m
  let m2 = GMapStringInt H.empty
  print m2
  let m3 = GMapEither m m2
  let (GMapEither m3l m3r) = m3
  print m3l
  print m3r

我是否理解正确，在这里使用元组更合适，例如：

data instance  GMap (a, b) v = GMapTuple (GMap a v) (GMap b v)

我认为这可能会提供更好的直觉。

Answer 1

当我们进行抽象时，它通常具有所谓的"semantic domain"，这是抽象应该表示的东西。抽象的属性应该匹配语义域的属性。（当抽象具有类型 class 时，它被称为 type class morphism）。

GMap 显然是在试图表示某种映射操作。映射的原型示例是函数。也有像 Data.Map 这样的有限映射，但它也有点假装是一种特殊的函数。

所以无论如何，我们应该期望 GMap a b 具有与函数 a -> b 相似的属性。如果 GMap (a,b) v 被定义为等于 (GMap a v, GMap b v)，那么我们应该期望在语义域中存在相应的同构。所以只需将所有 GMap 转换为函数箭头 ->，我们得到：

f' :: ((a,b) -> v) -> (a -> v, b -> v)
g' :: (a -> v, b -> v) -> ((a,b) -> v)

g' 很容易进行类型检查，但是有两种不同的实现方式，无法选择一种：

g' :: (a -> v, b -> v) -> ((a,b) -> v)
g' = (tl, tr) (x,y) = tl x
-- and
g' = (tl, tr) (x,y) = tr y

和f'是完全不可能的

f' :: ((a,b) -> v) -> (a -> v, b -> v)
f' t = (\a -> ??? , \b -> ???)

在左边???，我们有一个a，我们需要一个v，但是我们只能构造一个v，如果我们给t 一个 a 和一个 b，我们没有任何地方可以得到我们需要的 b。同样的事情发生在元组的右边部分。

没有明确的方法可以在一对 (a,b) -> v 的函数和一对函数之间来回切换。因此，将这两件事声明为 GMap 似乎是不正确的。同样的事情发生在像 Data.Map 这样的有限映射上（你可以得到一些东西来进行类型检查，但它不会最终成为真正的同构，因为 f' . g' /= id （反之亦然，我不记得是哪个） ).

而(Either a b -> v) -> (a -> v, b -> v)的同构很容易写

f :: (Either a b -> v) -> (a -> v, b -> v)
f t = (t . Left, t . Right)

g :: (a -> v, b -> v) -> (Either a b -> v)
g (l, r) (Left x) = l x
g (l, r) (Right y) = r y

这种语义域的东西对于脚踏实地的程序员来说可能有点抽象。为什么我们能不能写出这个同构很重要？但是当您尝试让 GMap 做任何事情时，您会发现问题很快就会以实际的方式出现。

让我们开始捆绑数据系列，我们应该能够编写几个非常简单的操作：

class MapKey k where
    data family GMap k :: * -> *

    empty :: GMap k v
    lookup :: GMap k v -> k -> Maybe v
    insert :: k -> v -> GMap k v -> GMap k v

还有一个非常简单的基本案例

instance MapKey Int where
    data GMap Int v = GMapInt (Int -> Maybe v)
    empty = GMapInt (const Nothing)
    lookup (GMapInt f) x = f x
    insert x v (GMapInt f) = GMapInt (\y -> if x == y then Just v else f y)

如果我们尝试

instance (MapKey a, MapKey b) => MapKey (a,b) where
    data GMap (a,b) v = GMapTuple (GMap a v) (GMap b v)
    empty = GMapTuple empty empty
    lookup (GMapTuple l r) (x,y) =
        -- several implementations here, but maybe we could do
        lookup l x `mplus` lookup r y

    insert (x,y) v (GMapTuple l r) = GMapTuple (insert x v l) (insert y v r)

看似有理，实则行不通

 >>> lookup (insert (1 :: Int, 2 :: Int) "value" empty) (1,3)
 Just "value"

应该给出 Nothing，因为我们插入了 (1,2)，而不是 (1,3)。你可以说这只是我实现中的一个错误，但我敢说你写了一个可以工作的。

类型和代数之间有一个很好的对应关系，可以指导您了解类型应该如何转换。这里 ~~ 表示 "analogous to":

Either a b  ~~  a + b
(a,b)       ~~  a * b
a -> b      ~~  b ^ a

所以

Map ((a,b) -> v) ~~ v^(a*b)
                  = (v^a)^b
                   ~~ Map b (Map a v)

也就是说，我们应该期望元组映射和嵌套映射之间存在同构。同样：

Map (Either a b -> v) ~~ v^(a+b)
                       = v^a * v^b
                        ~~ (Map v a, Map v b)

并且来自联积 (Either) 的映射和一对映射之间应该有很好的同构。

这非常深入，值得研究哪些事物与其他事物同构。

进一步阅读：

克里斯·泰勒，The Algebra of Algebraic Data Types
丹·皮波尼，Memoizing Polymorphic Functions with High School Algebra and Quantifiers
康纳尔·埃利奥特，Denotational Design with Type Class Morphisms

GMapEither 类型族示例是否真的不符合 Either 直觉？

Does GMapEither type family example not really correspond Either intuition?

haskell

type-families