• Advertisement
Sign in to follow this  

F# Ackermann Stack overflow

This topic is 3588 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So, I'm tinkering with a memoizing implementation of the Ackermann function using BigInt, and getting a stack overflow. I'm pretty sure I understand why - the closure for the memoization means that it's not able to 'true' tail recursion, so it can't be optimized out to a loop (and, yes, I've tested under Release mode with -O3). Can anyone see how to fix this, or even just comment on style?

open System
open System.Collections.Generic

let memoize f = let cache = new Dictionary<_, _>()
                fun args -> if cache.ContainsKey(args)
                              then cache.[args]
                              else let r = f args
                                   cache.[args] <- r

let rec _ack (m, n) = if m = 0I
                        then n + 1I
                        else if n = 0I
                               then ack (m - 1I, 1I)
                               else ack (m - 1I, ack (m, n - 1I))
and ack = memoize _ack
let main = Console.WriteLine(ack (4I, 1I))

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement