I'm new to Haskell and I really need some help!

I have to write a program that includes a recursive function to produce a list of binomial coefficients for the power n=12 using the Pascal's triangle technique.

I have some ideas in my head but because I'm just getting started I have no idea how to implement this to haskell?!

``````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...this is my main idea. But I cant even try this out because I have no idea how I put this in Haskell..getting errors all the time

• What have you tried? You should show some attempt to solve the problem yourself. – seong Dec 1 '14 at 16:54
• Try to be more specific. Honestly this sounds like a homework question where the point is to learn, not the actual implementation. What have you tried, and where did you get stuck - e.g. did you find the formula for Pascal's triangle and implement that? Do you understand the relationship between the triangle and the binomial coefficients? – lmm Dec 1 '14 at 16:55
• Yes I understand the relationship between the triangle and the binomial coefficients. It is in fact a homework question and I know what I theoretically need to do. But we just started Haskell 1 week ago, but I think that this question is too complicated for someone who never worked with haskell before, like me. So I know what to do, but I'm having trouble with the Haskell syntax. – Ceres Hilton Dec 1 '14 at 17:10

Start by assigning an index to each element in the triangle:

```  | 0   1   2   3   4   5   6
--+--------------------------
0 | 1
1 | 1   1
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've simply put the triangle on its side so that we can number them. So here I'd say that the element at `(6, 4)` is `15`, whereas `(4, 6)` doesn't exist. Now focus on writing a function

``````pascal :: Integer -> Integer -> Integer
pascal x y = ???
``````

Such that you can generate 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's triangle."
| otherwise = pascal ? ? + pascal ? ?
``````

Note that here, instead of figuring out which elements should be added together by diagonals, you can do it via rectangular coordinates. Here, you'll note that `y` is which row in the triangle you're on and `x` is the position of the element in that row. All you need to do is figure out what goes in place of the `?`s.

Once you get that working, I've got a one-liner for this triangle that is more efficient and can generate the entire triangle all at once while still using recursion:

``````import Data.List (scanl1)

pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals
``````

Don't try turning this solution in to your professor, it's not what they're looking for and it would make it pretty obvious 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 sort of problem. I would show how to index `pascals` to get a given `(n, k)` value, but doing so would also give you too many hints for solving the naive recursion.

Since there's been some confusion, the reason why I gave this solution is to draw a parallel between it and the often shown lazy implementation for the Fibonacci sequence:

``````fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
``````

Compared to

``````fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
``````

This definition generates an infinite list of all the Fibonacci numbers, and does so quite efficiently (from the point of view of the CPU, RAM is a different story). It encodes in its first 2 elements the base case, then a recursive expression that can calculate the rest. For the Fibonaccis, you need 2 values to start you off, but for Pascal's triangle, you only need one value, that value just happens to be an infinite list. There is an easy to see pattern going across the columns in the grid I posted above, the `scanl1 (+)` function just takes advantage of this pattern and allows us to generate it very easily, but this is generating the diagonals of the triangle rather than the rows. To get the rows, you can index this list, or you can do some fancy tricks with `take`, `drop`, and other such functions, but that's an exercise for another day.

• pascals function seems to yield an endless list of 1s. – nclark Aug 2 '16 at 23:20
• @nclark you have to take some from each sublist, so `map (take 10) pascals` will give you what you're looking for. Otherwise in ghci you're just going to set it try to compute the first element of pascals, which is supposed to be an infinite list of 1s. – bheklilr Aug 2 '16 at 23:25
• @bheklilr `map (take 10) pascals` will not yield the 10-th row. This code generates diagonals and indexing a n-th element will generate a offset infinite diagonal. – Szymon Bęczkowski Feb 23 '17 at 19:04

Start out 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 down the next row, you must apply this rule: sum the previous rows' adjacent elements, using a `0` for the lonely edge elements. Visually:

``````    0   1   0
\+/ \+/
0   1   1   0
\+/ \+/ \+/
0   1   2   1   0
\+/ \+/ \+/ \+/
1   3   3   1
...
``````

Operationally, that looks like this:

``````For row 0:
[1]  (it's 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])
=  =

For row 2:
[0, 1, 1]
+  +  +
[1, 1, 0]
=  =  =
[1, 2, 1]

Generally, for row N:

[0] ++ row(N-1)
row(N-1) ++ [0]
``````

Remember that element-wise addition of lists in Haskell is `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 fibs":

