我是一名本科编程专业的学生,我正在尝试创建一个类似于“糖果粉碎”的程序我试图在这里翻译这段代码,以便了解如何搜索可能的移动下面是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)) ])
但是,不管我怎么翻译它(显然我对哈斯克尔一无所知),这对我来说毫无意义因为我找不到那些符号的意思,我不知道怎么做虽然我知道在这些事情上寻求帮助有点蹩脚,但这是一个学校项目,我想我没有那么多时间来学习哈斯克尔的基础知识有谁能帮我找到真相(关于这个函数的作用/如何自己找到解决方案的想法等)?或者给我一些想法,让我自己做一个新的好功能。
谢谢你的时间
(由OP编辑)
太感谢你了这两个答案都非常详细和准确,我正在尝试创建一个新的功能,基于提供的数据,似乎很容易做到这一点后,现在这些帮助!
另外,kobejohn,我会看看你提议的代码块非常感谢。
谢谢大家谢谢!
最佳答案
我知道您不需要翻译,所以我在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子句中的函数仅存在于可能的范围内。这很好地映射到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中,您必须熟悉生成器(也称为协程)和面向流的编程。
祝你的任务顺利,我希望这能给你一些提高实现性能的想法。