Implementing factorial and fibonacci using the state monad (as a teaching exercise)
I've worked my way through Mike Wannier's monad tutorial (which is great) and I'm working on a few exercises in my post on how to use the "state" monad .
In particular, he offers an exercise in writing functions for factorial
and fibonacci
using the monad State
. I gave it a shot and came up with the answers below. (I find the notation do
quite confusing, hence my choice of syntax).
None of my implementations look particularly "Haskell-y", and in the interest of not internalizing bad practices, I thought I'd ask people to contribute to how they might implement these functions (using a State
monad). Is it possible to write this code much easier (besides switching to notation do
)? I strongly suspect this is the case.
I know it is a little impractical to use a monad for this purpose State
, but this is purely an educational exercise - a pun surely intended.
However, the performance is not much worse: to compute the factorial of 100000 (~ unfoldr
21k characters long response), the version took ~ 1.2 seconds (in GHCi) versus ~ 1.5 seconds for the state monad version.
import Control.Monad.State (State, get, put, evalState)
import Data.List (unfoldr)
fibonacci :: Integer -> Integer
fibonacci 0 = 0
fibonacci n = evalState fib_state (1,0,1,n)
fib_state :: State (Integer,Integer,Integer,Integer) Integer
fib_state = get >>=
\s ->
let (p1,p2,ctr,n) = s
in case compare ctr n of
LT -> put (p1+p2, p1, ctr+1, n) >> fib_state
_ -> return p1
factorial :: Integer -> Integer
factorial n = evalState fact_state (n,1)
fact_state :: State (Integer,Integer) Integer
fact_state = get >>=
\s ->
let (n,f) = s
in case n of
0 -> return f
_ -> put (n-1,f*n) >> fact_state
-------------------------------------------------------------------
--Functions below are used only to test output of functions above
factorial' :: Integer -> Integer
factorial' n = product [1..n]
fibonacci' :: Int -> Integer
fibonacci' 0 = 1
fibonacci' 1 = 1
fibonacci' n =
let getFst (a,b,c) = a
in getFst
$ last
$ unfoldr (\(p1,p2,cnt) ->
if cnt == n
then Nothing
else Just ((p1,p2,cnt)
,(p1+p2,p1,cnt+1))
) (1,1,1)
source to share
Your functions seem a little more complex than they should be, but you have the right idea. For factorial, all you need to keep track of is the current number you are multiplying and the amount you have accumulated so far. So, we'll say that State Int Int
is a computation that works with the current number in the state and returns the number you have multiplied so far:
fact_state :: State Int Int
fact_state = get >>= \x -> if x <= 1
then return 1
else (put (x - 1) >> fmap (*x) fact_state)
factorial :: Int -> Int
factorial = evalState fact_state
Prelude Control.Monad.State.Strict Control.Applicative> factorial <$> [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]
The Fibonacci sequence is similar. You need to keep the last two numbers to find out what you are going to add together and how far you have gone:
fibs_state :: State (Int, Int, Int) Int
fibs_state = get >>= \(x1, x2, n) -> if n == 0
then return x1
else (put (x2, x1+x2, n-1) >> fibs_state)
fibonacci n = evalState fibs_state (0, 1, n)
Prelude Control.Monad.State.Strict Control.Applicative> fibonacci <$> [1..10]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
source to share