使用列表monad實現每位數計數器

因此，我在看問題here，併爲此問題構建了一個相當難看的解決方案。在嘗試清理它時，我開始調查列表解析和列表monad。我決定要使用list monad實現一個按位數的計數器。鑑於數字的輸入序列，[1, 2]，我想產生看起來是這樣的輸出序列：使用列表monad實現每位數計數器

[ [ 0, 0], 
    [ 0, 1 ], 
    [ 0, 2 ], 
    [ 1, 0 ], 
    [ 1, 1 ], 
    [ 1, 2 ] ]

也就是說，我會遍歷所有元素的所有可能的值，在該範圍內的清單。

的haskell.org list monad documentation說：

結合的函數被施加到輸入列表中的所有可能值和所得到的列表被級聯以產生所有可能的結果的列表。

太棒了！看上去很完美......這是我寫的生產解決方案的代碼：

count :: [Integer] -> [[Integer]] 
count [] = [] 
count (x:xs) = 
    -- get all possible sequences for the remaining digits 
    let 
    remDigits :: [[Integer]] 
    remDigits = count xs 
    in 
    -- pull out a possible sequence for the remaining digits 
    do nextDigits <- remDigits 
    -- pull out all possible values for the current digit 
    y <- [0..x] 
    -- record that "current digit" : "remaining digits" is 
    -- a valid output. 
    return (y:nextDigits)

但調用count與任何產生空列表，我不知道爲什麼。我錯過了什麼？

來源

2009-12-06 Aidan Cully

如果您只是將您的基本情況更改爲'count [] = [[]]'，則此代碼有效。 – ephemient 2009-12-06 19:17:32

實際上，這正是我所尋找的答案......我發現我的問題是，在基本情況下，單子列表中沒有解決方案，所以沒有任何可以解決的問題。 CBFraser的回答如下，但你的解決方案更接近我原先的想法。 – 2009-12-06 20:02:25

首先，你需要一個單例列表的基本情況作爲參數。試試這個：

count :: [Integer] -> [[Integer]] 
count [] = [] 
count [n] = map (\x -> [x]) [0..n] 
count (x:xs) = 
    do y <- [0..x] 
     nextDigits <- count xs 
     return (y:nextDigits) 

main = do 
    print $ count [1] 
    print $ count [1,2]

來源

2009-12-06 18:27:13 CBFraser

產生與OP指定的結果不同的結果！ – Dario 2009-12-06 18:47:32

謝謝 - 你說得對。 – 2009-12-06 18:47:56

其餘的錯誤與我使用monads的順序有關。我應該在外面有y < - [0..x]，而nextDigits < - 在內部有xs。 – 2009-12-06 18:50:33

count = sequence . map (enumFromTo 0)

是的，它真的就這麼簡單。試試看吧:)

來源

2009-12-06 19:09:05 ephemient

+1，這是一個非常好的解決方案 – CBFraser 2009-12-06 19:20:05

+1是免費的，但沒有意義;） – Dario 2009-12-06 19:33:18

爲了完整起見，你也可以表達邏輯列表解析，這可能是使用一些簡單的功能列表單子的最佳方式：

count (x:xs) = [ (y:ys) | y <- [0..x], ys <- count xs ]

來源

2009-12-06 19:12:29 CBFraser

更短

count = mapM (enumFromTo 0)

來源

2009-12-07 02:39:35 newacct

D'oh，不知道我是如何錯過'sequence + map'到'mapM'的機械翻譯，但是+1 +對於明顯的改進：D – ephemient 2009-12-07 02:43:38

使用列表monad實現每位數計數器

回答

相關問題