如何对实例为递归数据类型的类型类进行模式匹配？

Question

此问题是的后续问题。

我正在启动一个基于一阶逻辑的宠物项目，并决定为此目的使用 Haskell。我的第一个障碍是定义一个 'formula of first order logic'，因此数据类型：

data Formula v  = Belong v v                      -- x in y
                | Bot                             -- False
                | Imply (Formula v) (Formula v)   -- p -> q
                | Forall v (Formula v)            -- forall x, p

但是，我不愿意根据实现细节编写代码，而是宁愿抽象掉细节，以防我改变主意，或者如果我想通过替代实现重用功能，因此类型类:

class FirstOrder m where
  belong    :: v -> v -> m v
  bot       :: m v
  imply     :: m v -> m v -> m v
  forall    :: v -> m v -> m v
  asFormula :: m v -> Formula v

我添加了最后一个函数 asFormula 以使用 ViewPatterns（如上面 link 中所建议的），以便能够对值进行模式匹配这个类型类。

现在假设我想定义一个简单的函数：

subst :: (FirstOrder m) => (v -> w) -> m v -> m w

根据给定的映射 f::v -> w（感觉像 fmap）替换公式中的变量，因此公式 belong x y 映射到 belong (f x) (f y) 等。然后使用 ViewPatterns:

subst f (asFormula -> Belong x y) = belong (f x) (f y)

到目前为止一切顺利...

但是，当尝试写入 subst f p->q = (subst f p) -> (subst f q):

subst f (asFormula -> Imply p q)  = imply (subst f p) (subst f q)

我得到一个类型错误，后来想到它是非常有意义的：模式匹配将 p 和 q 绑定到 Formula v 类型的元素而不是所需的输入 m v。

现在我可以看到问题了，甚至可以想办法通过向类型类添加一个 fromFormula 函数来转换回类型 m v 来解决它，但我在想这个从性能的角度来看是疯狂的（就像 asFormula 请注意一样疯狂），为了保持代码的通用性要付出巨大的代价。

所以我现在在这里，试图通过自由代数（递归数据类型）上的结构递归来定义一个简单的函数，但我希望抽象出实现细节（并从类型类而不是数据类型中编写代码）把我置于一个似乎不可能的位置。

有出路吗，还是我应该忘记抽象并使用递归数据类型？

Answer 1

这看起来过于笼统，但我们还是忽略它吧。

您可以使用显式 F-(co-) 代数和不动点来求解。

data FormulaF v k
   = Belong v v                      -- x in y
   | Bot                             -- False
   | Imply (k v) (k v)               -- p -> q
   | Forall v (k v)                  -- forall x, p

newtype Formula v = Formula (FormulaF v Formula)      
   -- fixed point. You might not need it, but it's nice to have.
   --

那么，你可以做

class FirstOrder m where
  belong    :: v -> v -> m v
  bot       :: m v
  imply     :: m v -> m v -> m v
  forall    :: v -> m v -> m v
  asFormula :: m v -> FormulaF v m

和

subst :: (FirstOrder m) => (v -> w) -> m v -> m w
subst f (asFormula -> Belong x y) = belong (f x) (f y)
subst f (asFormula -> Imply p q)  = imply (subst f p) (subst f q)

现在应该可以工作了，因为 asFormula 不会递归地将整个 m v 转换为完整的公式，而是转换为表面上看起来像公式的 FormulaF v m （非常你模式匹配的第一个构造函数，比如 Imply)，但在内部深处仍然看起来像 m v.

如果您真的想采用这种过于笼统的方法，也许您应该看看 recursion-schemes、F-代数和 F-余代数，以及它们相关的 cata-/ana-/hylo-/para-/whatever 态射。

最后，我建议避免尝试在 FP 中采用 OOP 设计模式。有时你可以用这种方式硬塞一些东西，但它通常是单调的。例如，在 Haskell 中，我们非常习惯具有固定数量构造函数的类型（但是一组开放的函数对它们进行操作），就像在 OOP 接口中具有固定数量的方法（但是一个开放的子类集）。可以尝试概括这一点，但它很复杂，应该只在需要时才做。

如何对实例为递归数据类型的类型类进行模式匹配？

How to pattern match against typeclass whose instance are recursive data types?

haskell

pattern-matching

typeclass

recursive-datastructures