Once you go functional, you can never go back

Re:Once you go functional, you can never go back by david-given on Monday May 18, 2015 @09:12AM (#9564201)

IIUIC, the example they give of recursively calculating the Fibonacci series is pretty much _the_ textbook example of how not to use recursion --- it's O(2^n) and doesn't use tail calls, which means it's slow and will gobble memory.

Actually calculating the Fibonacci series efficiently in a non-lazy functional language looks surprisingly non-trivial. In Haskell it's pretty simple:

http://blog.srinivasan.biz/software/fibonacci-numbers-the-sl...

[ Parent | on HN ]

Re:Once you go functional, you can never go back by cygx on Monday May 18, 2015 @09:27AM (#9564262)

The Haskell code in question:

    fibs = 1:1:zipWith (+) fibs (tail fibs)

It's also a common showcase for Perl6 lazy lists:

    my @fibs = 1, 1, * + * ... *;

[ Parent | on HN ]

Re:Once you go functional, you can never go back by cygx on Monday May 18, 2015 @12:32PM (#9565332)

Note that Perl6 uses big integers by default, so this will work even beyond the limit n=92 at which 64-bit integers will overflow.

[ Parent | on HN ]

Re:Once you go functional, you can never go back by dllthomas on Monday May 18, 2015 @08:23PM (#9567577)

Haskell does this, too.

[ Parent | on HN ]

Re:Once you go functional, you can never go back by codygman on Tuesday May 19, 2015 @04:46AM (#9568746)

I will admit perl 6 is pretty damn cool. I'll definitely have to look at it soon.

[ Parent | on HN ]

Re:Once you go functional, you can never go back by nanny on Monday May 18, 2015 @09:38AM (#9564308)

Seriously: Scheme is guaranteed to have tail-call replacement, the author should really take advantage of that.

Here's one that does:

    (define (fib-tco n)
      (let loop ((x 0)
                 (y 1)
                 (num n))
        (if (zero? n)
            x
            (loop y (+ x y) (- num 1)))))

Try getting the 1000th Fibonacci number which each of these.

Also, what's with the dangling parentheses?

[ Parent | on HN ]

Re:Once you go functional, you can never go back by cousin_it on Monday May 18, 2015 @09:25AM (#9564254)

Here's a page about calculating Fibonacci numbers efficiently:

http://www.nayuki.io/page/fast-fibonacci-algorithms

The method you linked to is listed there as "Dynamic programming (slow)".

[ Parent | on HN ]

Re:Once you go functional, you can never go back by philh on Monday May 18, 2015 @09:40AM (#9564323)

> Actually calculating the Fibonacci series efficiently in a non-lazy functional language looks surprisingly non-trivial.

I don't know if you'd count it as trivial, but one could do

    def fib(n, a=0, b=1, c=2):
        if n <= 1:
            return n
        if n == c:
            return a+b
        return fib(n, b, a+b, c+1)

which beats the Haskell lazy list in being O(1) space (except Python doesn't eliminate tail calls).

[ Parent | on HN ]

Re:Once you go functional, you can never go back by wz1000 on Monday May 18, 2015 @10:07AM (#9564473)

The front of the list can be garbage collected, so the Haskell version can be O(1) in memory.

[ Parent | on HN ]

Re:Once you go functional, you can never go back by dllthomas on Monday May 18, 2015 @08:35PM (#9567614)

Ignoring growth in the size of the output itself (and the intermediary values that are output of earlier stages), anyway...

[ Parent | on HN ]

Re:Once you go functional, you can never go back by Nemcue on Monday May 18, 2015 @09:52AM (#9564390)

Further more, it's very hard to see the merit of FP strictly from Fibonacci.

I'd go so far as to assume most of us don't spend all day coding anything close to Fibonacci series.

[ Parent | on HN ]