代数数据类型的自下而上递归遍历

Question

代数数据类型的自下而上递归遍历

haskellrecursionfoldalgebraic-data-types

7

当处理较大的代数数据类型时，Haskell中存在一种特定的递归遍历方式，无法通过对数据类型进行折叠来捕获。例如，假设我有一个简单的数据类型，用于表示命题逻辑中的公式，并定义了一个在其上进行折叠的函数：

type FAlgebra α φ =
 (φ, φ,                -- False, True
  α -> φ,              -- Atom
  φ -> φ,              -- Negation
  φ -> φ -> φ,         -- Conjunction
  φ -> φ -> φ,         -- Disjunction
  φ -> φ -> φ,         -- Implication
  φ -> φ -> φ)         -- Bi-implication

fold :: FAlgebra α φ -> Form α -> φ
fold (f,t,lit,not,con,dis,imp,iff) = fold' where
 fold' (Fls)     = f
 fold' (Tru)     = t
 fold' (Lit α)   = lit α
 fold' (Not φ)   = not (fold' φ)
 fold' (Con φ ψ) = con (fold' φ) (fold' ψ)
 fold' (Dis φ ψ) = dis (fold' φ) (fold' ψ)
 fold' (Imp φ ψ) = imp (fold' φ) (fold' ψ)
 fold' (Iff φ ψ) = iff (fold' φ) (fold' ψ)

这个递归模式为像求值或查找字面量的递归提供了一个简洁的答案：

eval :: (Ord α) => Map α Bool -> Form α -> Bool
eval v = fold (False, True, (fromJust . flip M.lookup v),
               not, (&&), (||), ((||) . not), (==))

literals :: (Ord α) => Form α -> Set α
literals = fold (S.empty, S.empty, S.singleton, id,
                 S.union, S.union, S.union, S.union)

然而，当我希望“扫描”数据类型时，它的表现就不那么好了。在下面的代码中，simp是一个必要模式匹配定义的辅助函数:

simplify :: Form α -> Form α
simplify (Not φ)   = simp (Not (simplify φ))
simplify (Con φ ψ) = simp (Con (simplify φ) (simplify ψ))
simplify (Dis φ ψ) = simp (Dis (simplify φ) (simplify ψ))
simplify (Imp φ ψ) = simp (Imp (simplify φ) (simplify ψ))
simplify (Iff φ ψ) = simp (Imp (simplify φ) (simplify ψ))
simplify φ         = φ

使用折叠定义简化，当然会产生不正确的结果。例如，以下内容并不等同：

simplify = fold (Fls, Tru, Lit, (simp . Not), con Con, con Dis, con Imp, con Iff)
 where con f φ ψ = simp (f φ ψ)

如何处理像simplify这样的递归问题？我应该定义一个类似于对数据类型进行折叠的通用遍历，还是有一种标准的递归模式来定义这样的函数？

- emi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nominolo · Accepted Answer

你尝试过使用 Uniplate 吗？对于只针对单一类型的操作，它可以执行自底向上的重写和重写直到达到固定点。

例如：

import Data.Generics.Uniplate.Direct
import qualified Data.Map as M

data Form a = Fls | Tru | Lit a
            | Not (Form a)
            | Con (Form a) (Form a)
            | Dis (Form a) (Form a)
            -- etc.
  deriving (Show, Eq)

instance Uniplate (Form a) where
  uniplate (Not f) = plate Not |* f
  uniplate (Con f1 f2) = plate Con |* f1 |* f2
  uniplate (Dis f1 f2) = plate Dis |* f1 |* f2
  -- one case for each constructor that may contain nested (Form a)s
  uniplate x = plate x

simplify :: Form a -> Form a 
simplify = transform simp
 where
   simp (Not (Not f)) = f
   simp (Not Fls) = Tru
   simp (Not Tru) = Fls
   simp x = x

test =
  simplify (Not (Not (Not (Not (Lit "a"))))) == Lit "a"

您需要了解的相关函数是 transform 和 rewrite。

如果您想深入了解Uniplate，还可以阅读一篇论文（PDF）。