``````pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals
``````

``````pascal 0 0 = 1
``````

Then handle the edge cases

``````pascal n 0 = 1
pascal n r | n == r = 1
``````

Now expand with the recursive step

``````pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r
``````

If you want the list for a specific row, write a wrapper

``````binom n = map (pascal n) [0..n]
``````

Figuring out the types shouldn't be hard

``````pascal :: Integral a => a -> a -> a
binom :: Integral a => a -> [a]
``````
• Exponential time complexity. Not a good idea. – jubobs Dec 7 '14 at 10:54

Another possible solution (more suitable for beginners 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)
``````

Using `let` to avoid more space usage. `pascal` is calling recursively to find all previous rows, using them to get the next row, until getting to the desired row.

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]
``````
The provided text passage is a discussion on a programming forum where a user is seeking help with a Haskell assignment to generate a list of binomial coefficients for a given power using Pascal's triangle. The user describes their understanding of the problem and the challenges they face with Haskell syntax. Other users provide feedback, suggestions, and code snippets to help the user solve the problem.
no_question

the text does not contain a direct mathematical question or a calculation problem. instead, it is a discussion about a programming assignment, where the user is seeking help with implementing a recursive function in haskell to generate binomial coefficients using pascal's triangle. the focus is on the implementation details and the challenges faced by the user, rather than a specific mathematical question or calculation.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
I'm new to Haskell and I really need some help!

I have to write a program that includes a recursive function to produce a list of binomial coefficients for the power n=12 using the Pascal's triangle technique.

I have some ideas in my head but because I'm just getting started I have no idea how to implement this to haskell?!

``````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...this is my main idea. But I cant even try this out because I have no idea how I put this in Haskell..getting errors all the time

• What have you tried? You should show some attempt to solve the problem yourself. – seong Dec 1 '14 at 16:54
• Try to be more specific. Honestly this sounds like a homework question where the point is to learn, not the actual implementation. What have you tried, and where did you get stuck - e.g. did you find the formula for Pascal's triangle and implement that? Do you understand the relationship between the triangle and the binomial coefficients? – lmm Dec 1 '14 at 16:55
• Yes I understand the relationship between the triangle and the binomial coefficients. It is in fact a homework question and I know what I theoretically need to do. But we just started Haskell 1 week ago, but I think that this question is too complicated for someone who never worked with haskell before, like me. So I know what to do, but I'm having trouble with the Haskell syntax. – Ceres Hilton Dec 1 '14 at 17:10

Start by assigning an index to each element in the triangle:

