algorithm - Haskell 递归方案：同时遍历两个结构

Question

我正在尝试使用递归方案编写 Robinson 的统一算法。统一算法采用两种类型并吐出一个结果。类型是：

data TypeF a
    = TypeApplication a a
    | TypeVariable Name
    deriving (Read,Show,Eq,Functor,Foldable,Traversable)
type Type = Fix TypeF

unify :: Type -> Type -> Result
unify = ...

如何使用递归方案优雅地做到这一点？

Answer 1

我只是建议currying和hylomorphism。

data TypeF a
    = TypeApplication a a
    | TypeVariable Name
    deriving (Read,Show,Eq,Functor,Foldable,Traversable)
type Type = Fix TypeF

unify :: (Type, Type) -> Result
unify = hylo algebra coalgebra
    where algebra :: TypeF Result -> Result
          algebra = ...
          coalgebra :: (Type, Type) -> TypeF (Type, Type)
          coalgebra = ...

顺便说一句，我可能会TypeF使用递归方案包如下。

import Data.Functor.Foldable.TH (makeBaseFunctor)

data Type = TypeApplication Type Type
          | TypeVariable Name

makeBaseFunctor ''Type

在这种情况下，这将自动生成您想要的内容，而无需使用 to Fix。