StateT와 non-determinism 모나드 : 간단한 예제

Question

StateT와 비 결정론 모나드로 작업하는 법을 배우는 중 일부를 사용하여 정수의 파티션을 열거하기 위해 이들을 사용하는 함수를 작성하고 싶습니다. 정수를 재사용). 예를 들어, 4의 인수를 전달하면 [[1,1,1,1],[1,1,2],[2,2],[1,3],[4]]이됩니다 (고유성은 중요하지 않습니다. 작업 코드로 들어가는 것이 더 중요합니다).

(또한 동적 프로그래밍과 파티션 계산을위한 함수 기반 솔루션 생성을위한 재귀 적 솔루션이 있다는 것을 알고 있습니다.이 연습의 목적은 StateT와 [ .])

여기 5보다 작거나 같은 모든 입력에서 작동하도록 설계되었다 내 시도입니다 :

{-# LANGUAGE NoImplicitPrelude #-} 
{-# OPTIONS_GHC -Wall #-} 

import CorePrelude 
import Control.Monad.State.Lazy 

sumState :: StateT Int [] [Int] 
sumState = do 
    m <- lift [1..5] 
    n <- get <* modify (-m+) 
    case compare n 0 of 
    LT -> mzero 
    EQ -> return [m] 
    GT -> fmap (n:) sumState 

runner :: Int -> [([Int],Int)] 
runner = runStateT sumState 

내가 디버깅에 도움이 runStateT 오히려 evalStateT보다 사용하고는 (그것을 참조하는 것이 도움이 최종 상태 값). 앞서 말했듯이이 두 모나드를 함께 사용하는 올바른 방법을 먼저 이해하고 싶기 때문에 고유 한 파티션을 생성하는 것에 대해 너무 걱정하지 않습니다.

GHCi에로드하고 runner 4 결과를 평가하면 위의 코드가이 출력을 생성하는 이유에 대해 혼란 스럽습니다.

[([4,3,2,1,1],-1),([4,3,2,1,2],-2),([4,3,2,1,3],-3),([4,3,2,1,4],-4),([4,3,2,1,5],-5),([4,3,2,1],-1),([4,3,2,2],-2),([4,3,2,3],-3),([4,3,2,4],-4),([4,3,2,5],-5),([4,3,1,1],-1),([4,3,1,2],-2),([4,3,1,3],-3),([4,3,1,4],-4),([4,3,1,5],-5),([4,3,1],-1),([4,3,2],-2),([4,3,3],-3),([4,3,4],-4),([4,3,5],-5),([4,2,1,1],-1),([4,2,1,2],-2),([4,2,1,3],-3),([4,2,1,4],-4),([4,2,1,5],-5),([4,2,1],-1),([4,2,2],-2),([4,2,3],-3),([4,2,4],-4),([4,2,5],-5),([4,1,1],-1),([4,1,2],-2),([4,1,3],-3),([4,1,4],-4),([4,1,5],-5),([4,1],-1),([4,2],-2),([4,3],-3),([4,4],-4),([4,5],-5)] 

내가 뭘 잘못하고 있니? 파티션을 열거하기 위해 StateT와 []를 결합하는 올바른 방법은 무엇입니까?

Answer 1

두 가지 작은 실수가 있습니다. 첫 번째는 여기에 있습니다 : 우리가 m을 빼기 전에

n <- get <* modify (-m+) 

이것은 n의 값을 가져옵니다. 맞춤법 것을 선호하는 경우는 거의 확실

n <- modify (-m+) >> get 

대신

, 또는

modify (-m+) 
n <- get 

를 원한다.

GT -> fmap (n:) sumState 

변경이

GT -> fmap (m:) sumState 

에 당신이 황금 위치 : 다른 하나는 당신이 GT 지점에 추가하고 값 대신 목록에 현재 상태를 가하고있는 것입니다 :

*Main> runner 4 
[([1,1,1,1],0),([1,1,2],0),([1,2,1],0),([1,3],0),([2,1,1],0),([2,2],0),([3,1],0),([4],0)]