```  | 0   1   2   3   4   5   6
--+--------------------------
0 | 1
1 | 1   1
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've simply put the triangle on its side so that we can number them. So here I'd say that the element at `(6, 4)` is `15`, whereas `(4, 6)` doesn't exist. Now focus on writing a function

``````pascal :: Integer -> Integer -> Integer
pascal x y = ???
``````

Such that you can generate 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's triangle."
| otherwise = pascal ? ? + pascal ? ?
``````

Note that here, instead of figuring out which elements should be added together by diagonals, you can do it via rectangular coordinates. Here, you'll note that `y` is which row in the triangle you're on and `x` is the position of the element in that row. All you need to do is figure out what goes in place of the `?`s.

Once you get that working, I've got a one-liner for this triangle that is more efficient and can generate the entire triangle all at once while still using recursion:

``````import Data.List (scanl1)

pascals :: [[Integer]]
pascals = repeat 1 : map (scanl1 (+)) pascals
``````

Don't try turning this solution in to your professor, it's not what they're looking for and it would make it pretty obvious 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 sort of problem. I would show how to index `pascals` to get a given `(n, k)` value, but doing so would also give you too many hints for solving the naive recursion.

Since there's been some confusion, the reason why I gave this solution is to draw a parallel between it and the often shown lazy implementation for the Fibonacci sequence:

``````fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
``````

Compared to

``````fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
``````

This definition generates an infinite list of all the Fibonacci numbers, and does so quite efficiently (from the point of view of the CPU, RAM is a different story). It encodes in its first 2 elements the base case, then a recursive expression that can calculate the rest. For the Fibonaccis, you need 2 values to start you off, but for Pascal's triangle, you only need one value, that value just happens to be an infinite list. There is an easy to see pattern going across the columns in the grid I posted above, the `scanl1 (+)` function just takes advantage of this pattern and allows us to generate it very easily, but this is generating the diagonals of the triangle rather than the rows. To get the rows, you can index this list, or you can do some fancy tricks with `take`, `drop`, and other such functions, but that's an exercise for another day.

• pascals function seems to yield an endless list of 1s. – nclark Aug 2 '16 at 23:20
• @nclark you have to take some from each sublist, so `map (take 10) pascals` will give you what you're looking for. Otherwise in ghci you're just going to set it try to compute the first element of pascals, which is supposed to be an infinite list of 1s. – bheklilr Aug 2 '16 at 23:25
• @bheklilr `map (take 10) pascals` will not yield the 10-th row. This code generates diagonals and indexing a n-th element will generate a offset infinite diagonal. – Szymon Bęczkowski Feb 23 '17 at 19:04

Start out 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 down the next row, you must apply this rule: sum the previous rows' adjacent elements, using a `0` for the lonely edge elements. Visually:

``````    0   1   0
\+/ \+/
0   1   1   0
\+/ \+/ \+/
0   1   2   1   0
\+/ \+/ \+/ \+/
1   3   3   1
...
``````

Operationally, that looks like this:

``````For row 0:
[1]  (it's 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])
=  =

For row 2:
[0, 1, 1]
+  +  +
[1, 1, 0]
=  =  =
[1, 2, 1]

Generally, for row N:

[0] ++ row(N-1)
row(N-1) ++ [0]
``````

Remember that element-wise addition of lists in Haskell is `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 fibs":

``````pascals = [1] : map (\xs -> zipWith (+) ([0] ++ xs) (xs ++ [0])) pascals
``````

``````pascal 0 0 = 1
``````

Then handle the edge cases

``````pascal n 0 = 1
pascal n r | n == r = 1
``````

Now expand with the recursive step

``````pascal n r = pascal (n - 1) (r - 1) + pascal (n - 1) r
``````

If you want the list for a specific row, write a wrapper

``````binom n = map (pascal n) [0..n]
``````

Figuring out the types shouldn't be hard

``````pascal :: Integral a => a -> a -> a
binom :: Integral a => a -> [a]
``````
• Exponential time complexity. Not a good idea. – jubobs Dec 7 '14 at 10:54

Another possible solution (more suitable for beginners 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)
``````

Using `let` to avoid more space usage. `pascal` is calling recursively to find all previous rows, using them to get the next row, until getting to the desired row.

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]
``````
user
The provided text passage is a discussion on a programming forum where a user is seeking help with a Haskell assignment to generate a list of binomial coefficients for a given power using Pascal's triangle. The user describes their understanding of the problem and the challenges they face with Haskell syntax. Other users provide feedback, suggestions, and code snippets to help the user solve the problem.

TYPE: NO_QUESTION

The text does not contain a direct mathematical question or a calculation problem. Instead, it is a discussion about a programming assignment, where the user is seeking help with implementing a recursive function in Haskell to generate binomial coefficients using Pascal's triangle. The focus is on the implementation details and the challenges faced by the user, rather than a specific mathematical question or calculation.