Haskell：为Zippers创建类型类

So I've been reading a bit about the Zipper pattern in Haskell (and other functional languages, I suppose) to traverse and modify a data structure, and I thought that this would be a good chance for me to hone my skills at creating type classes in Haskell, since the class could present a common traversal interface for me to write code to, independent of the data structure traversed.

所以我一直在阅读Haskell中的Zipper模式(以及其他函数语言,我想)来遍历和修改数据结构,我认为这是一个很好的机会让我磨练我的技能来创建类型Haskell中的类,因为类可以为我编写代码提供一个通用的遍历接口,而不依赖于遍历的数据结构。

I thought I'd probably need two classes - one for the root data structure, and one for the special data structure created to traverse the first:

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

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

But when I tried these with some simple datastructures like a list:

但是当我尝试使用一些像列表这样的简单数据结构时:

-- 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 }

Or a binary tree:

或二叉树:

-- 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 }

I couldn't get it to compile, I'd just get a lot of errors like this for each of my Zippable instance definitions:

我无法编译,我只是为我的每个Zippable实例定义得到了很多这样的错误:

Zipper.hs:28:14:
    Couldn't match expected type `z'
           against inferred type `ListZipper a'
      `z' is a rigid type variable bound by
          the type signature for `zipper' at Zipper.hs:10:20
    In the expression: ListZipper {preceding = [], following = as}
    In the definition of `zipper':
        zipper as = ListZipper {preceding = [], following = as}
    In the definition for method `zipper'

So I'm not sure where to go from here. I suspect that my issue is that I'm trying to bind these two instances together, when the (Zipper z) => declaration just wants z to be any Zipper.

所以我不确定从哪里开始。我怀疑我的问题是我正在尝试将这两个实例绑定在一起,当(Zipper z)=>声明只想让z成为任何Zipper时。

2 个解决方案

#1

(Aside: your go'up naming scheme is... inventive. Haskell style is usually camelCase.)

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

You're on the right track. What you've written is equivalent to the below.

你走在正确的轨道上。你写的内容相当于下面的内容。

{-# 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

(For all types z, given Zipper z, there exists a zipper :: [a] -> z.)

(对于所有类型z,给定Zipper z,存在拉链:: [a] - > z。)

You're tring to define zipper = ... :: [a] -> ListZipper a, which is clearly too restrictive.

你要定义zipper = ... :: [a] - > ListZipper a,这显然限制太多了。

Your code will typecheck with the following minimal changes:

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

{-# 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
    ...

See multi-parameter type classes. It's a post-Haskell'98 extension, but Haskell implementations widely support it.

请参阅多参数类型类。它是后Haskell'98扩展,但Haskell实现广泛支持它。

#2

You can also use type synonym families instead of multi-parameter type classes and functional dependencies. In cases like these they offer a cleaner and easier-to-understand solution. In that case the class and instance would become:

您还可以使用类型同义词系列,而不是多参数类型类和功能依赖项。在这些情况下,它们提供了更清晰,更易于理解的解决方案。在这种情况下,类和实例将变为:

class Zippable t where
  type ZipperType t :: *
  enter :: t -> ZipperType t
  focus :: ZipperType t -> t

instance Zippable [a] where
  type ZipperType [a] = ListZipper a
  enter = ...
  focus = ...

Fun with type functions is an excellent introduction to type synonym families for people already familiar with Haskell. I also wrote an article on how type synonym families can often be used instead of functional dependencies a while ago.

类型函数的乐趣是对已经熟悉Haskell的人类型同义词系列的一个很好的介绍。我还写了一篇关于如何经常使用类型同义词系列而不是之前的函数依赖项的文章。

Hope this helps!

希望这可以帮助!

#1