Cebirsel veri türlerinin ardışık aşağıdan yukarıya geçişi

Question

Haskell'de büyük boyutlu cebirsel veri türleri ile uğraşırken, veri türü üzerinde katlanarak yakalanmayan belirli bir tekrarlamalı geçiş vardır.

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) 

:

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' ψ) 

Bu yineleme şeması değerlendirme ve bulma değişmezleri gibi recursions bir öz yanıt sağlar; Örneğin, önermeler mantığı formülleri temsil basit bir veri türü ve üzerinde oluşturulan bir kat olduğunu varsayalım

Ancak, veri türünü "taramak" istediğimde çok iyi geçmiyor.

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 φ   = φ 

tabii ki, hatalı sonuçlar üretir, basitleştirmek tanımlamak için bir kat kullanma: Aşağıda, simp gerekli model eşleştirme ile tanımlanan bir yardımcı fonksiyonudur.

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

gibi recursions için en iyi çözüm basitleştirmek nedir: Örneğin, aşağıdaki eşdeğer değildir? Veri tipi üzerinden katlamaya benzer bir genel geçiş tanımlamalı mıyım yoksa bu işlevleri tanımlamak için standart bir yineleme modeli var mı?

Answer 1

Uniplate'u denediniz mi? Yalnızca tek bir tipte çalışan işlemler için aşağıdan-yukarıya yeniden yazmalar yapabilir ve sabit bir noktaya kadar yeniden yazar. Örneğin

:

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" 

ilgili fonksiyonları transform ve rewrite vardır için.

Uniplate hakkında daha ayrıntılı bilgi için ayrıca a paper (PDF) da var.