How to solve correctly pascal triangle in haskell?

Question

I am implementing Pascal Triangle in Haskell, but the code is not working the right way. The code is giving 1 more row. Also I've trying to print the result like a tree but it's been difficult and confuse for me, so I did not add the printing code.

These are the results I get:

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

Expected output:

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

Ideal output:

*Main> pascal 3
           
         1  
        1 1 
       1 2 1

This is the code:

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]]]

So... is your expected output for `pascal 1` going to be `[[1]]`? If so, isn't this just a matter of having the wrong base case? — Carl, Aug 11 '20 at 05:54
@Carl It's an easy thing to test whether simply fixing the base case produces a function that matches the expected output given. Did you try that test? — Daniel Wagner, Aug 11 '20 at 05:56
I asked a question on memoization of pascals triangle in haskell, might give some inspiration perhaps https://stackoverflow.com/questions/11473130/memoization-pascals-triangle — Viktor Mellgren, Aug 11 '20 at 08:58
edits must not invalidate existing answers. I rolled it back to 1st version, with small edit to title. — Will Ness, Aug 12 '20 at 09:45
I guess, the post is left at what it is. I asked a [question on Meta](https://meta.stackexchange.com/questions/352989/edit-wars-with-new-users) about edit wars, inspired by this one. If the OP wants, I shall remove links to this SO post. — Zhiltsoff Igor, Aug 21 '20 at 09:11

leftaroundabout · Accepted Answer · 2020-08-11T09:33:08.700

First let me note that your approach is a bit backwards. The whole point of Pascal's triangle is that it offers an efficient way to tabulate the choose function without calculating each of the values independently. That doesn't mean your way of doing it is wrong, but it's certainly not very good. Do try to solve the problem without the choose function! You know,

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

Hint: don't start with writing a function that computes the entire triangle or individual elements, but rather one that takes one row of the triangle and gives you the next row. Then all that's left to do is iterateing that function.

As for how to fix it in your current approach – well, obviously if you want pascal 1 to yield [[1]] then pascal 0 = [[1]] can't be a very sensible base case. Rather, start with

pascal 1 = [[1]]

or

pascal 0 = []

(which is a little better because the function will not be undefined for zero... but still is for negative numbers – we like to avoid this or at least give a clear error message for such situations.)

Then, for the mth line, you should compute only the choose (m-1) k series. Easy to fix. Remember to also pick the correct range for k.

As for how to pretty-print the output in a nice isosceles shape: write a helper function

centerAlign :: [String] -> [String]

which adds whitespace in front of each line, corresponding to half of what it lacks in length compared to the maximum-length one.

Then you can simply do putStrLn . unlines . centerAlign . map show on the Pascal's triangles.

Zhiltsoff Igor · Answer 2 · 2020-08-13T11:43:30.110

Here is the code to get the "ideal output":

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

First of all, here are some samples (the latter one does not look great, truth be told - see Edit for a better version):

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

So, what is happening here:

We take an already built triangle pasc. We turn the last row into a string, putting all the elements in a string, separated by spaces. That's the length of each row in our final triangle.
We take each row and process it with process. It does a simple thing: it puts all the elements in a string, separated by spaces. If its length is less then n, it adds the missing spaces (equal amount on both right and left; in fact, the spaces on the right might be dropped, as it is done). At the end we put a new line.
We map putStr . process over the list and then sequence the effects. mapM (or its more general version - traverse) serves for such purposes. The resulting type would have been IO [()] - we do not need a list of units, so we make it IO () by replacing mapM with mapM_ (or its more general version - traverse_).

You might want to combine pascal and printPascal:

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

Edit: to make the tree look a bit nicer for bigger numbers we might want to change the step (keeping it odd). Here is the edited version of the code, the only edit is the 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

Here are some samples:

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

I reckon them to look a bit nicer.

How to solve correctly pascal triangle in haskell?

2 Answers2