Represent sequence of tetrahedral numbers in Haskell

Question

I've been wanting to learn some Haskell for a while now, and I know it and similar languages have really good support for various kinds of infinite lists. So, how could I represent the sequence of tetrahedral numbers in Haskell, preferably with an explanation of what's going on?

0   0   0
1   1   1
2   3   4
3   6   10
4   10  20
5   15  35
6   21  56
7   28  84
8   36  120

In case it's not clear what's going on there, the second column is a running total of the first column, and the third column is a running total of the second column. I'd prefer that the Haskell code retain something of the "running total" approach, since that's the concept I was wondering how to express.

Answer 1

You're correct, Haskell is really nice for doing things like this:

first_col = [0..]
second_col = scanl1 (+) first_col
third_col = scanl1 (+) second_col

• first_col is an infinite list of integers, starting at 0
• scanl (+) calculates a lazy running sum: Prelude docs

We can verify that the above code is doing the right thing:

Prelude> take 10 first_col 
[0,1,2,3,4,5,6,7,8,9]
Prelude> take 10 second_col 
[0,1,3,6,10,15,21,28,36,45]
Prelude> take 10 third_col 
[0,1,4,10,20,35,56,84,120,165]

Answer 2

Adding to perimosocordiae's great answer, languages like Haskell are so slick they allow you to make an infinite list of infinite lists.

First lets define the operator that produces each successive row:

op :: [Integer] -> [Integer]
op = scanl1 (+)

As explained by perimosocordiae, this is just a lazy running sum.

We also need a base case:

tnBase :: [Integer]
tnBase = [0..]

So how do we get an infinite list of infinite lists of tetrahedral numbers? We iterate this operation on the base case, then the output produced by the base case, then that output...

tn = iterate op tnBase

iterate is in the Prelude, such functions can be found using hoogle and searching by name (if you have a good guess) or type signature (you generally know the signature of what you need). Source code is usually linked from the haddock documentation.

Presentation

(in case you're not comfortable with map, take, drop, and head)

This is all well and good, but rather useless if you don't know how to get passed the first infinite list to see the second, third, etc. There are plenty of options, for just getting a particular list you can drop the first few:

getNthTN n = head (drop n tn)

Getting the first few results of each list is probably more what you're looking for though:

printFirstFew n m = print $ take m (map (take n) tn)

Here map (take n) tn will take the first n values from each list of tetrahedral numbers while take m will limit our results to the first m lists.

And lastly, I like the awesome groom package for quick interactive playing with data:

> groom $ take 10 (map (take 10) tn)
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
 [0, 1, 3, 6, 10, 15, 21, 28, 36, 45],
 [0, 1, 4, 10, 20, 35, 56, 84, 120, 165],
 [0, 1, 5, 15, 35, 70, 126, 210, 330, 495],
 [0, 1, 6, 21, 56, 126, 252, 462, 792, 1287],
 [0, 1, 7, 28, 84, 210, 462, 924, 1716, 3003],
 [0, 1, 8, 36, 120, 330, 792, 1716, 3432, 6435],
 [0, 1, 9, 45, 165, 495, 1287, 3003, 6435, 12870],
 [0, 1, 10, 55, 220, 715, 2002, 5005, 11440, 24310],
 [0, 1, 11, 66, 286, 1001, 3003, 8008, 19448, 43758]]