Radu Grigore wrote:
List based solutions should also work if garbage collection
is done right, e.g.,
fib n = fs !! n
where fs = 1 : 1 : zipWith (+) fs (tail fs)
So you mean my solution of the LCS problem should work in O(n) space
"if garbage collection is done right"? What exactly does this
On 6/16/05, Lennart Augustsson <[EMAIL PROTECTED]> wrote:
> fib n = f n 1 1
>where f 0 _ b = b
> f n a b = f (n-1) (a+b) a
Indeed. I should have seen this. It's a pretty standard trick for
making a function tail recursive.
> List based solutions should also work if garbage collection
Radu Grigore wrote:
Anyway, I was wondering if the O(n) space and O(n^2) time solution can
be implemented in Haskell. Another way to ask this. Consider the
classic fibonacci example. Can one compute the n-th fibonacci number
in O(n) time and O(1) space, i.e. remember only the "last" two values
du
The programming language I know best is C++. Wait, don't close the message.
I also know OCaml and a couple of days ago I read "A Gentle
Introduction to Haskell". In order to practice what I've learned a bit
above "hello world" programs I chose to solve some easy tasks from
SPOJ. They have automati
