Last active
December 16, 2015 18:00
-
-
Save pelotom/5474817 to your computer and use it in GitHub Desktop.
Calculating the first n Fibonacci numbers using Effectful with the ST monad.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import effectful._ | |
import scalaz._ | |
import Scalaz._ | |
import effect._ | |
import ST._ | |
import std.indexedSeq._ | |
def fibST(n: Int): List[Int] = { | |
type ForallST[A] = Forall[({type λ[S] = ST[S, A]})#λ] | |
def compute[S] = effectfully { | |
val arr = newArr[S, Int](n, 1).! | |
for (i <- 2 until n) | |
arr.write(i, arr.read(i-2).! + arr.read(i-1).!).! | |
arr.freeze.!.toArray.toList | |
} | |
runST(new ForallST[List[Int]] { def apply[S] = compute[S] }) | |
} | |
// fibST(20) ==> List(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment