4 ms·

I feel a bit sorry for people getting introduced to "functional programming" from the imperative world. The plethora of language features available in FLs distr

by sriku 11y ago

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.

dschiptsov 11y ago
This would cause stack overflow.
- koverstreet 11y ago
  It won't - but how is that even relevant? The issue is that it's exponential time.
wz1000 11y ago
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.
- cygx 11y ago
  That's totally academic anyway: With 64-bit integers, you can only go as high as n=92 (aka floor 64/lb φ) before overflowing.
  - dllthomas 11y ago
    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.
- sriku 11y ago
  > 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.
  - tome 11y ago
    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))
    - sriku 11y ago
      Nice. .. and you meant to type zipWith' on the second line.
      - tome 11y ago
        Yeah I did!
gus_massa 11y ago
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.
marcosdumay 11y ago
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.
- sriku 11y ago
  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.
lispm 11y ago
(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))))

by sriku 11y ago

dschiptsov 11y ago

This would cause stack overflow.

koverstreet 11y ago
It won't - but how is that even relevant? The issue is that it's exponential time.

wz1000 11y ago

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.

cygx 11y ago
That's totally academic anyway: With 64-bit integers, you can only go as high as n=92 (aka floor 64/lb φ) before overflowing.
- dllthomas 11y ago
  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.
sriku 11y ago
> 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.
- tome 11y ago
  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))
  - sriku 11y ago
    Nice. .. and you meant to type zipWith' on the second line.
    - tome 11y ago
      Yeah I did!

gus_massa 11y ago

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.

marcosdumay 11y ago

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.

sriku 11y ago
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.

lispm 11y ago

(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))))