Haskell算法/Candy粉碎可能的动作

Question

我是一名本科编程学生，我正在尝试创建一个类似于“糖果迷”的程序。我试图在这里翻译这段代码，以便了解如何搜索可能的移动。下面是Haskell中的一段代码(不完全确定)

possibleMoves gf = filter works $ filter valid $ allMoves
where allMoves           = concat [ [((i,j),(i+1,j)), ((i,j),(i,j+1))] | (i,j) <- range ((0,0),(9,9)) ]
      valid (_,(i,j))    = i < 10 && j < 10 -- first coordinate is always correct
      works move@(i1,i2) = let gf' = flipStones gf move
                           in  lookAround i1 gf' || lookAround i2 gf'

lookAround (i,j) gf' = any ((>=3).length) $
    (groupBy combineable $ [ gf' ! (i',j) | i' <- range (max 0 (i-2), min 9 (i+2)) ]) ++
    (groupBy combineable $ [ gf' ! (i,j') | j' <- range (max 0 (j-2), min 9 (j+2)) ])

但是，不管我如何翻译它(显然我对Haskell一无所知)，这对我来说是毫无意义的。因为我找不到这些符号的含义，我不知道该怎么做。虽然我知道在这样的事情上寻求帮助有点蹩脚，但这是一个学校项目，我想我没有那么多的时间去学习Haskell的基础知识。有谁能帮我找出真相(关于这个函数做什么的想法/如何自己找到解决方案等等)？或者给我一些想法，让我自己创造一个新的好功能。

耽误您时间，实在对不起

(由OP编辑)

太谢谢你了！这两个答案都是非常详细和准确的，我正在尝试创建一个新的功能，根据所提供的数据，它似乎更容易做到这一点，现在完成这些帮助！

另外，克贝约翰，我会看看你提议的代码片段。非常感谢。

谢谢大家，谢谢！

Answer 1

我知道您不需要翻译，所以我在python中提供了一个大致相同的实现，使用python生成器和习惯用法，试图说明基于懒惰/流的结果生成的概念。

考虑到您正在尝试理解它是如何工作的，让我们单独查看每个部分。我已经列出了代码以使其更容易理解，并添加了类型签名，这样您就可以感觉到这些部分是如何组合在一起的。您可以查找为伟大的善学一只Haskell中使用的符号。

type Position = (Int, Int)
type Move = (Position, Position)

possibleMoves :: Position -> [Move]
possibleMoves gf = filter works $ filter valid $ allMoves
    where

        allMoves :: [Move]
        allMoves = concat [ [ ((i,j),(i+1,j))
                            , ((i,j),(i,j+1)) ]
                          | (i,j) <- range ((0,0),(9,9)) ]

        valid :: Move -> Bool
        valid (_,(i,j)) = i < 10 && j < 10

        works :: Move -> Bool
        works move@(i1,i2) = let gf' = flipStones gf move
                             in lookAround i1 gf' || lookAround i2 gf'

该函数首先使用列表理解生成所有可能的移动(绑定为allMoves)的列表。haskell中的语法与python的列表理解略有不同。由于haskell的惰性语义，这段代码最好被看作是返回所有可能的动作流的生成器。

def allMoves():
    for i in range(0,9):
        for j in range(0,9):
            yield ((i,j),(i+1,j))
            yield ((i,j),(i,j+1))

然后有一个函数valid，它检查移动是否合法，并根据答案返回True/False。

def valid(move):
    return move[1][0] < 10 && move[1][2] < 10

最后，一个函数works，它检查结果是否确实做了一些有用的事情。

def works(move):
    # flipStones returns a new game_field that incorporates the move we're testing
    new_gf = flipStones(game_field, move)
    return lookAround(move[0], new_gf) || lookaround(move[1], new_gf)

最后，这些函数都连接在一起，提供了最终的答案。乍一看，$符号可能令人困惑，但只要把它想象成管道操作符，从右到左排列值即可。它可以很容易地用括号代替。

possibleMoves gf = filter works $ filter valid $ allMoves
-- Is exactly equivalent to
possibleMoves gf = filter works ( filter valid ( allMoves ) )

where子句中的函数仅存在于possibleMoves的范围内。这很好地映射到python内部函数，如您在这里所看到的。

from itertools import ifilter

# possibleMoves takes
def possibleMoves(game_field):

    def allMoves():
        for i in range(0,9):
            for j in range(0,9):
                yeild ((i,j),(i+1,j))
                yield ((i,j),(i,j+1))

    def valid(move):
        return move[1][0] < 10 && move[1][3] < 10

    def works(move):
        # the gf in scope here is the gf passed to possibleMoves
        new_gf = flipStones(game_field, move)
        return lookAround(move[0], new_gf) && lookAround(move[1], new_gf)

    return ifilter(works, ifilter(valid, allMoves()))

接下来，我们来看看lookAround。

lookAround :: Position -> Position -> Bool
lookAround (i,j) gf' = any ((>=3).length) $
    (groupBy combineable $ [ gf' ! (i',j) | i' <- range (max 0 (i-2), min 9 (i+2)) ]) ++
    (groupBy combineable $ [ gf' ! (i,j') | j' <- range (max 0 (j-2), min 9 (j+2)) ])

这是一个函数，我只能假设它是搜索代码中相同的min/max值。函数定义的左边就像一个破坏性的赋值。(any和groupby是python的标准版本)

from itertools import groupby

def lookAround(pos1, pos2):
    i, j = pos1[0], pos1[1]
    # look around 2 above/below, grouping into runs of colors, returns list of lists
    list1 = groupby([pos2[(i_, j)] for i_ in range(max(0,i-2), min(9,i+2))])
    # look around 2 left right, grouping into runs of colors, returns list of lists
    list2 = groupby([pos2[(i, j_)] for j_ in range(max(0,j-2), min(9,j+2))])
    # return true if there's a run of 3 or more colours in either direction
    return any(lambda l: len(l)>=3, list1 + list2)

我希望这能帮你理解到底发生了什么。实现速度的关键是使用延迟生成的列表(python中的生成器)。这意味着，一旦知道一个结果是不需要的，或者会导致一个无效的答案，它就可以被丢弃。这样做的结果是，您只需要做实际需要的工作，缺点是在python中，您必须对生成器(也称为coroutines)和面向流的编程感到舒服。

祝你的作业顺利，我希望这能给你一些提高你的实现性能的想法。

Answer 2

顾名思义，allMoves是一个包含所有可能的移动的列表，不管用户是否允许它们。它是通过从所有可能的坐标对(range (0,0) (9,9))的列表开始并生成水平(((i,j),(i+1,j)))和垂直(((i,j),(i,j+1)))交换来生成的。

生成这些交换的循环是使用Haskell的列表理解语法实现的。这些交换以2的列表(水平和垂直从每个坐标产生)生成，然后使用concat组合成一个列表。(IMHO，这是糟糕的Haskell风格，比严格意义上更令人困惑:一旦他们开始使用列表理解，他们就不必使用concat来实现这一目的.)

从这个列表开始，他们两次使用标准函数filter来消除他们不想要的列表元素。filter的第一个参数是用于对元素排序的布尔函数，第二个参数是列表本身；它只返回函数返回True的元素的列表。

filter的第一次使用使用了函数valid，并消除了引用坐标范围以外的元素的移动。

filter的第二次使用使用了函数works，它似乎决定了移动是否导致匹配。值gf (它是对整个函数possibleMoves的输入)应该是一个竞争场，works函数首先从它计算一个修改后的竞技场gf' = flipstones gf move --将预期的移动应用到原始字段(函数flipstones应该是在程序的其他地方用户定义的)。表示法move@(i1,i2)将传入的移动绑定到move，同时也将元组的元素提取为i1和i2。

然后，函数works调用lookaround两次(对移动的每个元素调用一次)，以确定是否有any匹配其length为>=3。为此，lookaround再次使用列表理解，以选择有关传入坐标对的行和列元素。注意:在其他语言可能使用array[index]的地方，这里的索引操作是array ! index。

函数lookaround使用标准函数groupBy根据函数combineable将行(和列)分割成组(像flipstones一样，函数combineable似乎是在程序的其他地方定义的)。为了方便起见，它将这两个组列表连接起来(使用list-串联操作符++)，然后检查是否有任何组的长度为3或更长。

正如您自己可以猜测的那样，这段Haskell代码似乎并不是特别优化的，但它很简单:一旦您了解了代码的作用，很明显，它正确地返回了一个由所有可能的用户移动组成的列表，而不是其他的。