Feeds:
Posts

I have been doing some python brush-up over the last couple of days, and came across the following bit of code in an irc chat about approaches for fibonacci in python.

``````
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return a
print fib(1000)
``````

I think this is pretty typical, reasonable, and efficient python code.

I wondered, how would I express this in haskell? How different this computation looks from the canonical

fibs = 1:1:zipwith (+) fibs (tail fibs)

!

The answer, as is commonly the case for code written in imperative languages, is that this algorithm lives in the state monad. It can be ported to haskell, practically transliterated, as:

``````
{-
-- haskell translational of python algo
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return a
print fib(1000)
-}
fib :: Integer -> Integer
fib n = flip evalState (0,1) \$ do
forM (xrange n) \$ \_ -> do
(a,b) <- get
put (b,a+b)
(a,b) <- get
return a

xrange n = [0..(n-1)]

-- test that it works

t = fib 1000 == traditionalFib 1000
``````

Also added this to hawiki at

### 14 Responses

1. interesting exercise, although i still like the following more

fibs = unfoldr (\(a,b)->Just(a,(b,a+b))) (1,1)

why recursive definition when a non-recursive is just as easy? and not relying on a clever implementation.

2. I’d not use something as elaborate as a state monad, when a lazy list will do:

def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return a
print fib(1000)

Would go to:

{-# LANGUAGE BangPatterns #-}

main = print (fib 1000)

fib n = take n (go 0 1)
where
go !a !b = a : go b (a + b)

3. Hey, I find your post really showing how to use a state in Haskell in the same way how it is used in Python for example! I liked it so much, that I even translated it to my blog here: http://gracjanpolak.wordpress.com/2009/12/13/transliteracja-pythona-do-haskella/. I hope you don’t mind Polish translations!

4. on December 13, 2009 at 2:57 pm | Reply optionsanarchist

So what you’re saying is that the State monad provides an isomorphism between imperative and procedural programming.

In that sense, they both are (for all intents and purposes) equal.

(a,b) <- get
put (b, a+b)

you could also do

modify (snd &&& uncurry (+))

Although whether that is clearer is up for debate. =)

6. Is this really more idiomatic than lifting the assignment to argument-passing in the usual way?

fib n =
let
fib 0 a b = a
fib n a b = fib \$ n – 1 \$ b \$ a + b
in fib n 0 1

• on January 17, 2010 at 6:41 pm | Reply thomashartman1

My point is that what’s more idiomatic depends on what your context (or your primary programming language) is.

This post was aimed at pythonistas, and people that claim that haskell is a single paradigm language that is unfriendly to people that only have experience in imperative programming.

fib :: Integer -> Integer
fib n = flip evalState (0,1) \$ do
replicateM n \$ do
modify \$ \(a,b) -> (b,a+b)
gets fst

8. Nice work!

modify \x -> (snd x, (snd x) + (fst x))

And you can do “return \$ gets fst” rather than getting b again and not using it.

I actually wonder what the point-free version of that modify lambda expression would look like.

9. Sorry, I forgot the part where I was wondering if what I just wrote could be written similarly in Python.

It’s good to see code expressed similarly between languages, but it makes me wonder if there’s another perhaps more expressive way to do the same in Python too!

• on January 17, 2010 at 6:42 pm | Reply thomashartman1

I kind of doubt it, because if you try to to do any kind of recursive fib in python you run into “maximum recursion levels” exceeded error.

10. I would probably write it :

> fib n = flip evalState (0,1) \$ do
> replicateM n \$ modify (\(a,b) -> (b,a+b))
> gets fst

11. [...] below method comes courtesy of Thomas Hartman from the Patch-Tag blog. I belive that it shows how elegant Haskell code can look, even while using the State Monad to hide [...]

12. Even simpler version:

fib = f n 0 1
f 0 a b = a
f n a b = f (n-1) b (a+b)