News for hackers. Stuff that matters.
Re:Once you go functional, you can never go back by sriku on Monday May 18, 2015 @09:38AM (#9564305)
I feel a bit sorry for people getting introduced to "functional programming" from the imperative world. The plethora of language features available in FLs distracts them from the main endeavour of FP - which is modeling your problem domain in terms of function composition.

With that perspective, one can do FP in pretty much any language and reap all of its conceptual and engineering benefits. Without that perspective, one can end up completely avoiding functional modeling of the problem domain at hand when using a language tailored to FP and end up faring no better than when using a language encouraging imperative style.

FWIW ..

> Fibonacci sequence in LISP-oid Scheme

.. has exponential complexity whereas the C version runs in O(n).

    long fib(long n) {
        return n < 2 ? n : fib(n-1) + fib(n-2);
    }
.. is the C equivalent of the same badly performant fib implementation.
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.
Re:Once you go functional, you can never go back by gus_massa on Monday May 18, 2015 @10:24AM (#9564591)
Racket doesn't have a built-in memorization, but you can define a "define/mem" macro to handle the memorization details and you can reuse it later. This way, the example of the article runs in O(n) time without other changes:

  #lang racket
  
  (define-syntax-rule (define/mem (name arg) body ...)
    (begin
      (define cache (make-hash))
      (define (name arg)
        (hash-ref! cache arg (lambda () body ...)))))
  
  (define/mem (fib n)
    (cond
      [(= n 0) 0]
      [(= n 1) 1]
      [else (+ (fib (- n 1)) (fib (- n 2)))]))
  
  (fib 100)
But be careful, because this is O(n) in memory because the calculated values are never collected.
Re:Once you go functional, you can never go back by lispm on Monday May 18, 2015 @12:59PM (#9565524)

    (define (fib n)
      (fib-iter 1 0 n))
 
    (define (fib-iter a b count)
      (if (= count 0)
          b
          (fib-iter (+ a b) a (- count 1))))
Re:Once you go functional, you can never go back by marcosdumay on Monday May 18, 2015 @10:37AM (#9564668)
Not sure even function composition is universal.

The ML family, for example, lets you model a lot of things in type specification, and Haskell goes even further making types a good model even for behavior. And Lisp has a deep focus on metaprograming.

Re:Once you go functional, you can never go back by sriku on Wednesday May 20, 2015 @11:55PM (#9580874)
You're partially right, but function composition features in the type world too. For example, when you say -

    data Tree a = Leaf a | Branch (Tree a) (Tree a)
It looks like you're dealing purely with types, however you've declared two constructors "Leaf" and "Branch" which are, in essence, functions with the following signatures -

    Leaf :: a -> Tree a
    Branch :: Tree a -> Tree a -> Tree a
Additionally, you have `Branch` being an operation that's closed on trees (i.e. maps trees to trees), which composes nicely.

On top of that, type classes are mechanisms to talk about which functions can be called on which data, hence guiding which functions can be composed with which others.

Re:Once you go functional, you can never go back by dschiptsov on Monday May 18, 2015 @09:43AM (#9564342)
This would cause stack overflow.
Re:Once you go functional, you can never go back by koverstreet on Monday May 18, 2015 @09:45AM (#9564357)
It won't - but how is that even relevant? The issue is that it's exponential time.