How to write fibonacci in functional style without mutating external state?

Question

I am trying to understand how a Fibonacci number generator would be implemented in a pure functional paradigm. I can make the memoized version but that follows the state of an external variable as it recurses so that breaks functionality (to my naive understanding at least). Is there a way to do this without breaking the functional paradigm? My base implementation that uses a variable outside the function whose state is used for the algo.

known = {
        0:0,
        1:1
        }
def fib(n):
    if n in known:
         return known[n]
    else:
         known[n] = fib(n-1) + fib(n-2)
         return known

How can I change fib so that it works, but without modifying external state, like known above?

@Carcigenicate Given the wideness should I delete the question? — user85779, May 12 '19 at 00:52
Question title was poor but what the OP seeks is obvious based on the post. I edited the post and voted to reopen this question. — Mulan, May 12 '19 at 06:17
@Error-SyntacticalRemorse Would a generator help, given that with a memoized version no redundant calculations (and all their sub-calculations) are ever actually carried out? — user85779, May 12 '19 at 10:27
1) The code you provided needs a `global known` inside of `fib`. 2) `from functools import lru_cache` is a built in memoize decorator. 3) Memoize only remembers input (which in your case works because of recursion) however it still makes several lookups. If you make a generator that dynamically creates more fib numbers as needed and puts them in a list then you can get `O(1)` lookup except if it has not been generated then it is `O(n)` where `n` is the number of fib numbers you need to still generate. — Error - Syntactical Remorse, May 12 '19 at 15:03

Mulan · Accepted Answer · 2019-05-12T17:43:01.967

Here's one way you can do it using default arguments -

def fib (n, a = 0, b = 1):
  if n == 0:
    return a
  else:
    return fib (n - 1, b, a + b)

print (fib (10))
# 55

print (fib (100))
# 354224848179261915075

And another way using an internal helper function, loop -

def fib (n):
  def loop (m, a, b):
    if m == 0:
      return a
    else:
      return loop (m - 1, b, a + b)
  return loop (n, 0, 1)

print (fib (10))
# 55

print (fib (100))
# 354224848179261915075

We can even make a generic loop and recur interface that allows for infinite recursion so that calculating large fib number will not overflow the stack -

def recur (*values):
  return (recur, values)

def loop (f):
  a = f ()
  while isinstance (a, tuple) and a[0] is recur:
    a = f (*a[1])
  return a

def fib (n):
  def step (m = n, a = 0, b = 1):
    if m == 0:
      return a
    else:
      return recur (m - 1, b, a + b)
  return loop (step)

print (fib (10))
# 55

print (fib (100))
# 354224848179261915075

print (fib (2000))
# 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125

This final implementation is capable of seriously big fibonacci numbers. The 10,000^th fib is calculated in a flash and the result is over 2,000 digits long -

print (fib (10000))
# 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

[TIL](https://stackoverflow.com/questions/48787082/what-effects-are-modeled-by-the-stream-infinite-list-monad/48792806#comment98838419_48792806) a totally crazy way to code up the old double-recursive Fibonacci in Haskell: ``fibs = liftA2 (+) (cons 0 (cons 1 fibs)) (cons 1 fibs) where cons x ns i | i==0 = x | otherwise = ns (i-1)``. :) :) takes forever to get past the 30th, of course. :) — Will Ness, May 13 '19 at 05:03
very cool. implementing programs with lazy streams like these still twist my brain harder than almost any other programming problem. now i'm contemplating some combination of streams that produces the same result but in a more efficient way... as always, thanks for sharing. — Mulan, May 13 '19 at 05:19
yes. :) and this is *not* streams. :) :) I didn't check but with streams I think it *is* efficient (just change `cons` to `Cons`). but with that "isomorphic" representation, it's not. I had fun working the translation out bit by bit. -- there're also ways to make it slower -- to varying degrees -- with streams/lists too. user:pigworker posted something like that once, maybe I'll find the link. Something about emulating fix (or finding fixpoint) with foldr. Later. :) — Will Ness, May 13 '19 at 05:26
sorry, I was imagining the recursive `xs = (cons 0 (cons 1 xs))` as a sort of stream because haskell evaluates it lazily. I shouldn't have said it's a stream :( — Mulan, May 13 '19 at 05:36
why not, it is, only encoded differently. (I guess I'm confused there, huh). that's what was funny/crazy about it. :) that post shows the mutual encoding ("isomorphism") between streams and functions from natural numbers (like `f xs i = xs !! i`). With `Cons` it's a stream but with `cons` it's a function. If we substitute all the definitions we end up with `fibs = \ case 0 -> 0 + 1 ; 1 -> 1 + fibs 0 ; i -> fibs (i-2) + fibs (i-1)`. Funny. :) — Will Ness, May 13 '19 at 07:26
@WillNess A more idiomatic approach would be `fibs = cons 0 (cons 1 (liftA2 (+) fibs (fibs . succ)))` where `cons x f 0 = x; cons x f n = f (pred n)`. However, it should be noted that this implementation is not memoized even though it looks like the idiomatic memoized fibonacci sequence, `fib = 0 : 1 : zipWith (+) fib (tail fib)`. This is because `cons` is not memoized. If we use a memoized version of `cons` (i.e. `cons x f = ((x : map f [0..]) !!)`), then it can compute `fibs 10000` in a flash. — Aadit M Shah, May 13 '19 at 12:23
@AaditMShah ah, yes, the leading members of the sequence. `tail == (. succ)`, also nice! --- re memoization, the original point of that exercise was to represent lists with functions, so using list there becomes kind of circular... — Will Ness, May 13 '19 at 12:36
@WillNess You don't need lists for memoization. However, it's the most convenient way to get the point across in a comment. — Aadit M Shah, May 13 '19 at 13:16

How to write fibonacci in functional style without mutating external state?

1 Answers1