If I have this constant pascal
defined as
pascal :: [[Int]]
pascal = iterate newrow [1]
where newrow = (zipWith (+) <*> tail) . ([0]++) . (++[0])
And I evaluate pascal !! 50 !! 50
in GHCI, how much of the triangle does this evaulate? Does that laziness mean only the necessary values (plus a bunch of thunks) get calculated?
Using the Pascal's triangle formula, we can describe this observation: C(n,k) = C(n-1,k-1) + C(n-1,k) . In particular, look at the second number from the left in each row. Each of those has a one to its upper left, and to its upper right is the row number of the previous row.
When expanding a bionomial equation, the coeffiecents can be found in Pascal's triangle. For example, if you are expanding (x+y)^8, you would look at the 8th row to know that these digits are the coeffiencts of your answer.
Yes, only the elements that are required to compute the element in question are evaluated.
GHCi offers the :sprint
and :print
debugging commands that can give you some information about what parts of a value have already been evaluated.
On this example:
GHCi> :sprint pascal
pascal = _
(That's because nothing has been evaluated at this point, and thunks are shown as _
.)
GHCi> pascal !! 5 !! 5
1
(I'm not using 50
because then this example would become too long.)
GHCi> :sprint pascal
pascal = [1] : [_,1] : [_,_,1] : [_,_,_,1] : [_,_,_,_,1] :
(_ : _ : _ : _ : _ : 1 : _) : _
Now you get a pretty clear idea what parts have been looked at.
Let's try one more:
GHCi> pascal !! 5 !! 4
5
GHCi> :sprint pascal
pascal = [1] : [1,1] : [_,2,1] : [_,_,3,1] : [_,_,_,4,1] :
(_ : _ : _ : _ : 5 : 1 : _) : _
And another one:
GHCi> pascal !! 10 !! 5
252
GHCi> :sprint pascal
pascal = [1] : [1,1] : [1,2,1] : [1,3,3,1] : [1,4,6,4,1] :
(1 : 5 : 10 : 10 : 5 : 1 : _) :
(_ : 6 : 15 : 20 : 15 : 6 : _) :
(_ : _ : 21 : 35 : 35 : 21 : _) :
(_ : _ : _ : 56 : 70 : 56 : _) :
(_ : _ : _ : _ : 126 : 126 : _) :
(_ : _ : _ : _ : _ : 252 : _) : _
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With