Haskell-style recursive lazy list in Python

Gong-Yi Liao 0
Viewed 116

Consider a generalized Fibonacci series:

Y_n = f({Y_i}_{n-k}^{n-1})

we can implement this series in a Haskell one-liner:

gfib f xs = (head xs) : gfib f ((tail xs) ++ [f xs])

with results:

ghci> take 10 $ gfib sum [0, 0, 1]
[0,0,1,1,2,4,7,13,24,44]
ghci> take 10 $ gfib sum [0, 1]
[0,1,1,2,3,5,8,13,21,34]

I am wondering how can I implement the same series in Python with least code as possible and not using class/objects.

Thanks.

haskell python
1 Answers

Use a generator:

def gfib(f, xs_init):
  xs = xs_init[:] # make a copy to keep all mutations local
  while True:
    x = f(xs)
    yield xs.pop(0)
    xs.append(x)
4castle0
Related