대수 데이터 형식의 상향식 상향 탐색

Question

하스켈에서 대수 데이터 형식을 처리 할 때 데이터 형식을 통해 접을 때 특정 재귀 적 탐색이 캡처되지 않습니다.

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

이 재귀 방식 평가 또는 발견 리터럴 같은 재귀에 대한 간결한 대답을 제공합니다 : 예를 들어, 내가 명제 논리의 수식을 나타내는 간단한 데이터 유형 및 그 위에 정의 된 배를 가정

그러나 데이터 형식을 "스윕"하고 싶을 때는 너무 좋지 않습니다.

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

물론, 잘못된 결과를 생성 단순화 정의 접힘 사용 : 이하, SIMP 필요한 패턴 매칭에 의해 정의 된 보조 기능이다.

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

같은 재귀에 최적의 솔루션이을 단순화 무엇입니까 : 예를 들어, 다음은 동일하지 않습니다? 데이터 유형에 대한 fold와 비슷한 generic traversal을 정의해야합니까? 아니면 그러한 함수를 정의하기위한 표준 재귀 패턴이 있습니까?

Answer 1

Uniplate을 사용해 보셨습니까? 단일 유형에서만 작동하는 작업의 경우 고정 점까지 상향식 재 작성 및 재 작성을 수행 할 수 있습니다. 예를 들어

:

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" 

관련 기능 당신은 transform 및 rewrite이기 때문.

유니 플레이트에 대한 자세한 내용은 a paper (PDF)도 있습니다.