0

好吧，我不知道如何在haskell中做到这一点。例如，我有这样的矩阵

[[1,2],[3,4]]

我想生成一个列表列表，其中包含该矩阵的每个元素的所有可能邻居。

预期结果是：

[[1,2],[1,3],[1,4],[2,1],[2,3],[2,4],[3,1],[3,2],[3,4],[4,1],[4,2],[4,3]]

我知道如何创建函数，该函数将使用每个单元格的邻居线创建列表列表：

pos how = [ (0+dx,0+dy) | dx <- [0..(how-2)], dy <- [0..how-1] ] :: [(Int,Int)]
neighbour (x,y) how = [ (x+dx,y+dy) | dy <- [-1..1], dx <- [-1..1],
                                      x+dx >= 0, y+dy >= 0, x+dx<=how-2, y+dy <= how-1,
                                      (x,y)/=(x+dx,y+dy) ] :: [(Int,Int)]
all_n how = [ p | x <- pos how, let p = neighbour x how ] :: [[(Int,Int)]]

但我无法将其更改为按我描述的那样工作。

4

2 回答 2

5

让我勾勒出一种与您建议的方法截然不同的方法。在谈论邻居时，我会说 e 的d邻居是元素e向d方向迈出的一步。因此，例如，在矩阵中，数字是数字的右邻居。我们需要使用一些库代码。[[1,2],[3,4]]21

import Data.List

我们将从最简单的事情开始：让我们只找到一维列表的右邻居。

rightList (x:y:rest) = (x,y) : rightList (y:rest)
rightList _ = []

我们可以通过不确定地选择矩阵的一行并找到该行中的所有右邻居来找到矩阵中的所有右邻居。

right m = m >>= rightList

我们可以使用任何寻找邻居的函数，并通过反转元组来创建寻找另一个方向的邻居的函数。例如，左邻居与右邻居相同，但元组元素交换了，所以：

swap (x,y) = (y,x)
co direction = map swap . direction
left = co right

下层邻居呢？实际上，下邻居只是转置矩阵中的右邻居：

down = right . transpose
up   = co down

下一个感兴趣的方向是右下邻。这个有点棘手；我们要做的是并行遍历两个列表，但偏移一个。

downRight (xs:ys:rest) = zip xs (drop 1 ys) ++ downRight (ys:rest)
downRight _            = []
upLeft = co downRight

有一个最终方向，即直立邻居；如果我们将矩阵颠倒过来，这些都是右下角的邻居。

upRight  = downRight . reverse
downLeft = co upRight

最后，要形成所有邻居，我们可以不确定地选择一个相邻方向，然后找到该方向上的所有邻居。

allDirections = [right, left, up, down,
                 downRight, upLeft, upRight, downLeft]
neighbors m = allDirections >>= ($m)

输出的顺序并不完全符合您指定的顺序，但我想这可能并不重要。

于 2012-06-29T21:01:58.717 回答
1

为了更正您现在的代码，我提供了几个问题，经过深思熟虑的答案可能会帮助您取得进步：

  • how-2是一件奇怪的事情。为什么2要减去正确的数字？
  • 的类型all_n很奇怪。为什么它是一个函数？（它的参数代表什么？）为什么它返回一个嵌套列表，而不是一个平面列表？
  • 您似乎只跟踪一个大小参数，但您的矩阵是二维矩阵。为什么会有这样的差异？（为什么你没有宽度和高度参数？）
  • 一旦你有了一个坐标，你知道如何从矩阵中获取那个位置的元素吗？（提示：有一个函数(!!) :: [a] -> Int -> [a]。）如果你有一个坐标列表，你知道如何对列表中的每个元素执行此操作吗？（提示：有一个函数map :: (a -> b) -> ([a] -> [b])。）

祝你好运！

于 2012-06-29T21:33:28.797 回答