Pascal's triangle in Haskell
I'm new to Haskell and I really need help!
I need to write a program that includes a recursive function to create a list of binomial coefficients for cardinality n = 12 using the Pascal triangle technique.
I have some ideas in my head, but since I am just getting started I have no idea how to implement this in haskell ?!
Can someone please help me?
first row: (a+b)^0 = 1
second row: (a+b)^1 = 1a+1b
third row: (a+b)^2 = 1a^2+2ab+1b^2
and so on ... that's my main idea. But I can't even try this because I have no idea how I put this in Haskell. All recording errors
source to share
Start by assigning an index to each element of the triangle:
| 0 1 2 3 4 5 6 - + -------------------------- 0 | 1 1 | eleven 2 | 1 2 1 3 | 1 3 3 1 4 | 1 4 6 4 1 5 | 1 5 10 10 5 1 6 | 1 6 15 20 15 6 1
Here I just put the triangle on my side so we can count them. So here I would say that the at element (6, 4)
is equal 15
when it (4, 6)
doesn't exist. Now focus on writing the function
pascal :: Integer -> Integer -> Integer
pascal x y = ???
So you can create this version of the triangle. You can start by writing
pascal x y
| x == 0 = 1
| x == y = 1
| x < y = error "Not a valid coordinate for Pascal triangle."
| otherwise = pascal ? ? + pascal ? ?
Note that here, instead of defining which elements should be joined by diagonals, you can do it via rectangular coordinates. Here you will notice that y
- this is which line in the triangle you are on and x
- this is the position of the element in that line. All you have to do is figure out what's going on instead of ?
s.
Once you get started, I have one liner for this triangle which is more efficient and can generate the entire triangle at the same time while still using recursion:
import Data.List (scanl1)
pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals
Don't try to turn this solution into your professor, that's not what they are looking for and it would be pretty obvious that someone gave you this solution if you've only been doing Haskell for a week. However, it really shows how powerful Haskell can be for this kind of problem. I would show you how to index pascals
to get a given value (n, k)
, but that would also give you too many hints for a naive recursion solution.
Since there has been some confusion, the reason I gave this solution is to draw a parallel between it and the often shown lazy implementation of the Fibonacci sequence:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Compared with
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
This definition generates an infinite list of all Fibonacci numbers and does it quite efficiently (from a CPU point of view, RAM is a different story). It encodes in its first two elements the base case and then a recursive expression that can evaluate the rest. For Fibonacci, you need 2 values to get you started, but for Pascal triangle, you only need one value, that value is just an infinite list. There is an easy way to see the pattern going through the columns in the grid posted above, the function scanl1 (+)
just uses this pattern and lets us generate it very easily, but this creates the diagonals of the triangle, not the rows. To get strings, you can index this list, or you can do some fancy tricks with take
,drop
and other similar functions, but this is an exercise for another day.
source to share
Start with the triangle itself:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
You should notice that to write the next line, you must apply this rule: sum the adjacent elements of the previous lines using 0
edges for single elements. Visually:
0 1 0
\+/ \+/
0 1 1 0
\+/ \+/ \+/
0 1 2 1 0
\+/ \+/ \+/ \+/
1 3 3 1
...
Promptly, it looks like this:
For row 0:
[1] (it a given; i.e. base case)
For row 1:
[0, 1] <- row 0 with a zero prepended ([0] ++ row 0)
+ +
[1, 0] <- row 0 with a zero appended (row 0 ++ [0])
= =
[1, 1] <- element-wise addition
For row 2:
[0, 1, 1]
+ + +
[1, 1, 0]
= = =
[1, 2, 1]
Generally, for row N:
element-wise addition of:
[0] ++ row(N-1)
row(N-1) ++ [0]
Remember that adding lists in Haskell increments amounts to zipWith (+)
.
Thus, we arrive at the following Haskell definition:
pascal 0 = [1]
pascal n = zipWith (+) ([0] ++ pascal (n-1)) (pascal (n-1) ++ [0])
Or in a fashion similar to the famous "lazy fibers":
pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals
source to share
Start with the base unit.
pascal 0 0 = 1
Then handle edge cases
pascal n 0 = 1
pascal n r | n == r = 1
Now expand it with a recursive step
pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r
If you need a list for a specific string, write a wrapper
binom n = map (pascal n) [0..n]
Figuring out types doesn't have to be difficult
pascal :: Integral a => a -> a -> a binom :: Integral a => a -> [a]
source to share
Another possible solution (more suitable for newbies in my opinion):
pascal :: Integer -> [Integer]
pascal 0 = [1]
pascal 1 = [1, 1]
pascal n = let p = pascal (n - 1)
in [1] ++ pascalStep p ++ [1]
pascalStep :: [Integer] -> [Integer]
pascalStep [] = []
pascalStep [_] = []
pascalStep (x:y:xs) = x + y : pascalStep (y : xs)
Use let
to avoid more use of space .
pascal
calls recursively to find all previous lines, using them to get the next line until the desired line is found.
Output:
*Main> pascal 3
[1,3,3,1]
*Main> pascal 4
[1,4,6,4,1]
*Main> pascal 5
[1,5,10,10,5,1]
source to share