Transliteracja Pythona do Haskella
Dzisiejszy wpis jest tłumaczeniem Transliterating python to haskell: Fibonacci in the state monad Thomasa Hartmana.
Przez ostatnie kilka dni przypominałem sobie programowanie w Pythonie. Natrafiłem przy okazji na IRCu na algorytmy obliczania wartości funkcji Fibonacciego w tym języku.
def fib(n):
a, b = 0, 1
for _ in xrange(n):
a, b = b, a + b
return a
print fib(1000)
Uważam powyższy piękny kod za typową, rozsądną i wydajną implementację algorytmu w Pythonie.
> import Control.Monad.State
Jak wyrazić powyższy algorytm w Haskellu? Klasycznym sposobem obliczania ciągu Fibonacciego w tym języku jest:
> fibs = 1:1:zipWith (+) fibs (tail fibs)
Zauważmy, że kod w językach imperatywnych zwykle żyje w monadzie stanu. Dzięki temu można algorytmy imperatywne przenosić, niemalże transliterować, jako:
> 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)] > > -- sprawdźmy czy działa > traditionalFib n = fibs !! (n-1) > > t = fib 1000 == traditionalFib 1000
Algorytm dostępny jest też na HaWiki.
