title: Functional programming: How to convert an implementation of fibonacci written in python to haskell
body: <p>So, for this task I have to convert python to haskell. The code I have to implement in haskell is a code that generates a fibonacci sequence using a top down iteration method. The problem is that i'm fairly new at haskell, and I don't quite know how to execute this problem. </p>
  
  <p>I have created a while-loop in haskell, and a function. </p>
  
  <p>Python code:</p>
  
  <pre><code>def fib_top_down_iter_with_cache(n, trace=False):
      fibDict = {1:1, 2: 1}
      (inp, stack) = (['fib', n], [])
      fib_top_down_iter_with_cache.function_calls = 0
      while inp:
          if trace: 
              print(fibDict, inp, stack)
          (inp, token) = (inp[:-1], inp[-1])
          if isinstance(token, int):
              stack = [token] + stack
          elif token == 'fib':
              (n, stack) = (stack[0], stack[1:])
              fib_top_down_iter_with_cache.function_calls += 1
              if n in fibDict:
                  inp = inp + [fibDict[n]]
              else:
                  inp = inp + ['cache', n, '+', 'fib', n - 1, 'fib', n - 2]
          elif token == '+':
              (n1, n2, stack) = (stack[0], stack[1], stack[2:])
              inp = inp + [n1 + n2]
          elif token == 'cache':
              (n1, n2, stack) = (stack[0], stack[1], stack[1:])
              fibDict[n1] = n2
          else:
              raise Exception()
      return stack[0]
  </code></pre>
  
  <p>What I have tried in haskell:</p>
  
  <pre><code>while :: state -&gt; (state -&gt; Bool) -&gt; (state -&gt; state) -&gt; (state -&gt; result) -&gt; result
  while state eval bodyFn extractRes
      | eval state = while (bodyFn state) eval bodyFn extractRes
      | otherwise = extractRes state
  
  data Input
      = Word String | Num Integer
      deriving (Eq, Show)
  
  word :: Input -&gt; String
  word (Word x) = x
  
  value :: Input -&gt; Integer
  value (Num x) = x
  
  fibTopDownIterWithCache :: Integer -&gt; Integer
  fibTopDownIterWithCache n = fibTopDownIterWithCache []
  fibTopDownIterWithCache n cache = while ([Word "fib", Num n], [])
                                          (-- Just don't know how to implement the rest)
  </code></pre>
  
  <p>So, the cache has to be implemented as a Data.Map data type, and I have to attach the cache as an attribute of the function (which i have done, i think). Then I have to pass the cache around as an additional parameter. </p>
  
  <p>The expected value is just the nth fibonacci value. </p>