时间戳

首页 > 解决方案 > 将递归大小写转换为 Haskell 时遇到问题

python - 将递归大小写转换为 Haskell 时遇到问题

问题描述

我有以下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是一个字典，like{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 递归案例的帮助。我知道我可以执行adjListCopy[start].remove(vertex)使用该Map.adjustWithKey功能。我遇到麻烦的主要原因是因为for循环。

标签： pythondictionaryhaskell

解决方案

这应该有效：

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 adjListAtstartingf对 的每个元素调用函数adjListAtstarting，True如果所有调用都返回则f返回False，但False如果有任何调用返回则f返回True。这与您的 Python for 循环相匹配，False如果内部测试是 ever 则立即返回，如果循环退出则True返回True，因为内部测试总是错误的。

filter (vertex /=)接受一个列表，并返回一个包含除 . 之外的所有元素的列表vertex。（注意：您remove在 Python 中使用，它只从列表中删除第一次出现的元素。这将从列表中删除所有匹配的元素。如果列表永远不会包含两个相同的元素，那么这很好。如果他们这样做了，那么您将需要使用该delete函数（从 导入Data.List）。）

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

推荐阅读