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

Question

在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 ? ?)

简化等递归的最佳解决方案是什么？我应该定义一个类似于数据类型的折叠的通用遍历,还是有一个标准的递归模式来定义这些函数？

Answer 1

你尝试过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).