如何正确求解 haskell 中的帕斯卡三角形？

Question

我正在 Haskell 中实现 Pascal Triangle，但代码运行不正确。该代码再提供 1 行。我也试图像树一样打印结果，但这对我来说很困难和困惑，所以我没有添加打印代码。

这些是我得到的结果：

*Main> pascal 1
[[1],[1,1]]
*Main> pascal 2
[[1],[1,1],[1,2,1]]

预期输出：

*Main> pascal 2
    [[1],[1,1]]

理想输出：

*Main> pascal 3
           
         1  
        1 1 
       1 2 1

这是代码：

choose n 0 = 1
choose 0 k = 0
choose n k = choose (n-1) (k-1)* n `div` k

pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal m = pascal (m - 1) ++ [[choose m k | k <- [0,1..m]]]

Answer 1

首先请注意，您的方法有点落后。 Pascal 三角形的全部要点在于它提供了一种有效的方法来将 choose 函数制成表格 而无需 独立计算每个值。这并不意味着您的做法错误，但肯定不是很好。不要尝试在没有 choose 函数的情况下解决问题！你知道，

                 1
                ╱ ╲
               1   1
              ╱ ╲+╱ ╲
             1   2   1
            ╱ ╲+╱ ╲+╱ ╲
           1   3   3   1
          ╱ ╲+╱ ╲+╱ ╲+╱ ╲
         1   4   6   4   1
        ...     ...     ...

提示：不要从编写计算整个三角形或单个元素的函数开始，而是编写一个获取三角形的行并给出下一行的函数.那么剩下要做的就是iterate调用该函数。

至于如何在您当前的方法中修复它——好吧，很明显，如果您希望 pascal 1 产生 [[1]]，那么 pascal 0 = [[1]] 就不是一个非常明智的基本情况。相反，从开始

pascal 1 = [[1]]

或

pascal 0 = []

（更好一点，因为函数不会为零未定义......但仍然是负数 - 我们希望避免这种情况或至少为这种情况提供明确的错误消息。）

然后，对于第 m 行，您应该只计算 choose (m-1) k 系列。易于修复。请记住还要为 k.

选择正确的范围

至于如何pretty-print输出一个漂亮的等腰形状：写一个辅助函数

centerAlign :: [String] -> [String]

它在每行前面添加了空格，相当于它在 length compared to the maximum-length 中缺少的一半。

然后你可以简单地对帕斯卡三角形做putStrLn . unlines . centerAlign . map show。

Answer 2

这是获得“理想输出”的代码：

printPascal :: [[Integer]] -> IO ()
printPascal pasc = 
  let                      
     process row = 
      let 
       striped = (foldr1 (\ x y -> x ++ " " ++ y) . map show) row
       spaces = replicate ((n - length striped) `div` 2) ' '
      in spaces ++ striped ++ "\n"
                   
     n = length . (foldr1 (\ x y -> x ++ " " ++ y) . map show) . last $ pasc
  in mapM_ (putStr . process) pasc

首先，这里有一些示例（说实话，后一个看起来不太好 - 请参阅编辑以获得更好的版本）：

GHCi> printPascal (pascal 1)
1
GHCi> printPascal (pascal 4)
   1   
  1 1  
 1 2 1 
1 3 3 1  
GHCi> printPascal (pascal 8)
         1         
        1 1        
       1 2 1       
      1 3 3 1      
     1 4 6 4 1     
   1 5 10 10 5 1   
 1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1

那么，这里发生了什么：

我们取一个已经构建好的三角形 pasc。我们把最后一行变成一个字符串，将所有元素放在一个字符串中，用空格分隔。这是我们最终三角形中每一行的长度。
我们获取每一行并使用 process 对其进行处理。它做了一件简单的事情：它将所有元素放在一个字符串中，用空格分隔。如果它的长度小于 n，它会添加缺失的空格（右边和左边的空格数量相等；事实上，右边的空格可能会被删除，因为它已经完成了）。最后我们换行。
我们将 putStr . process 映射到列表上，然后对效果进行排序。 mapM（或其更通用的版本 - traverse）用于此类目的。结果类型将是 IO [()] - 我们不需要单位列表，因此我们通过将 mapM 替换为 mapM_ （或其更通用的版本 - traverse_).

您可能希望结合使用 pascal 和 printPascal：

buildAndPrintPascal :: Integer -> IO ()
buildAndPrintPascal = printPascal . pascal

编辑： 为了使树对于更大的数字看起来更好一些，我们可能想要更改步骤（保持奇数）。这是代码的编辑版本，唯一的编辑是 step:

printPascal :: [[Integer]] -> IO ()
printPascal pasc = 
  let                      
     process row = 
      let 
       striped = (foldr1 (\ x y -> x ++ step ++ y) . map show) row
       spaces = replicate ((n - length striped) `div` 2) ' '
      in spaces ++ striped ++ "\n"
                   
     n = length . (foldr1 (\ x y -> x ++ step ++ y) . map show) . last $ pasc
     step = 
       let 
        times = (floor . logBase 10 . fromInteger . maximum . last $ pasc) * 2 + 1
       in replicate times ' '
  in mapM_ (putStr . process) pasc

以下是一些示例：

GHCi> buildAndPrintPascal 4
   1   
  1 1  
 1 2 1 
1 3 3 1
GHCi> buildAndPrintPascal 8
                1                
              1   1              
            1   2   1            
          1   3   3   1          
        1   4   6   4   1        
     1   5   10   10   5   1     
  1   6   15   20   15   6   1  
1   7   21   35   35   21   7   1
GHCi> buildAndPrintPascal 10
                               1                               
                            1     1                            
                         1     2     1                         
                      1     3     3     1                      
                   1     4     6     4     1                   
               1     5     10     10     5     1               
           1     6     15     20     15     6     1           
        1     7     21     35     35     21     7     1        
    1     8     28     56     70     56     28     8     1    
1     9     36     84     126     126     84     36     9     1

我觉得他们看起来更好看。

如何正确求解 haskell 中的帕斯卡三角形？

How to solve correctly pascal triangle in haskell?

haskell

recursion

pascals-triangle