algorithm - Haskell 递归方案 : Traverse two structures simultaneously

Question

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

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)和同态。

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，使用 recursion-schemes包。

import Data.Functor.Foldable.TH (makeBaseFunctor)

data Type = TypeApplication Type Type
          | TypeVariable Name

makeBaseFunctor ''Type

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