In Haskell version, I don't know what the original problem is, but at least from reading the problem statement, I think that when the input Just [0] is given in a random test, the answer should be [0, 0] (the above code would give [] as the answer). Because Just [0] is neither Null nor Empty, it shouldn't return an empty list (and I've been hitting random tests like this).

You're right, I was out of touch with the two test cases. I've rewritten the code to calculate up to fib 10000. OCaml is a bit strict with numbers, so I'd rather not write something like that ;).

Personally, I think recursive memoization is one approach to dynamic programming (compute from before or after), but I'll consider the dynamic programming approach too!