使用列表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实现每位数计数器

回答

相关问题