Рекурсивный восходящий обход алгебраических типов данных

При работе с большими алгебраическими типами данных в 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 φ ψ)

Какое наилучшее решение для рекурсий типа упрощает ? Должен ли я определить общий обход, аналогичный свертке по типу данных, или существует стандартный шаблон рекурсии для определения таких функций?

7
задан HaskellElephant 25 December 2011 в 22:02
поделиться