Last active
October 13, 2015 01:38
-
-
Save sshark/4119287 to your computer and use it in GitHub Desktop.
Simple maths functions e.g. Fibonacci and factorial sequences
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
// better use of lazy eval with Stream. | |
// please refer to http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Stream for details | |
lazy val fib: Stream[Int] = Stream.cons(0, Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2))) | |
implicit def iterableWithSum(it: Iterable[Int]) = new { def sum = it.foldLeft(0)(_ + _) } | |
fib.filter( _ % 2 == 0).takeWhile(_ < 4000000).sum | |
/* | |
The following implementation provides a more "cost effective" implementation due to the fact that | |
it has a more direct route to the numbers themselves | |
Don't quite understand this statement I copied from Scala API. | |
*/ | |
lazy val fib: Stream[Int] = { | |
def loop(h: Int, n: Int): Stream[Int] = h #:: loop(n, h + n) | |
loop(1, 1) | |
} | |
// not a good idea to use def, there is no memoization | |
def fib() : Stream[BigInt] = { | |
def fib0(prev: BigInt, acc : BigInt) : Stream[BigInt]= { | |
prev #:: fib0(acc, acc + prev) | |
} | |
fib0(0, 1) | |
} | |
fib take 10 toList | |
// factorial sequence | |
val facSeq : Stream[BigInt] = { | |
def facSeq0(j : BigInt, acc : BigInt) : Stream[BigInt] = { | |
acc #:: facSeq0(j + 1, acc * j) | |
} | |
facSeq0(1, 1) | |
} | |
facSeq take 10 print | |
facSeq take 5 filter(_ % 2 == 0) reduceRight (_ + _) // 32 | |
import scala.annotation.tailrec | |
def fac(i : BigInt) : BigInt = { | |
@tailrec | |
def fac0(j : BigInt, acc : BigInt) : BigInt = { | |
if (j == 0) acc | |
else fac0(j - 1, acc * j) | |
} | |
fac0(i, 1) | |
} | |
fac(5) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Changed Int to BigInt to correct overflow