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:
import Control.Monad.State
{-
-- 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
traditionalFibs' = 1: 1: (zipWith (+) traditionalFibs' (tail traditionalFibs'))
traditionalFib n = traditionalFibs' !! (n-1)
t = fib 1000 == traditionalFib 1000
Also added this to hawiki at
http://www.haskell.org/haskellwiki/The_Fibonacci_sequence#With_state
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.
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)
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!
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.
Instead of
(a,b) <- get
put (b, a+b)
you could also do
modify (snd &&& uncurry (+))
Although whether that is clearer is up for debate. =)
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
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.
How about:
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
replicateM n $ do
modify $ \(a,b) -> (b,a+b)
gets fst
Nice work!
How about
modify \x -> (snd x, (snd x) + (fst x))
instead of “get” then “put”
for your state update.
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.
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!
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.
I would probably write it :
> fib n = flip evalState (0,1) $ do
> replicateM n $ modify (\(a,b) -> (b,a+b))
> gets fst
[...] 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 [...]