haskell - 在haskell中实现程序for循环，跟踪多个变量

Question

我正在尝试进行一些 alpha-beta 修剪，here's an example of an algorithm当我思考如何解决这个问题时，我可以理解我想到的算法。

但是我必须用 Haskell 来写这个，并且正在努力将我的思维方式从过程 for 循环和变量等“转换”为 Haskell 的函数方法。

让我很困惑的部分是如何写这样的东西

function alphabeta(node, α, β, player) is
    .
    .
    value := −∞
    for each child of node do
        value := max(value, alphabeta(child, α, β, otherPlayer))
        α := max(α, value)
        if α ≥ β then
            break (* β cut-off *)
    return value
    .
    .

我意识到我可以有点用折叠来做for循环，例如

foldl (max ... alphabeta ...) -∞ (children node)

但是我发现当 α ≥ β 时我需要从循环中中断。

我想知道是否可以改用 scanl 和 dropWhile，也许类似

head $ dropWhile (<b) $ scanl (max ... alphabeta ...) -∞ (children node)

但是没有!看起来我应该将变化变量α与β进行比较。

for 循环不断变化并使用(在递归中)两个不同的变量，α 和 value，这就是让我失望的原因，我不知道如何“跟踪”两个相互影响的不同变量(就像我尝试单变量循环时找出递归解决方案变得很困难，至少对我来说)。

我只是想知道我能做些什么来更好地理解如何解决这个问题。

Answer 1

“循环”最基本的形式是递归。事实上，fold 是通过底层的递归实现的，虽然 fold 使其更易于管理且更不易出错，但您始终可以下降到最基本的级别，如果您不知道如何使用折叠。

经验法则是这样的:每次“进入下一次迭代”时，递归地调用该函数，并且从一次迭代到另一次迭代的所有状态都将成为函数参数。当您想从循环中“中断”时，只需不要递归地调用该函数即可。

话虽如此，您的算法将如下所示:

alphabeta node initialAlpha beta player =
    ...
    let value = loop minBound initialAlpha (childrenOf node)
    in
    ...
    where
    loop value alpha [] = value 
    loop value alpha (child:restOfChildren) =
        let newValue = max value (alphabeta child alpha beta otherPlayer)
            newAlpha = max alpha value
        in
            if newAlpha >= beta 
                then newValue 
                else loop newValue newAlpha restOfChildren

在入口点，我调用 loop 将其 minBound 作为 value 传递，并将 node 的所有子节点作为一个列表。

然后循环本身会匹配它所传递的子级列表:如果列表为空，则循环的结果是value；如果子级列表不为空，loop 对第一个子级执行计算，然后递归调用自身，将 value 和 的新值传递给下一次迭代alpha，以及其余的 child ；除非 newAlpha >= beta，在这种情况下，loop 的结果是当前(刚刚计算的)值。