haskell - 欧拉计划 8 - 我不明白

Question

我在 Haskell 中查找了第 8 个欧拉问题的解决方案，但我不太理解它。

import Data.List
import Data.Char

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails . map (fromIntegral . digitToInt)
         . concat . lines $ str

Here是解决方案的链接，here您可以找到该任务。

谁能给我一一解释一下解决方案吗？

Answer 1

读取数据

readFile读取文件"number.txt" 。如果我们将一个小的 16 位数字放入名为 number.txt 的文件中

7316
9698
8586
1254

运行

euler_8 = do
   str <- readFile "number.txt"
   print $ str

结果

"7316\n9698\n8586\n1254"

该字符串中有额外的换行符。为了删除它们，作者将字符串拆分为 lines .

euler_8 = do
   str <- readFile "number.txt"
   print . lines $ str

结果不再有任何'\n'字符，而是一个字符串列表。

["7316","9698","8586","1254"]

要将其转换为单个字符串，字符串为 concat一起享受。

euler_8 = do
   str <- readFile "number.txt"
   print . concat . lines $ str

连接的字符串是字符列表而不是数字列表

"7316969885861254"

每个字符都会转换为 Int通过digitToInt然后转换成Integer通过fromInteger 。在 32 位硬件上使用全尺寸 Integer很重要，因为 13 位数字的乘积可能大于 2^31-1 。这个转换是map ped 到列表中的每个项目。

euler_8 = do
   str <- readFile "number.txt"
   print . map (fromIntegral . digitToInt)
         . concat . lines $ str

结果列表充满 Integer s。

[7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4]

子序列

作者的下一个目标是找到此整数列表中的所有 13 位数字。 tails返回列表的所有子列表，从任意位置开始一直运行到列表末尾。

euler_8 = do
   str <- readFile "number.txt"
   print . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

对于我们的 16 位示例，这会产生 17 个列表。 (我已添加格式)

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
    [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
      [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
        [6,9,6,9,8,8,5,8,6,1,2,5,4],
          [9,6,9,8,8,5,8,6,1,2,5,4],
            [6,9,8,8,5,8,6,1,2,5,4],
              [9,8,8,5,8,6,1,2,5,4],
                [8,8,5,8,6,1,2,5,4],
                  [8,5,8,6,1,2,5,4],
                    [5,8,6,1,2,5,4],
                      [8,6,1,2,5,4],
                        [6,1,2,5,4],
                          [1,2,5,4],
                            [2,5,4],
                              [5,4],
                                [4],
                                 []
]

作者将使用一个技巧，我们重新排列这些列表以读取 13 位长的子列表。如果我们查看这些左对齐而不是右对齐的列表，我们可以看到每列都有子序列。

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4],
  [2,5,4],
  [5,4],
  [4],
  []
]

我们只希望这些列的长度为 13 位数字，因此我们只想 take第一个13行。

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [3,1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [1,6,9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,6,9,8,8,5,8,6,1,2,5,4],
  [9,6,9,8,8,5,8,6,1,2,5,4],
  [6,9,8,8,5,8,6,1,2,5,4],
  [9,8,8,5,8,6,1,2,5,4],
  [8,8,5,8,6,1,2,5,4],
  [8,5,8,6,1,2,5,4],
  [5,8,6,1,2,5,4],
  [8,6,1,2,5,4],
  [6,1,2,5,4],
  [1,2,5,4]
]

foldr (zipWith (:)) (repeat [])转置列表列表(解释它可能属于 another question )。它丢弃比最短行长的行部分。

euler_8 = do
   str <- readFile "number.txt"
   print . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

我们现在像往常一样读取列表中的子序列

[
  [7,3,1,6,9,6,9,8,8,5,8,6,1],
  [3,1,6,9,6,9,8,8,5,8,6,1,2],
  [1,6,9,6,9,8,8,5,8,6,1,2,5],
  [6,9,6,9,8,8,5,8,6,1,2,5,4]
]

问题

我们找到product每个子序列的map平 product到他们身上。

euler_8 = do
   str <- readFile "number.txt"
   print . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

这将列表减少到每个列表中的一个数字

[940584960,268738560,447897600,1791590400]

从中我们必须找到maximum .

euler_8 = do
   str <- readFile "number.txt"
   print . maximum . map product
         . foldr (zipWith (:)) (repeat [])
         . take 13 . tails
         . map (fromIntegral . digitToInt)
         . concat . lines $ str

答案是

1791590400