Haskell:为 zipper 创建类型类

因此，我一直在阅读有关 Haskell(以及其他函数式语言，我想)中的 Zipper 模式来遍历和修改数据结构的一些内容，我认为这将是我磨练创建类型技能的好机会Haskell 中的类，因为
该类可以为我提供一个通用的遍历接口(interface)来编写代码，而与遍历的数据结构无关。

我想我可能需要两个类 - 一个用于根数据结构，一个用于创建的特殊数据结构
遍历第一个:

module Zipper where

class Zipper z where
  go'up :: z -> Maybe z
  go'down :: z -> Maybe z
  go'left :: z -> Maybe z
  go'right :: z -> Maybe z

class Zippable t where
  zipper :: (Zipper z) => t -> z
  get :: (Zipper z) => z -> t
  put :: (Zipper z) => z -> t -> z

但是当我用一些简单的数据结构(如列表)尝试这些时:

-- store a path through a list, with preceding elements stored in reverse
data ListZipper a = ListZipper { preceding :: [a], following :: [a] }

instance Zipper (ListZipper a) where
  go'up ListZipper { preceding = [] } = Nothing
  go'up ListZipper { preceding = a:ps, following = fs } =
      Just $ ListZipper { preceding = ps, following = a:fs }
  go'down ListZipper { following = [] } = Nothing
  go'down ListZipper { preceding = ps, following = a:fs } =
      Just $ ListZipper { preceding = a:ps, following = fs }
  go'left _ = Nothing
  go'right _ = Nothing

instance Zippable ([a]) where
  zipper as = ListZipper { preceding = [], following = as }
  get = following
  put z as = z { following = as }

或者二叉树:

-- binary tree that only stores values at the leaves
data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a
-- store a path down a Tree, with branches not taken stored in reverse
data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a }

instance Zipper (TreeZipper a) where
  go'up TreeZipper { branches = [] } = Nothing
  go'up TreeZipper { branches = (Left l):bs, subtree = r } =
      Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
  go'up TreeZipper { branches = (Right r):bs, subtree = l } =
      Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } }
  go'down TreeZipper { subtree = Leaf a } = Nothing
  go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } =
      Just $ TreeZipper { branches = (Right r):bs, subtree = l }
  go'left TreeZipper { branches = [] } = Nothing
  go'left TreeZipper { branches = (Right r):bs } = Nothing
  go'left TreeZipper { branches = (Left l):bs, subtree = r } =
      Just $ TreeZipper { branches = (Right r):bs, subtree = l }
  go'right TreeZipper { branches = [] } = Nothing
  go'right TreeZipper { branches = (Left l):bs } = Nothing
  go'right TreeZipper { branches = (Right r):bs, subtree = l } =
      Just $ TreeZipper { branches = (Left l):bs, subtree = r }

instance Zippable (Tree a) where
  zipper t = TreeZipper { branches = [], subtree = t }
  get TreeZipper { subtree = s } = s
  put z s = z { subtree = s }

我无法编译它，我的每个 Zippable 实例定义都会出现很多这样的错误:

zipper .hs:28:14:
无法匹配预期的类型“z”
针对推断类型`ListZipper a'
`z' 是一个刚性类型变量，由
Zipper.hs:10:20 中“zipper”的类型签名
在表达式中:ListZipper {preceding = [], following = as}
在`zipper'的定义中:
zipper as = ListZipper {preceding = [], following = as}
在方法“zipper”的定义中

所以我不知道从哪里开始。我怀疑我的问题是我试图绑定(bind)这两个实例
在一起，当 (Zipper z) => 声明只是希望 z 是任何 Zipper 。

最佳答案

(旁白:你的 go'up 命名方案是......创造性的。Haskell 风格通常是驼峰式的。)

你在正确的轨道上。您所写的内容等同于以下内容。

{-# LANGUAGE RankNTypes #-}
instance Zippable [a] where
    zipper = ... :: forall z. (Zipper z) => [a] -> z
    get = ... :: forall z. (Zipper z) => z -> [a]
    set = ... :: forall z. (Zipper z) => z -> [a] -> z

(对于所有类型 z ，给定 Zipper z ，存在一个 zipper :: [a] -> z 。)

您正在尝试定义zipper = ... :: [a] -> ListZipper a，这显然太严格了。

您的代码将使用以下最小更改进行类型检查:

{-# LANGUAGE MultiParamTypeClasses #-}
class (Zipper z) => Zippable z t where
    zipper :: t -> z
    get :: z -> t
    set :: z -> t -> z
instance Zippable (ListZipper a) [a] where
    ...
instance Zippable (TreeZipper a) (Tree a) where
    ...

见 multi-parameter type classes 。这是一个后 Haskell'98 扩展，但 Haskell 实现广泛支持它。

关于Haskell:为 zipper 创建类型类，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/878774/