Haskell 算法/糖果传奇可能的移动

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的基础知识。有没有人能帮我弄明白（比如这个函数的作用/如何自己找到解决方案等）？或者给我一些建议，让我自己写一个新的好函数。

谢谢你们的时间。

---

（原作者编辑）

非常感谢！两个回答都非常详细和准确，我正在尝试基于提供的数据创建一个新函数，经过这些帮助后，这似乎变得容易多了！

另外，kobejohn，我会看看你提议的代码。非常感谢。

谢谢大家，真的非常感谢！

Answer 1

顾名思义，allMoves 是一个包含所有可能移动的列表，不管这些移动用户是否被允许。它是通过从所有可能的坐标对列表开始生成的，坐标范围是 range (0,0) (9,9)，然后生成水平的（((i,j),(i+1,j))）和垂直的（((i,j),(i,j+1))）移动。

生成这些移动的循环是用 Haskell 的 列表推导 语法实现的。这些移动以两个为一组生成（从每个坐标的水平和垂直方向），然后用 concat 把它们合并成一个列表。（在我看来，这种写法不太符合 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 两次（每个移动元素调用一次），来判断是否有 任何 匹配的元素，其 length 大于等于 3。为此，lookaround 再次使用列表推导，从传入的坐标对中选择行和列的元素。注意：在其他语言中可能会使用 array[index]，而这里的索引操作是 array ! index。

lookaround 函数使用标准函数 groupBy 将行（和列）根据 combineable 函数分成不同的组（像 flipstones 一样，combineable 函数似乎也是在程序的其他地方定义的）。为了方便，它将这两组列表合并在一起（使用列表合并操作符 ++），然后检查是否有任何组的长度大于等于 3。

---

正如你自己可以猜到的，这段 Haskell 代码似乎并没有特别优化，但它很简单：一旦你弄清楚代码的作用，就会发现它确实正确地返回了一个只包含所有可能用户移动的列表，而没有其他的。

Answer 2

我知道你不想要翻译，所以我用Python写了一个大致相同的实现，利用Python的生成器和一些常用的写法，来帮助你理解懒加载/流式结果生成的概念。

既然你想搞明白它是怎么工作的，我们就逐部分来看。我把代码整理得更清晰了一些，并加上了类型签名，这样你可以更好地理解各个部分是如何结合在一起的。你可以在Learn You A Haskell For Great Good上查找使用的符号。

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)) ])

这个函数我只能猜测是在寻找你代码中相同的最小/最大值。函数定义的左侧像是解构赋值。(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中，你需要对生成器（也称为协程）和流式编程感到熟悉。

祝你在作业中好运，希望这能给你一些提高实现性能的灵感。