News for hackers. Stuff that matters.
Re:Once you go functional, you can never go back by wz1000 on Monday May 18, 2015 @09:49AM (#9564378)
Here's a memoized Fibonacci in Haskell

    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
This is essentially equivalent to

   long memotable[]; // filled with -1, with first elements 0 and 1
   long fib(int n) {
       if(memotable[n] != -1)
           return memotable[n];
       memotable[n] = fib(n-2) + fib(n-1);
       return memotable[n];
   }
Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory.
Re:Once you go functional, you can never go back by sriku on Thursday May 21, 2015 @12:22AM (#9580938)
> Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory.

Do you expect the following code to run in constant space?

    head (drop 1000000000 (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))
Neither ghci nor ghc seems to run it in constant space.
Re:Once you go functional, you can never go back by tome on Thursday May 21, 2015 @02:25AM (#9581231)
That's because the entries in fibs are thunks which become very large. This runs in constant space:

    zipWith' f (x:xs) (y:ys) = let r = f x y in r `seq` r : zipWith' f xs ys
    head (drop (10 ^ 9) (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))
Re:Once you go functional, you can never go back by sriku on Saturday May 23, 2015 @04:31AM (#9592342)
Nice. .. and you meant to type zipWith' on the second line.
Re:Once you go functional, you can never go back by tome on Saturday May 23, 2015 @09:14AM (#9592811)
Yeah I did!
Re:Once you go functional, you can never go back by cygx on Monday May 18, 2015 @12:31PM (#9565325)
That's totally academic anyway: With 64-bit integers, you can only go as high as n=92 (aka floor 64/lb φ) before overflowing.
Re:Once you go functional, you can never go back by dllthomas on Monday May 18, 2015 @07:55PM (#9567497)
With Haskell, you aren't limited to 64-bit.

    Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
    Prelude> :set +s
    Prelude> fibs !! 10000
    33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
    (0.03 secs, 15,213,608 bytes)
If you have a practical use for large Fibonacci numbers, this seems an entirely practical way of producing them.