2011-02-05 19 views
7

Quando si ha a che fare con tipi di dati algebrici consistenti in Haskell, vi è un particolare attraversamento ricorsivo non catturato ripiegando il tipo di dati. Per esempio, supponiamo di avere un semplice tipo di dati che rappresentano formule in logica proposizionale, e una piega definita su di esso:Traversal bottom-up ricorsivo di tipi di dati algebrici

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

Questo schema ricorsione fornisce una risposta succinta per ricorsioni come valutazione o trovare letterali:

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) 

Tuttavia, non se la passano così bene quando voglio "spazzare" il tipo di dati. Nel seguito, simp è una funzione ausiliaria definita da necessario pattern-matching:

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

Utilizzando una piega per definire semplificare, naturalmente, genera risultati non corretti. Per esempio, il seguente non è equivalente:

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

Qual è la soluzione migliore per ricorsioni come semplificare? Devo definisco un attraversamento generico simile alla piega sul tipo di dati, o c'è un motivo ricorsione standard per definire tali funzioni?

risposta

7

Hai provato Uniplate? Per operazioni che funzionano solo su un singolo tipo, è possibile eseguire riscritture dal basso verso l'alto e riscrive fino a un punto fisso.

Ad esempio:

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" 

Le funzioni rilevanti per voi sono transform e rewrite.

Per una documentazione più approfondita circa UniPlate c'è anche a paper (PDF).

+0

Solo nel caso, per favore, aggiungere il link alla carta. –

+0

@Yasir: aggiunto. Ho trovato un collegamento non paywall funzionante. – nominolo

+0

Puoi semplicemente aggiungere il link come commento, nel caso in cui cambi idea e aggiorni la domanda con dati più utili in seguito (eventualmente aggiungendo il link). In questo modo non otterrai la tua risposta in CW. :-) –

Problemi correlati