是否有一个类型类可以改变层次结构的形状？

Question

我正在处理一些分层数据，这里是一个人为的例子：

data Item a =
    Leaf a
    | ListItems [Item a]
    | DoubleItem (Item a) (Item a)
    | TripleItem (Item a) (Item a) (Item a)

我发现自己经常编写这样的代码：

removeDoubles :: Item a -> Item a
removeDoubles x@(Leaf _) = x
removeDoubles (ListItems xs) = ListItems $ removeDoubles <$> xs
removeDoubles (DoubleItem x y) = ListItems [removeDoubles x, removeDoubles y]
removeDoubles (TripleItem x y z) = TripleItem (removeDoubles x) (removeDoubles y) (removeDoubles z)

removeTriples :: Item a -> Item a
removeTriples x@(Leaf _) = x
removeTriples (ListItems xs) = ListItems $ removeTriples <$> xs
removeTriples (DoubleItem x y) = DoubleItem (removeTriples x) (removeTriples y)
removeTriples (TripleItem x y z) = ListItems [removeDoubles x, removeDoubles y, removeDoubles z]

这两个函数之间显然存在一些重叠，并且如果我开始向

Item

添加更多构造函数，这种方法也不是很稳健。我应该使用一些类型类来帮助减少这种重复吗？我正在想象类似的东西：

removeDoubles :: Item a -> Item a
removeDoubles (DoubleItem x y) = ListItems [removeDoubles x, removeDoubles y]
removeDoubles x = traverseHierarchy removeDoubles x

Functor

、

Traversable

等似乎是围绕改变

a

的类型而设计的，而我对映射

a -> something

不太感兴趣，而对改变这个层次结构的形状更感兴趣。

感谢您的帮助！

Answer 1

我认为你正在寻找一种变形现象。有了更多的形式和库工具，下面的想法可以被概括并且自动化，但是对于您的特定任务，可以自动生成的代码类似于

data Item a =
  Leaf a
  | ListItems [Item a]
  | DoubleItem (Item a) (Item a)
  | TripleItem (Item a) (Item a) (Item a)

cata :: (a -> b) -- Leaf
     -> ([b] -> b) -- ListItems
     -> (b -> b -> b) -- DoubleItem
     -> (b -> b -> b -> b) -- TripleItem
     -> Item a
     -> b
cata leaf list double triple = go
  where go (Leaf x) = leaf x
        go (ListItems xs) = list (map go xs)
        go (DoubleItem x y) = double (go x) (go y)
        go (TripleItem x y z) = triple (go x) (go y) (go z)

这里

cata

概括了递归折叠结构的思想，与修改层次结构（例如删除双精度）无关。但是您可以使用这种通用机制轻松实现您的两个特定目标，而无需重复或显式递归：

removeDoubles = cata Leaf ListItems lift TripleItem
  where lift x y = ListItems [x, y]

removeTriples = cata Leaf ListItems DoubleItem lift
  where lift x y z = ListItems [x, y, z]

cata

是称为“递归方案”的更大概念系列的一部分。我确信有很多文章试图解释这些概念，但递归方案简介是我喜欢的一篇。实现这些概念的 Haskell 库，包括为您的类型自动生成

cata

函数，是

recursion-schemes

。