I saw this video concerning iterative function sequences
and thought that would be a good example to play around with in Haskell. Haskell has arbitrary precision integers, and also has rational numbers, standard. (I hesitate to say “built in” because, like many languages, the true built-in core is minimal with layers of library code on top of that. But it was available out of the box.)
It also has an
iterate function. What’s interesting is that the result is naturally presented as an infinite list. Other languages with abstract iteration or generators will provide some kind of interface to make your custom thing handleable in a common way. Perl even has a
tie feature to make your custom thing seem exactly like the built-in collections, which pushes the interface contract down to include native datatypes, rather than being layered on top of them.
But in Haskell, the generator is the native list. Rather than make some custom generating code support the iteration mechanism, the same old list holds what appears to be the complete result, as if done as an earlier step.
In some purely imperative language, you might ordinarily do things like:
- Select the common, standard, container type with the appropriate properties (e.g. linear, sequential).
- Run a computation loop and fill the container with the results.
- Pass the container to another procedure, which can use the contents for other work (e.g. print them to a file).
Suppose that was unsuitable for some reason and you wanted to delay the computations of step 2, running the producer in parallel with the consumer, or not bothering until/unless a value was actually used by step 3, or not knowing how many items will really be needed. You would have to explicitly program in a more complex sequence of commands to achieve that.
Instead of a plain common collection (e.g. a C++ vector) you’d need something else. You need to arrange producer/consumer threads with a work queue between them, or callbacks, or something. Step 2 would be preparing the whatsit, and step 3 would still be easy enough using standard iterators to abstract the actual details of the collection/stream/whatever.
Now look at it in Haskell. Steps 1 is not much to think about as the list is king. Step 2 is:
lz = iterate (λx→2*x+1) 0
Later, other code can get values from this list, e.g.
take 10 lz
produces a result of
The value lz is just another list of Integer, as far as the language is concerned. But clearly it could not have been filled in step 2 because it is as long as I need it to be, and never specified a size when filling it. It is actually an infinite list!
This certainly looks like the simple approach of: create the values, then use them. However, it actually doesn’t do any work when lz was defined, and only computes values when subsequent code reads them. Here I asked for the first 10 elements, and the list then went ahead and realized those values. If I ask for the value at index 30 (
lz!!30) it needs to run the computation all the way to that element before telling me it’s 1,073,741,823.
This illustrates that the program here is not imperative. I didn’t program in “do this step, do the next step, etc.” Rather, I just specified that I wanted the 30th item of the list, and it did the work of figuring out just how to do that based on the definitions. It’s more like a spreadsheet: cells are not computed in order, but based on what they depend on. Haskell uses a top-down approach: when a specific value is really needed, it looks at the formula for it. Gathering the values needed for that function will set off other chains of downward dependent calculations.
Using the GHCi interactive shell, it’s easy to play with little programs like this. A more difficult problem featured in the video is
zz = abs <$> numerator <$> iterate (λx→x^2−7%4) 0
Trying a line of code, then recalling it to adjust and submit again, reminded me of a time long ago when microcomputers ran BASIC (or assembly language) and were attached to the household television.
Interactive play is the way to really learn something, and with a more complex build environment or larger programs you still try and do that. It’s the combination of a direct Read-eval-print-loop and the ability to write interesting things in a single line of text that makes this experience especially efficient.
Want to try it yourself without installing anything? Try Haskell! is a browser-based experience that invites you to “type these out and see what happens” (psst: copy/paste is faster if you really can’t wait to find out).
Back to the Sequence
The actual sequence generated by iteration is rational numbers, but we want to ignore the denominator. Then, I saw that the sign of the number was preserved with
numerator, so the abs stripped that off.
The result starts off as [0,7,21,7,114639] and then the numbers get very large. Index 7 is 595096023596888261906480183623645954687, and it quickly gets overwhelming and impractical to display.
- n=4 has 6 digits (is exactly 114639)
- n=7 has 39 digits
- n=28 has 80,807,125 digits
- n=29 has 161,614,249 digits
- n=30 has 323,228,496 digits
- n=31 has 646,456,993 digits
That’s the largest I could compute with this program. The Windows version compiles to a 32-bit program, but I used editbin to set the 3G flag, so it had 3G of user address space instead of 2. That allowed it to computer n=30. Running on a Mac, which is 64-bit, only increased that by one more before getting Segmentation fault. I suspect there are things in the implementation that top out at 4G, even when more memory is available.