2

我必须在 Haskell 中编写一个程序来解决一些不确定的问题。我想我理解 List Monad 75% 所以这是一个不经意的选择，但是......

（我的问题是用船和水填充 nxm 板，我得到了行和列的总和，船的每个部分都有它的价值，现在它并不重要）。

我想尽早保护以使算法有效问题是插入船的可能性取决于我给定的/我在以前的动作中插入的让我们称之为板状态，我不知道如何通过它因为我不能单独从板上生成新状态）

我的算法是： 1. 初始化第一块板 2. 生成第一行尝试应用所有可能的插入（我可以垂直插入羊，所以我需要记住将羊的其他部分插入较低的行） 3. 解决较小板的问题（ofc生成每 2 行后，我检查是否一切正常）

但是我不知道如何传递新状态，因为据我了解 State Monad 它仅从旧状态生成新状态，这对我来说是不可能的，我想在对值进行操作时生成新状态） .

我对我对 Haskell 的仇恨感到抱歉，但是在用命令式语言编程几年后，被迫与那些 Monads 做一些我可以用其他语言编写的事情几乎立即让我发疯。（Haskell 中的其他东西对我来说很好，其中一些实际上非常好）。

4

1 回答 1

9

结合StateTlist monad 来获得你想要的行为。

这是一个使用列表 monad 的非确定性的简单示例，同时仍保留先前所做选择的历史记录：

import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

fill :: StateT [Int] [] [Int]
fill = do
    history <- get
    if (length history == 3)
        then return history
        else do
            choice  <- lift [0, 1, 2]
            guard (choice `notElem` history)
            put (choice:history)
            fill

fill为它尝试的每条路径维护一个单独的历史记录。如果它填满了棋盘，它会成功返回，但如果当前选择与先前的选择重叠，它会放弃该解决方案并尝试不同的路径。

您使用 运行它evalStateT，并提供一个初始的空历史记录：

>>> evalStateT fill []
[[2,1,0],[1,2,0],[2,0,1],[0,2,1],[1,0,2],[0,1,2]]

它返回所有可能解决方案的列表。在这种情况下，这恰好是我们可以填满棋盘的所有排列的列表。

于 2013-06-23T02:13:19.903 回答