하스켈로 정규형 정의하기

Question

표현식을 얻고 표준형으로 변환하려고합니다. 당신이 그에없는 입력을 제공하는 경우

Σ (A * 나) // 제품 이제

의 합계 : 더 나은 내 목적을 명확히하기 위해,이처럼 표현에 대한 일반적인 스타일을 정의 가정 형식 : (a + b) * (c + d)를 사용하려면 먼저 정규화해야합니다. (실제로는 간단한 예일 뿐이며 제 경우는 아닙니다) 이제 ML로 이미 작성된 코드가 있습니다. 도입니다. 다음은 몇 가지 snipets을 볼 수, 하스켈이 코드를 더 깔끔하게 할 수 있도록 할 수있는 모든 기능을 소개 않습니다되어

rew(p_choice(x,p_nil)) = rew(x) | 
rew(p_choice(p_nil,x)) = rew(x) | 
rew(p_sum(d,p_nil)) = p_nil | 
rew(p_sum(d,p_choice(x,y))) = rew(p_choice(rew(p_sum(d,x)),rew(p_sum(d,y)))) 
rew(p_cond(b,p_nil,p_nil)) = p_nil | 
rew(p_cond(b,p_choice(x,y),p_nil)) =rew(p_choice(rew(p_cond(b,x,p_nil)),rew(p_cond(b,y,p_nil)))) | 
rew(p_cond(b,p_sum(x,y),p_nil)) = rew(p_sum(x,rew(p_cond(b,y,p_nil)))) | 
rew(p_cond(b1,p_cond(b2,x,p_nil),p_nil)) = rew(p_cond(b1 andalso b2, x,p_nil)) | 
rew(p_cond(b,x,p_nil)) = p_cond(b,x,p_nil) | 
rew(p_cond(b,x,y)) = 
    rew(p_choice(rew(p_cond(b,x,p_nil)),rew(p_cond(not(b),y,p_nil)))) 

내 질문?

Answer 1

하스켈의 패턴 일치 설비는 매우 유사하며 가장 큰 하스켈 제외 (typeclasses, lazyness 등)가 도움이 될 것이라고 생각하지 않습니다. 즉 ML에서 일을 단순화하는 방법이있을 수 있습니다.

한 가지 고려해야 할 점은 작은 단계로 처리를 나누는 것입니다. 현재 상황이 왼쪽 또는 오른쪽 인수에 따라 일부 중복이 있습니다. 사물에 대한 하나의 특정 순서를 선택하는 중간 표준 양식으로 변형 해 볼 수 있습니다.

또 다른 트릭은 재귀에서 각 단계의 처리를 분리하므로 트리 탐색과 노드 처리를 섞지 않습니다. 각 노드에 대해 stp를 처리하는 함수를 작성한 다음 별도의 fold 함수를 사용하여 모든 것을 묶을 수 있습니다.

data Tree = Leaf Int | Node Tree Tree 

directsum :: Tree -> Int 
directSum (Leaf n) = n 
directsum (Node a b) = (directsum a) + (directsum b) 

-- vs 

foldtree :: (Int -> r) -> (r -> r -> r) -> Tree -> b 
foldtree onLeaf onNode t = 
    go t 
    where 
    go (Leaf n) = onLeaf n 
    go (Tree a b) = onNode (go a) (go b) 

foldedSum :: Tree -> Int 
foldedsum t = 
    foldtree leafsum nodesum t 
    where 
    leafsum n = n 
    nodesum a b = a + b