我目前正在研究项目欧拉问题（www.projecteuler.net），但它有点绊脚石。其中一个问题是提供20x20的数字网格，并要求直线上4个数字的最大乘积。该线可以是水平线，垂直线或对角线。
使用过程语言我没有解决这个问题，但我首先要做的就是获得更多经验并学习更多Haskell。
截至目前，我正在网格中读取并将其转换为整数列表列表，例如 - [[Int]]。这使得水平乘法变得微不足道，并且通过转置该网格，垂直也变得微不足道。
对角线是给我带来麻烦的。我想到了一些方法，我可以使用显式数组切片或索引，以获得一个解决方案，但它似乎过于复杂和hackey。我相信这里可能有一个优雅，实用的解决方案，我很想听听其他人能想到的。
我不同意可敬的唐斯图尔特。鉴于问题的组合性质以及问题大小仅为20x20的事实，列表列表将足够快。而且 持续 你想要的是使用数组索引来应对。相反，我建议你扩展理查德伯德在其着名的技术中开发的技术 数独求解器。更具体地说，我建议如下：
编写一个给定序列的函数，返回长度为4的所有连续子序列。
编写给定网格的函数，返回所有行。
编写一个给定网格的函数，返回所有列。
编写一个给定网格的函数，返回所有对角线。
有了这些功能，您的解决方案将变得简单。但正如你所提到的，对角线并不那么明显。无论如何，对角线是什么？ 我们来看一个例子：
X . . . . .
. X . . . .
. . X . . .
. . . X . .
. . . . X .
. . . . . X
假设您使用了 drop 函数，您从第0行删除0个元素，从第1行删除1个元素，依此类推。这就是你最喜欢的：
X . . . . .
X . . . .
X . . .
X . .
X .
X
对角线的元素现在形成了你留下的三角形的第一列。更好的是， 一切 你剩下的东西的列是原始矩阵的对角线。抛出一些对称变换，你就可以轻松地枚举了 所有 任意大小的方阵的对角线。用你的“长度为4的连续子序列”来解释每一个，鲍勃是你的叔叔！
对于那些可能被卡住的人来说更详细一点：
这个问题的关键是 组成。对角线分为四组。我的例子给出了一组。要获得其他三个，请将相同的功能应用于转置的镜像，转置和镜像。
Transpose是一个单行函数，无论如何你都需要它来干净地恢复列。
镜像比转置更简单 - 想想你可以在Prelude中使用哪些功能。
对称方法将给出每个主要对角线两次;幸运的是，问题表明重复对角线是可以的。
那么，对于这个特殊问题，单个线性列表或数组实际上是最简单的结构！关键是要考虑将这些运行视为以给定的步幅跳过列表。如果网格是 w ^ × H 那么大小
现在，对于四种运行中的每一种，您只需要计算可能的起点。像这样的东西：
allRuns :: Int -> Int -> Int -> [a] -> [[a]]
allRuns n w h es = horiz ++ vert ++ acute ++ grave
where horiz = runs [0..w-n] [0..h-1] 1
vert = runs [0..w-1] [0..h-n] w
acute = runs [n-1..w-1] [0..h-n] (w-1)
grave = runs [0..w-n] [0..h-n] (w+1)
runs xs ys s = [run (x+y*w) s | x <- xs, y <- ys]
run i s = map (es!!) [i,i+s..i+(n-1)*s]
当然，在一个有效的实现中，你将取代 [a] 有类似的东西 Data.Array Int a 和 es!! 同 es!
你可以使用 !! 用于按索引检索列表中的元素的函数。通过递增或递减索引的固定步骤可以获得对角线。
所以你有一个NxN网格，你想要提取长度为M的所有水平，垂直和对角线，然后找到最大的产品。让我们在示例4x4网格上说明一些Haskell技术，行长度为2：
[[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9,10,11,12],
[13,14,15,16]]
水平和垂直很容易，你只需要一个从列表中提取长度为M的块的函数：
chunks 2 [1,2,3,4] == [[1,2],[2,3],[3,4]]
这种功能的类型是 [a] -> [[a]]。这是一个与列表相关的功能，所以在重新发明轮子之前，让我们看看是否有相似之处 Data.List模块。啊哈， tails 类似的，它返回列表中包含越来越多元素的列表：
tails [1,2,3,4] == [[1,2,3,4],[2,3,4],[3,4],[4],[]]
如果我们只能缩短子列表以使它们长度为2.但我们可以通过使用 map function，它将函数应用于列表的每个元素并返回一个新列表：
map (take n) (tails xs) -- [[1,2],[2,3],[3,4],[4],[]]
我不担心较小的线条，因为最初的任务是找到最大的产品和产品 [15, N] ≥产品 [15]，N≥1。但是如果你想摆脱它们，似乎长度为N的列表包含长度为M的N-M + 1个块，所以你可以申请 take (4-2+1) 到结果列表。或者你可以简单地 过滤 列表：
chunks n xs = filter ((==n) . length) $ map (take n) (tails xs)
-- [[1,2],[2,3],[3,4]]
好的，我们可以从列表中提取一个块列表，但是我们有一个2D网格，而不是一个平面列表！ map 再次拯救我们：
map (chunks 2) grid -- [[[1,2],[2,3],[3,4]],[[5,6],[6,7],[7,8]],...]
但是这就是问题，结果代码将块放在单独的列表中，并且它使事情变得复杂，因为我们实际上并不关心，块从哪一行开始。因此，我们希望将结果列表的一个级别展平 concat . map或同等学历 concatMap：
concatMap (chunks 2) grid -- [[1,2],[2,3],[3,4],[5,6],[6,7],[7,8],...]
现在，我如何从网格中获取垂直块？听起来很可怕，直到你意识到你可以 颠倒 整个网格，即将行转换为列和列成行，然后应用相同的代码：
concatMap (chunks 2) (transpose grid) -- [[1,5],[5,9],[9,13],[2,6],[6,10],...]
现在困难的部分：对角线。 诺曼拉姆齐 给出一个想法：如果你可以从第0行丢弃0个元素，从第1行丢弃1个元素，等等？对角线将成为垂直线，易于提取。您还记得将函数应用于您使用的列表的每个元素 map，但在这里你需要对每个元素应用不同的函数，即 drop 0， drop 1， drop 2等 map 不合适。但是，看，第一个论点 drop 形成连续数字的模式，可以表示为无限列表 [0..]。现在如果我们可以从中获取一个元素 [0..] 我们需要的是一个从无限列表中获取数字的函数 [0..] 和网格中的一行，并适用 drop 用这个数字到行。 zipWith 是你需要的：
zipWith drop [0..] grid -- [[1,2,3,4],[6,7,8],[11,12],[16]]
map head $ zipWith drop [0..] grid -- [1,6,11,16]
但我想要所有长度为2的对角线，而不仅仅是最大的对角线。那么看看网格并思考，你看到第0行的元素有哪些对角线？ [1,6],[2,7],[3,8]。因此很明显，您只需要前两行并转置元素：
transpose $ zipWith drop [0,1] grid -- [[1,6],[2,7],[3,8],[4]]
现在我如何从其他行开始对角线？记住我们的 tails 招？我们可以通过提供我们的新功能来获得所有对角线 concatMap 并将其应用于 tails grid：
concatMap (transpose . zipWith drop [0,1]) (tails g)
-- [[1,6],[2,7],[3,8],[5,10],[6,11],...]
但这些只是从左上角到右下角的对角线。那些从右上到左下角的是什么？最简单的方法就是反转网格的行：
concatMap (transpose . zipWith drop [0,1]) (tails $ reverse g)
-- [[13,10],[14,11],[15,12],[9,6],[10,7],...]
最后，您需要找到所有行的产品并选择最大的产品。最终代码如下：
grid = [[1..4],[5..8],[9..12],[13..16]]
chunks n xs = map (take n) (tails xs)
horizontal = concatMap (chunks 2) grid
vertical = concatMap (chunks 2) (transpose grid)
grave = concatMap (transpose . zipWith drop [0,1]) (tails grid)
acute = concatMap (transpose . zipWith drop [0,1]) (tails $ reverse grid)
maxProduct = maximum $ map product $ horizontal ++ vertical ++ grave ++ acute
-- answer: 240
这段代码是否最优雅高效？没有，但它起作用并说明了函数式编程的某些思维模式。首先，你需要编写正常工作的代码，然后迭代重构它，直到你得到一个易于阅读和一般的解决方案。