Control.MonadPlus.Free 불필요한 배포없이

Question

난 ANDY에 매핑 된 >>= 및 mplus이 매핑 된 Prolog와 같은 AND/OR 의사 결정 트리를 구성하기 위해 EDSL을 생성하기 위해 무료 모나드를 사용하려고합니다. 내가 A AND (B OR C) AND (D OR E) 같은 것을 설명 할 수 있기를 원하지만, 이것을 distributivity로 바꾸어 (A AND B AND D) OR (A AND B AND E) OR (A AND C AND D) OR (A AND C AND E)으로 바꾸고 싶지는 않습니다. 궁극적으로, 나는 solver가 다룰 대안의 수에서 combinatorial explosion을 일으키지 않고, constraint solver에서 AND/OR 노드를 reified constraint로 변환하고 싶다. Control.MonadPlus.Free에서

은 Plus ms >>= ff은 ms 각 모나드하에 Pure 잎의 각각에인가되게한다. 이는 f이 대체하는 각 Pure 리프에 대해 다른 값을 생성 할 수 있기 때문에 필요합니다.

그러나 Plus ms >> g에, g 그래서 Plus에 그것을 배포하는 것은 불필요한 것, ms의 잎의 영향을받지 않을 수 있습니다. 에 의해,이어서 여기

data Free f a = Pure a 
       | Free (f (Free f a)) 
       | Then [Free f()] (Free f a) 
       | Plus [Free f a] 

새로운 Then 생성자 값이 우리가 무시 모나드의 시퀀스를 원하는 분야

시행 착오를 통해 I는 I 새로운 Then 생성자로 Control.MonadPlus.Free 모나드을 연장 할 수 있음을 발견 실제 값을 산출하는 최종 모나드.

instance Functor f => Monad (Free f) where 
    return = Pure 

    Pure a >>= f = f a 
    Free fa >>= f = Free $ fmap (>>= f) fa 
    Then ms m >>= f = Then ms $ m >>= f 
    Plus ms >>= f = Plus $ map (>>= f) ms 

    Pure a >> mb = mb 
    Then ms ma >> mb = Then (ms ++ [ma >>= (const $ return())]) mb 
    ma >> mb = Then [] ma >> mb 

>> 연산자 "캡"Pure()와 Pure a을 교체하여 기존의 잎, 목록에 덮인 모나드를 추가하고, 새와 값 모나드를 대체처럼 새로운 Monad 예를 보인다. 나는 새로운 모나드에 ++을 추가하는 것이 비효율적이라는 것을 잘 알고 있지만, fmap (그리고 모든 것은 연속을 사용하여 다시 쓸 수있다)으로 체인의 끝에 새로운 모나드를 바느질하는 것은 >>=만큼 나쁘다.

이렇게하는 것이 합당한 것 같습니다. 이것이 모나드 법을 위반합니까 (중요합니까?) 또는 기존 Control.Monad.Free을 사용하는 더 좋은 방법이 있습니까?

Answer 1

내 operational 패키지를보고 싶을 수도 있습니다. 무료 패키지는 다른 모나드 패키지와 다릅니다.

특히 BreadthFirstParsing.hs 예제를 살펴보십시오. mplus 기능이있어서 >>=은 이 아니고은 자동으로 배포됩니다. 이를 통해 퍼서 결합기를 광범위하게 구현할 수 있습니다. Control.Monad.Free로 번역

는

, 요점은 다음 펑

data F b = MZero | MPlus b b 

를 사용하는 경우 Free F 자동 mplus 이상 >>=를 배포하는 것입니다. 당신은 당신이 자동으로 >>=를 배포하지 않는 MPlus에 대한 의미를 구현하려면, 대신 펑에게

data F b = MZero | forall a. MPlus (Free f a) (Free f a) (a -> b) 

을 사용해야합니다.(이것이 내가 무료 라이브러리보다 운영 라이브러리를 선호하는 주된 이유입니다.)