代数的データ型の再帰的ボトムアップトラバーサル

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を使用すると、誤った結果が生成されます。たとえば、以下は同等ではありません:

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

次のような再帰に対する最良の解決策は何ですか 簡素化?データ型の折り畳みに似た汎用トラバーサルを定義する必要がありますか、またはそのような関数を定義するための標準的な再帰パターンはありますか？

Answer 1

あなたは試しましたか ユニプレート?単一の型でのみ動作する操作の場合、ボトムアップ書き換えと固定小数点までの書き換えを実行できます。

例えば:

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）.