Skip to content

Instantly share code, notes, and snippets.

@nvanderw
Created August 4, 2012 03:08
Show Gist options
  • Save nvanderw/3253855 to your computer and use it in GitHub Desktop.
Save nvanderw/3253855 to your computer and use it in GitHub Desktop.
Polymorphic fibonacci generation using monad transformers
import Control.Monad
import Control.Monad.State.Lazy
-- Simple way to get Fibonacci numbers using monad transformers
fibT :: (Monad m, Num a) => StateT a (StateT a m) ()
fibT = get >>= \x -> lift get >>= \y -> put y >> (lift . put $ x + y)
-- Get the nth Fibonacci number
fib :: Num a => Int -> a
fib n = execState (execStateT (replicateM_ n fibT) 0) 1
-- Composes a StateT action with itself and gets a lazy list of all resulting
-- states in the underlying monad
execStatesT :: Monad n => StateT s n a -> s -> n [s]
execStatesT m s = execStateT m s >>= \s' -> execStatesT m s' >>= \ss -> return (s':ss)
fibs :: Num a => [a]
fibs = evalState (execStatesT fibT 0) 1
main = mapM_ (putStrLn . show) (fibs :: [Integer])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment