Ackermann is a recursive function with a tendency to generate large numbers like there's no tomorrow. I've decided to implement it on F# as a part of my learning process.
Here is my first attempt:
let rec ackermann m n =
if m = 0 then
n + 1
else
if n = 0 then
ackermann (m - 1) 1
else
ackermann (m - 1) (ackermann m (n - 1))
Ok, not as impressive as those great samples I've been browsing on the net, but still a challenge to write for an old curly brackets developer. Here's what I found hard:
- tabs not allowed;
- initially no brackets or BEGIN/END to create blocks (#light pragma) was a problem; surprising as it may seem, this was easily absorved - now I just love it (probably because I didn't have to code a syntactic analyser for F#);
- parameters are still hard to code; not just to define, but also to push; no comma here - except for non F# CLR methods...
- the error messages are not yet natural to me; ex: "found int -> int when expecting int * int"
I confess it took me a some try and error until I got it right - it kind of remember when I learned C back in 1988: try structure.member; doesn't compile? try structure->member; Thank god for the great IDE.
Then I've tried the pattern matching way of live.
let rec ackermann m n =
match m, n with
0, n -> n + 1
| m, 0 -> ackermann (m - 1) 1
| m, n -> ackermann (m - 1) (ackermann m (n - 1))
It seems more FSharpish, right? My next step could very well be a memoization approach, who knows. One thing's for sure: learning a new language is a lesson on humbleness - I feel like a total ignorant! :)
[update]
Here are my results (ok, the table comes from wikipedia):
m\n | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 |
1 | 2 | 3 | 4 | 5 | 6 |
2 | 3 | 5 | 7 | 9 | 11 |
3 | 5 | 13 | 29 | 61 | 125 |
4 | 13 | Stack Fault | Stack Fault | Stack Fault | Stack Fault |
5 | Stack Fault | Stack Fault | Stack Fault | Stack Fault | Stack Fault |
The results are not a complete surprise. What comes as a surprise to me is that both my cores were in use during the test. Is it possible?
1 comment:
Hi,
Interesting post. The function stack overflows because it is not tail recursive. You can create a tail recursive version like so:
#light
let ackermann m n =
let rec ackermann m n acc =
match m, n, acc with
| 0, _, m :: tl -> ackermann m (n + 1) tl
| 0, n, _ -> n + 1
| m, 0, _ -> ackermann (m - 1) 1 acc
| m, n, _ -> ackermann m (n - 1) ((m - 1)::acc)
ackermann m n []
I used this function to succesfully calculate
ackermann 5 0 = 65533
But I got bored trying to calculate "ackermann 4 2" because it took so long. I think interger overflow will soon become problem, you can get round this by chaning the program to use F#'s big integers.
I too observed some usage of my second core. The only explation I can think of is this is the CLR doing an asynchronous garbage collection.
Cheers,
Rob
Post a Comment