scala函数式斐波那契数列
scala函数式斐波那契数列
新手
object fibonacci {
def main(args:Array[String]): Unit = {
println(fib(20))
}
def fib(n:Long): Long = {
@annotation.tailrec
def go(m:Long,frist:Long,last:Long): (Long,Long) = {
if(m==1)
(frist,last)
else
go(m-1,last,frist+last)
}
go(n,0,1)._2
}
}
Scheme
(define (fibonacci n)
(define (fib count a b)
(if (= count n)
b
(fib (+ count 1) b (+ a b))))
(fib 1 0 1))
(display (fibonacci 20))
学了模式匹配后
object fibonacci {
def main(args: Array[String]): Unit = {
def num(x: Long): (Long, Long) = x match {
case 0 => (0, 1)
case 1 => (1, 1 + 1)
case n => val tmp = num(n - 1);(tmp._2, tmp._1 + tmp._2)
}
println(num(20))
}
}
foldr/foldl党
object fibonacci {
def main(args: Array[String]): Unit = {
val numbers =List.tabulate(20)(_ => 0:Long)
val ans = numbers.foldLeft(List[Long](1,0))((m:List[Long],_) => (m.head + m.drop(1).head)+:m)
val ans2 = numbers.foldRight(List[Long](1,0))((_ ,n:List[Long]) => (n.head + n.drop(1).head)+:n)
println(ans)
println(ans2)
}
}
Lazy evaluation技能Get
object fibonacci {
def main(args:Array[String]): Unit = {
lazy val fibs = {
def f(a: Int, b: Int): LazyList[Int] = a #:: f(b, a + b)
f(1, 1)
}
val bigs = fibs drop 20 take 1
println(bigs.head)
}
}
强行迭代
object fibonacci {
def main(args: Array[String]): Unit = {
println(fabIteration(20))
def fabIteration(index: Int): Long = {
if (index == 1 || index == 2) {
1L
} else {
var f1 = 1L
var f2 = 1L
var f3 = 0L
for (_ <- 1 to index - 1) {
f3 = f1 + f2
f1 = f2
f2 = f3
}
f3
}
}
}
}
入”Points-free” 邪教
object fibonacci {
def main(args: Array[String]): Unit = {
val pointFree = sumPrecedingOnes andThen enumFromTo(1,20)
println(pointFree((1,1)))
}
}
object sumPrecedingOnes extends ( (((Long, Long)))=> ((Long, Long),((Long, Long)) => (Long, Long))){
override def apply(con: ((Long, Long))): ((Long, Long), ((Long, Long)) => (Long, Long)) = (con,(t:(Long,Long)) =>(t._2,t._1+t._2))
}
object enumFromTo extends ( (Int,Int) => (((Long, Long),((Long, Long)) => (Long, Long))) => (Long, Long)){
override def apply(begin: Int, end: Int) = {
(con) => {
var some = con._1
for (_ <- begin to end) {
some = con._2(some)
}
some
}
}
}
Continuation passing style
object fibonacci {
def main(args:Array[String]): Unit = {
val cc = (ones:(Long,Long)) => (ones._2,ones._1 + ones._2)
@annotation.tailrec
def facCps(index:Int,ones:(Long,Long),k: ((Long,Long)) => (Long,Long)): (Long,Long) = {
if(index == 1) {
ones
} else {
facCps(index - 1, k(ones),k)
}
}
val ans = facCps(20,(0,1),cc)
println(ans._2)
}
}
