测试嵌套列表中的对角相邻元素
Testing diagonally adjacent elements in nested lists
这是 recent question that wasn't asked clearly. The poster Aditi Jain's clarifications invalidate the answer 的后续内容，已经 post 在那里，因此这个新的 post.
objective是检查嵌套列表中是否没有对角相邻的元素对。 The poster 是 Haskell 编程的新手。
函数签名是：
checkNegation :: [[Int]] -> Bool
示例：
checkNegation [[1,2], [-2,3]] 将 return False:
[ [ 1 , 2], -- 2, -2 are diagonally adjacent
[-2 , 3] ]
checkNegation [[1,2], [3,-1]] 将 return False:
[ [ 1 , 2], -- 1, -1 are diagonally adjacent
[ 3 , -1] ]
checkNegation [[1,2], [-1,3]] 将 return True:
[ [ 1 , 2], -- no diagonally adjacent negatives
[-1 , 3] ]
checkNegation [[0,2,1], [3,1,-2], [3,-1,3]] 将 return False:
[ [ 0 , 2, 1], -- 2, -2 are diagonally adjacent
[ 3 , 1, -2],
[ 3 , -1, 3] ]
原始 post 中未提供编码尝试。
（我没有将此标记为 CW，以免阻止回答者因他们的努力而获得声誉点数）
我们可以使用 Data.Universe.Helpers 包中的 diagonals 实用程序。这样
λ> diagonals [[0,2,1], [3,1,-2], [3,-1,3]]
[[0],[3,2],[3,1,1],[-1,-2],[3]]
这只是我们需要的一半。因此，让我们翻转我们的 2D 列表并再次应用 diagonals。翻转列表需要 reverse . transpose 操作，这样
λ> (reverse . transpose) [[0,2,1], [3,1,-2], [3,-1,3]]
[[1,-2,3],[2,1,-1],[0,3,3]]
现在我们可以使用这个翻转列表上的对角线来获得剩余的对角线。
λ> (diagonals . reverse . transpose) [[0,2,1], [3,1,-2], [3,-1,3]]
[[1],[2,-2],[0,1,3],[3,-1],[3]]
对于所有对角线，我们需要将它们连接起来。所以我们可能会喜欢；
allDiags = (++) <$> diagonals . reverse . transpose <*> diagonals
剩下的就是应用必要的布尔测试。
import Data.List (transpose)
import Data.Universe.Helpers (diagonals)
checkNegation :: Num a => Eq a => [[a]] -> Bool
checkNegation = and . map (and . (zipWith (\x y -> 0 /= (x + y)) <*> tail)) . allDiags
where
allDiags = (++) <$> diagonals . reverse . transpose <*> diagonals
λ> checkNegation [[0,2,1], [3,1,-2], [3,-1,3]]
False
λ> checkNegation [[1,2], [-1,3]]
True
如果我们逐行取矩阵，做起来会容易一些。例如：
[a,b,c],
[d,e,f],
我们只想比较对：
[(a,e),(b,f),(b,d),(c,e)]
所以第一步是编写一个函数，从两个相邻的行构造该列表。
diags xs ys = zip xs (drop 1 ys) ++ zip (drop 1 xs) ys
我们使用drop 1而不是tail，因为它不会在空列表上出错，而我稍后要使用此函数的方式将使用空列表。
如果我们在折叠中使用它，那么，它看起来像下面这样：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p = fst . foldr f (False, [])
where
f xs (a, ys) = (a || or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys), xs)
我们还使它对任何关系都通用。
接下来我们想弄清楚如何检查两个数字是否互为负数。
negEachOther x y = negate x == y
然后我们的校验否定函数如下：
checkNegation = anyDiags negEachOther
这里我们可以使用 anyDiags 函数做一些有趣的事情。实际上其中隐藏了 writer monad 的用途。这样，我们可以重写折叠以使用该事实：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p = getAny . fst . foldrM f []
where
f xs ys = (Any (or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys)), xs)
虽然我不确定它是否更清楚。
或者，我们可以使用 zip xs (tail xs) 技巧完成所有操作：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p xs = or (zipWith f xs (tail xs))
where
f xs ys = or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys)
首先我们将行配对：首先与第二行配对，然后第二与第三行配对，然后第三与第四行配对，依此类推。
然后，对于每对行，我们考虑所有楔形单元格三元组，如下所示：
--*---
-*-*--
以便底行单元格与顶行单元格对角相邻。
然后我们只检查底部是否有顶部的负数。
除此之外（字面上）有一个边缘情况：行的开头和结尾。如果我们做这个楔形的三元组，我们将错过顶行的第一个和最后一个元素。为了解决这个问题，我们首先将整个矩阵包裹在 Just 中，然后在左右两侧用 Nothing 扩展每一行：
[a,b,c] ==> [Nothing, Just a, Just b, Just c, Nothing]
[d,e,f] ==> [Nothing, Just d, Just e, Just f, Nothing]
现在我们可以安全地迭代三元组而不会遗漏任何东西。
checkNegation :: [[Int]] -> Bool
checkNegation matrix = any rowPairHasNegation rowPairs
where
extendedMatrix = map extendRow matrix
extendRow row = [Nothing] ++ map Just row ++ [Nothing]
rowPairs = extendedMatrix `zip` drop 1 extendedMatrix
rowPairHasNegation (row, nextRow) =
any cellTripleHasNegation $
drop 1 row `zip` nextRow `zip` drop 2 nextRow
cellTripleHasNegation ((x1y0, x0y1), x2y1) =
isNegation x1y0 x0y1 || isNegation x1y0 x2y1
isNegation (Just a) (Just b) = a == -b
isNegation _ _ = False
据我所知，这将导致对整个矩阵进行三次迭代 - 一次是顶行，两次是底行，这意味着 O(n*m)
如果您有这样的矩阵并想比较相邻的对角线元素：
m = [[ 1, 2, 3, 4]
,[ 5, 6, 7, 8]
,[ 9,10,11,12]]
那你想做两个比较。首先，您要逐个元素地比较通过删除第一行和第一列（左）获得的子矩阵与通过删除最后一行和最后一列（右）获得的子矩阵：
[[ 6, 7, 8] [[ 1, 2, 3]
,[10,11,12] ,[ 5, 6, 7]]
其次，您要逐个元素地比较通过删除第一行和最后一列（左）获得的子矩阵与通过删除最后一行和第一列（右）获得的子矩阵):
[[ 5, 6, 7] [[ 2, 3, 4]
,[ 9,10,11]] ,[ 6, 7, 8]]
我们可以使用 init、tail 和 map 构造这些子矩阵：
m1 = tail (map tail m) -- drop first row and first column
m2 = init (map init m) -- drop last row and last column
m3 = tail (map init m) -- drop first row and last column
m4 = init (map tail m) -- drop last row and first column
给予：
λ> m1
[[6,7,8],[10,11,12]]
λ> m2
[[1,2,3],[5,6,7]]
λ> m3
[[5,6,7],[9,10,11]]
λ> m4
[[2,3,4],[6,7,8]]
我们如何比较两个子矩阵？好吧，我们可以编写 zipWith 的二维版本，将二元函数逐个元素应用于两个矩阵，同样的方式 zipWith 将二元函数逐个元素应用于两个列表：
zipZipWith :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]
zipZipWith f m1 m2 = zipWith zipRow m1 m2
where zipRow r1 r2 = zipWith f r1 r2
这是通过使用 zipRow 辅助函数逐行将矩阵压缩在一起来实现的。对于每一对行，zipRow 使用函数 f 逐个元素地将行压缩在一起。这个定义可以简化为稍微不太清楚：
zipZipWith f m1 m2 = zipWith (zipWith f) m1 m2
无论如何，要检查两个矩阵中对应的元素对是否互为负数，我们可以使用 zipZipWith isNeg 其中：
isNeg :: (Num a, Eq a) => a -> a -> Bool
isNeg x y = x == -y
然后，要检查这些对中的 任何 是否为负数，我们可以使用 concat 将布尔矩阵更改为长列表和 or 检查任何 True 值：
anyNegPairs :: (Num a, Eq a) => [[a]] -> [[a]] -> Bool
anyNegPairs ma mb = or . concat $ zipZipWith isNeg ma mb
最后，执行比较的完整函数将是：
noDiagNeg :: (Num a, Eq a) => [[a]] -> Bool
noDiagNeg m = not (anyNegPairs m1 m2 || anyNegPairs m3 m4)
由于 zipZipWith 与 zipWith 一样，在比较不同大小的参数时会忽略 "extra" 元素，实际上没有必要 trim 关闭最后一个 column/row，因此可以通过删除所有 inits:
来简化子矩阵定义
m1 = tail (map tail m)
m2 = m
m3 = tail m
m4 = map tail m
我们实际上可以根据 m4 来写 m1 以节省双重计算 map tail m:
m1 = tail m4
但编译器足够聪明，可以自行解决这个问题。
因此，合理的最终解决方案是：
noDiagNeg :: (Num a, Eq a) => [[a]] -> Bool
noDiagNeg m = not (anyNegPairs m1 m2 || anyNegPairs m3 m4)
where
m1 = tail (map tail m)
m2 = m
m3 = tail m
m4 = map tail m
anyNegPairs ma mb = or . concat $ zipZipWith isNeg ma mb
isNeg x y = x == -y
zipZipWith :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]
zipZipWith f m1 m2 = zipWith (zipWith f) m1 m2
它似乎在测试用例上按预期工作：
λ> noDiagNeg [[1,2],[-2,3]]
False
λ> noDiagNeg [[1,2],[3,-1]]
False
λ> noDiagNeg [[1,2],[-1,3]]
True
λ> noDiagNeg [[0,2,1],[3,1,-2],[3,-1,3]]
False
这与@oisdk 的解决方案非常相似，但如果您还不太熟悉折叠，这个版本可能更容易理解。
它在（某些）没有元素的矩阵上失败：
λ> noDiagNeg []
*** Exception: Prelude.tail: empty list
λ> noDiagNeg [[],[]]
*** Exception: Prelude.tail: empty list
所以如果这是一个问题，您可以使用@oisdk 将 tail 替换为 drop 1 的技术。 （实际上，我可能会将 tail' = drop 1 定义为助手，并将所有 tail 调用替换为 tail' 调用，因为那样看起来会好一点。）
这是 recent question that wasn't asked clearly. The poster Aditi Jain's clarifications invalidate the answer 的后续内容，已经 post 在那里，因此这个新的 post.
objective是检查嵌套列表中是否没有对角相邻的元素对。 The poster 是 Haskell 编程的新手。
函数签名是：
checkNegation :: [[Int]] -> Bool
示例：
checkNegation [[1,2], [-2,3]] 将 return False:
[ [ 1 , 2], -- 2, -2 are diagonally adjacent
[-2 , 3] ]
checkNegation [[1,2], [3,-1]] 将 return False:
[ [ 1 , 2], -- 1, -1 are diagonally adjacent
[ 3 , -1] ]
checkNegation [[1,2], [-1,3]] 将 return True:
[ [ 1 , 2], -- no diagonally adjacent negatives
[-1 , 3] ]
checkNegation [[0,2,1], [3,1,-2], [3,-1,3]] 将 return False:
[ [ 0 , 2, 1], -- 2, -2 are diagonally adjacent
[ 3 , 1, -2],
[ 3 , -1, 3] ]
原始 post 中未提供编码尝试。
（我没有将此标记为 CW，以免阻止回答者因他们的努力而获得声誉点数）
我们可以使用 Data.Universe.Helpers 包中的 diagonals 实用程序。这样
λ> diagonals [[0,2,1], [3,1,-2], [3,-1,3]]
[[0],[3,2],[3,1,1],[-1,-2],[3]]
这只是我们需要的一半。因此，让我们翻转我们的 2D 列表并再次应用 diagonals。翻转列表需要 reverse . transpose 操作，这样
λ> (reverse . transpose) [[0,2,1], [3,1,-2], [3,-1,3]]
[[1,-2,3],[2,1,-1],[0,3,3]]
现在我们可以使用这个翻转列表上的对角线来获得剩余的对角线。
λ> (diagonals . reverse . transpose) [[0,2,1], [3,1,-2], [3,-1,3]]
[[1],[2,-2],[0,1,3],[3,-1],[3]]
对于所有对角线，我们需要将它们连接起来。所以我们可能会喜欢；
allDiags = (++) <$> diagonals . reverse . transpose <*> diagonals
剩下的就是应用必要的布尔测试。
import Data.List (transpose)
import Data.Universe.Helpers (diagonals)
checkNegation :: Num a => Eq a => [[a]] -> Bool
checkNegation = and . map (and . (zipWith (\x y -> 0 /= (x + y)) <*> tail)) . allDiags
where
allDiags = (++) <$> diagonals . reverse . transpose <*> diagonals
λ> checkNegation [[0,2,1], [3,1,-2], [3,-1,3]]
False
λ> checkNegation [[1,2], [-1,3]]
True
如果我们逐行取矩阵，做起来会容易一些。例如：
[a,b,c],
[d,e,f],
我们只想比较对：
[(a,e),(b,f),(b,d),(c,e)]
所以第一步是编写一个函数，从两个相邻的行构造该列表。
diags xs ys = zip xs (drop 1 ys) ++ zip (drop 1 xs) ys
我们使用drop 1而不是tail，因为它不会在空列表上出错，而我稍后要使用此函数的方式将使用空列表。
如果我们在折叠中使用它，那么，它看起来像下面这样：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p = fst . foldr f (False, [])
where
f xs (a, ys) = (a || or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys), xs)
我们还使它对任何关系都通用。
接下来我们想弄清楚如何检查两个数字是否互为负数。
negEachOther x y = negate x == y
然后我们的校验否定函数如下：
checkNegation = anyDiags negEachOther
这里我们可以使用 anyDiags 函数做一些有趣的事情。实际上其中隐藏了 writer monad 的用途。这样，我们可以重写折叠以使用该事实：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p = getAny . fst . foldrM f []
where
f xs ys = (Any (or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys)), xs)
虽然我不确定它是否更清楚。
或者，我们可以使用 zip xs (tail xs) 技巧完成所有操作：
anyDiags :: (a -> a -> Bool) -> [[a]] -> Bool
anyDiags p xs = or (zipWith f xs (tail xs))
where
f xs ys = or (zipWith p xs (drop 1 ys)) || or (zipWith p (drop 1 xs) ys)
首先我们将行配对：首先与第二行配对，然后第二与第三行配对，然后第三与第四行配对，依此类推。
然后，对于每对行，我们考虑所有楔形单元格三元组，如下所示：
--*---
-*-*--
以便底行单元格与顶行单元格对角相邻。
然后我们只检查底部是否有顶部的负数。
除此之外（字面上）有一个边缘情况：行的开头和结尾。如果我们做这个楔形的三元组，我们将错过顶行的第一个和最后一个元素。为了解决这个问题，我们首先将整个矩阵包裹在 Just 中，然后在左右两侧用 Nothing 扩展每一行：
[a,b,c] ==> [Nothing, Just a, Just b, Just c, Nothing]
[d,e,f] ==> [Nothing, Just d, Just e, Just f, Nothing]
现在我们可以安全地迭代三元组而不会遗漏任何东西。
checkNegation :: [[Int]] -> Bool
checkNegation matrix = any rowPairHasNegation rowPairs
where
extendedMatrix = map extendRow matrix
extendRow row = [Nothing] ++ map Just row ++ [Nothing]
rowPairs = extendedMatrix `zip` drop 1 extendedMatrix
rowPairHasNegation (row, nextRow) =
any cellTripleHasNegation $
drop 1 row `zip` nextRow `zip` drop 2 nextRow
cellTripleHasNegation ((x1y0, x0y1), x2y1) =
isNegation x1y0 x0y1 || isNegation x1y0 x2y1
isNegation (Just a) (Just b) = a == -b
isNegation _ _ = False
据我所知，这将导致对整个矩阵进行三次迭代 - 一次是顶行，两次是底行，这意味着 O(n*m)
如果您有这样的矩阵并想比较相邻的对角线元素：
m = [[ 1, 2, 3, 4]
,[ 5, 6, 7, 8]
,[ 9,10,11,12]]
那你想做两个比较。首先，您要逐个元素地比较通过删除第一行和第一列（左）获得的子矩阵与通过删除最后一行和最后一列（右）获得的子矩阵：
[[ 6, 7, 8] [[ 1, 2, 3]
,[10,11,12] ,[ 5, 6, 7]]
其次，您要逐个元素地比较通过删除第一行和最后一列（左）获得的子矩阵与通过删除最后一行和第一列（右）获得的子矩阵):
[[ 5, 6, 7] [[ 2, 3, 4]
,[ 9,10,11]] ,[ 6, 7, 8]]
我们可以使用 init、tail 和 map 构造这些子矩阵：
m1 = tail (map tail m) -- drop first row and first column
m2 = init (map init m) -- drop last row and last column
m3 = tail (map init m) -- drop first row and last column
m4 = init (map tail m) -- drop last row and first column
给予：
λ> m1
[[6,7,8],[10,11,12]]
λ> m2
[[1,2,3],[5,6,7]]
λ> m3
[[5,6,7],[9,10,11]]
λ> m4
[[2,3,4],[6,7,8]]
我们如何比较两个子矩阵？好吧，我们可以编写 zipWith 的二维版本，将二元函数逐个元素应用于两个矩阵，同样的方式 zipWith 将二元函数逐个元素应用于两个列表：
zipZipWith :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]
zipZipWith f m1 m2 = zipWith zipRow m1 m2
where zipRow r1 r2 = zipWith f r1 r2
这是通过使用 zipRow 辅助函数逐行将矩阵压缩在一起来实现的。对于每一对行，zipRow 使用函数 f 逐个元素地将行压缩在一起。这个定义可以简化为稍微不太清楚：
zipZipWith f m1 m2 = zipWith (zipWith f) m1 m2
无论如何，要检查两个矩阵中对应的元素对是否互为负数，我们可以使用 zipZipWith isNeg 其中：
isNeg :: (Num a, Eq a) => a -> a -> Bool
isNeg x y = x == -y
然后，要检查这些对中的 任何 是否为负数，我们可以使用 concat 将布尔矩阵更改为长列表和 or 检查任何 True 值：
anyNegPairs :: (Num a, Eq a) => [[a]] -> [[a]] -> Bool
anyNegPairs ma mb = or . concat $ zipZipWith isNeg ma mb
最后，执行比较的完整函数将是：
noDiagNeg :: (Num a, Eq a) => [[a]] -> Bool
noDiagNeg m = not (anyNegPairs m1 m2 || anyNegPairs m3 m4)
由于 zipZipWith 与 zipWith 一样，在比较不同大小的参数时会忽略 "extra" 元素，实际上没有必要 trim 关闭最后一个 column/row，因此可以通过删除所有 inits:
m1 = tail (map tail m)
m2 = m
m3 = tail m
m4 = map tail m
我们实际上可以根据 m4 来写 m1 以节省双重计算 map tail m:
m1 = tail m4
但编译器足够聪明，可以自行解决这个问题。
因此，合理的最终解决方案是：
noDiagNeg :: (Num a, Eq a) => [[a]] -> Bool
noDiagNeg m = not (anyNegPairs m1 m2 || anyNegPairs m3 m4)
where
m1 = tail (map tail m)
m2 = m
m3 = tail m
m4 = map tail m
anyNegPairs ma mb = or . concat $ zipZipWith isNeg ma mb
isNeg x y = x == -y
zipZipWith :: (a -> b -> c) -> [[a]] -> [[b]] -> [[c]]
zipZipWith f m1 m2 = zipWith (zipWith f) m1 m2
它似乎在测试用例上按预期工作：
λ> noDiagNeg [[1,2],[-2,3]]
False
λ> noDiagNeg [[1,2],[3,-1]]
False
λ> noDiagNeg [[1,2],[-1,3]]
True
λ> noDiagNeg [[0,2,1],[3,1,-2],[3,-1,3]]
False
这与@oisdk 的解决方案非常相似，但如果您还不太熟悉折叠，这个版本可能更容易理解。
它在（某些）没有元素的矩阵上失败：
λ> noDiagNeg []
*** Exception: Prelude.tail: empty list
λ> noDiagNeg [[],[]]
*** Exception: Prelude.tail: empty list
所以如果这是一个问题，您可以使用@oisdk 将 tail 替换为 drop 1 的技术。 （实际上，我可能会将 tail' = drop 1 定义为助手，并将所有 tail 调用替换为 tail' 调用，因为那样看起来会好一点。）