Как написать фибоначчи в функциональном стиле без изменения внешнего состояния? - PullRequest
Новая
       16

Как написать фибоначчи в функциональном стиле без изменения внешнего состояния?

0 голосов
/ 12 мая 2019

Я пытаюсь понять, как генератор чисел Фибоначчи был бы реализован в чисто функциональной парадигме. Я могу сделать запомненную версию, но она следует за состоянием внешней переменной, так как она повторяется, что нарушает функциональность (по крайней мере, наивно). Есть ли способ сделать это, не нарушая функциональную парадигму? Моя базовая реализация, которая использует переменную вне функции, состояние которой используется для алгоритма. 

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

Как я могу изменить fib, чтобы он работал, но без изменения внешнего состояния, как known выше?

1 Ответ

2 голосов
/ 12 мая 2019

Вот один способ, которым вы можете сделать это, используя аргументы по умолчанию - 

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

И еще один способ, используя внутреннюю вспомогательную функцию, 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

Мы можем даже сделатьуниверсальный интерфейс loop и recur, который допускает бесконечную рекурсию, так что вычисление большого числа FIB не будет переполнять стек - 

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

Эта окончательная реализация способна к серьезно большим числам Фибоначчи.10000 th fib рассчитывается в мгновение ока, и результат имеет длину более 2000 цифр - 

print (fib (10000))
# 33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
...