StateT和非確定性monad：一個簡單的例子

作爲學習如何使用StateT和非確定性monad的一部分，我想編寫一個函數，它使用這些枚舉整數的分區（雖然被允許重用整數）。例如，傳遞4的參數應該導致[[1,1,1,1],[1,1,2],[2,2],[1,3],[4]]（唯一性並不重要，我更關心的是隻能使用工作代碼）。（另外，我知道有一個遞歸解決方案用於生成分區以及動態編程和生成基於功能的分區計數的解決方案 - 此練習的目的是構建一個將StateT和[ ]）StateT和非確定性monad：一個簡單的例子

這裏是我的嘗試是被設計用來對任何輸入小於或等於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幫助調試（它有助於看看最終狀態值）。就像我說的，我並不擔心產生獨特的分區，因爲我首先想知道將這兩個monad一起使用的正確方法。

加載它在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和[]結合起來的正確方法是什麼？

來源

2014-12-19 iceman

我的頭腦被'（-m +）'吹了。甚至_do_做什麼？ – MathematicalOrchid

我不能說'（-m +）'實際上在做什麼，但我會解釋我的意圖:)假設我們傳遞一個4的參數（即'runner 4'到'GHCi'）。這個想法是，'修改'將會減少當前狀態（在第一遍中，是'4'），其中一個數字[1..5]表示爲m。然後我們測試新狀態是<0, > 0還是== 0。如果<0，我們丟棄該值;如果> 0，我們在該特定分支（通過'fmap（m：）'）並且沖洗/重複前置m到分區，如果== 0，我們簡單地終止分支（通過'return [m]'）我們已經達到了該分行的目標金額。 – iceman

@MathematicalOrchid當然，'（+）'是'-m'的部分應用。儘管傳統上拼寫爲'減去m'。 –

你只是有兩個小錯誤。第一個是在這裏：

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

這得到的n值我們減去m之前。幾乎可以確定你想要

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

代替，或

modify (-m+) 
n <- get

如果你喜歡的拼寫。另一種是，你把當前狀態的列表，而不是你在GT分支增加值：

GT -> fmap (n:) sumState

改變，要

GT -> fmap (m:) sumState

，你是金：

*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)]

來源

2014-12-19 19:42:55

賓果。（第二個是我自己愚蠢的錯誤......）謝謝！ – iceman

StateT和非確定性monad：一個簡單的例子

回答

相關問題