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!

Note that the task asks to produce an array (read: vector), and this will return a seq. Tests pass nonetheless. Rant mode off.

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!

You're missing a couple of test cases.

Also, can you do it without memoisation? I did this whole thread to figure out how to do it with dynamic programming instead of memoisation.

I started understanding a bit of dynamic programming one day, and realised that this way of calculating Fibonacci fit the definition.