Haskell. Po polsku.

Nowinki o funkcyjnym języku programowania Haskell

Transliteracja Pythona do Haskella

leave a comment »

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.

About these ads

Written by gracjanpolak

Grudzień 13, 2009 @ 15:42

Napisane w Haskell

Dodaj komentarz

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

WordPress.com Logo

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Twitter picture

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

Follow

Otrzymuj każdy nowy wpis na swoją skrzynkę e-mail.

%d bloggers like this: