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?
Solo nel caso, per favore, aggiungere il link alla carta. –
@Yasir: aggiunto. Ho trovato un collegamento non paywall funzionante. – nominolo
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. :-) –