Search code examples
haskellrecursionpascals-triangle

How to solve correctly pascal triangle in haskell?

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

  • 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.