3

作为学习如何使用 StateT 和 nondeterminism monad 的一部分，我想编写一个函数，使用它们来枚举整数的分区（同时允许重用整数）。例如，传递一个参数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帮助调试（查看最终状态值很有帮助）。就像我说的，我不太担心生成唯一分区，因为我首先想了解一起使用这两个 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 和 [] 以枚举分区的正确方法是什么？

4

1 回答 1

3

你只有两个小错误。第一个在这里：

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-19T19:42:55.807 回答