При работе с большими алгебраическими типами данных в 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 φ ψ)
Какое наилучшее решение для рекурсий типа упрощает ? Должен ли я определить общий обход, аналогичный свертке по типу данных, или существует стандартный шаблон рекурсии для определения таких функций?