将递归case转换为Has时出现问题

Question

我有以下python代码：

def win(start, adjList):
  if len(adjList[start]) == 0: return True

  else:

    for vertex in adjList[startingPoint]:

      adjListCopy = copy.deepcopy(adjList)
      adjListCopy[start].remove(vertex)

      if (win(vertex, adjListCopy)): return False

  return True

这里adjList是一个字典，类似于{0: [1,2], 2: [3], 3: []}，start是一个要查看的索引，在本例中假设start是0。如果我们从0开始就能赢，它就会回来。你知道吗

在haskell中，我将字典表示为Map

以下是我目前的代码：

win adjList start =
    if (adjListAtstarting) == Just [] || (adjListAtstarting) == Nothing
        then True
    else
        False
        -- loop through each item in the map, and recurse

    where adjListAtstarting = Map.lookup start adjList

我需要帮助处理haskell的递归案例。我知道我可以使用Map.adjustWithKey函数执行adjListCopy[start].remove(vertex)。我遇到麻烦的主要原因是for循环。你知道吗

Answer 1

这应该起作用：

import qualified Data.Map as Map

win adjList start = not $ any f adjListAtstarting
    where adjListAtstarting = Map.findWithDefault [] start adjList
          f vertex = win (Map.adjust (filter (vertex /=)) start adjList) vertex

既然您希望处理Just []和Nothing相同，我使用了findWithDefault而不是lookup，所以您根本不必处理Maybe。正如AChampion指出的，您不需要if测试，因为如果列表为空，正确的事情就会自动发生。你知道吗

not $ any f adjListAtstarting在adjListAtstarting的每个元素上调用函数f，如果对f的所有调用都返回True，则返回True；如果对f的任何调用都返回True，则返回False。这与Python for循环相匹配，如果内部测试是True，则立即返回False；如果由于内部测试总是false而退出循环，则返回True。你知道吗

filter (vertex /=)获取一个列表，并返回一个包含除vertex之外的所有元素的列表。（注意：您在Python中使用了remove，它只从列表中删除元素的第一个匹配项。这将从列表中删除所有匹配的元素。如果列表永远不会包含同一元素的两个元素，那么就可以了。如果他们这样做了，那么您将需要使用the ^{} function (imported from ^{})）

Map.adjust (filter (vertex /=)) start adjList在adjList的start元素上调用filter (vertex /=)，并返回一个映射，其中该调用的结果是替换输入中的start元素，并且所有其他元素都相同。（您只需要adjust而不需要adjustWithKey，因为您对值所做的更改不依赖于键。）