Last active
December 18, 2015 17:13
-
-
Save fbiville/a09a23e09f167fc2d4f7 to your computer and use it in GitHub Desktop.
FP in Scala - exercises
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
def fib(n:Int):Int = { | |
@annotation.tailrec | |
def _fib(count:Int, x1:Int, x2:Int):Int = { | |
val current = x1+x2 | |
if (count == n) current | |
else _fib(count+1, x2, current) | |
} | |
if (n == 1) 0 | |
else if (n == 2) 1 | |
else _fib(3, 0, 1) | |
} |
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
def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = { | |
@annotation.tailrec | |
def _isSorted(head:A, rest:Array[A], previous:Boolean): Boolean = { | |
if (!previous || rest.isEmpty) previous | |
else { | |
val newHead = rest.head | |
_isSorted(newHead, rest.tail, ordered(head, newHead)) | |
} | |
} | |
if (as.isEmpty) true | |
else _isSorted(as.head, as.tail, true) | |
} |
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
def curry[A,B,C](f: (A, B) => C): A => (B => C) = { | |
(a: A) => ((b:B) => f(a,b)) | |
} |
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
def uncurry[A,B,C](f: A => B => C) : (A, B) => C = { | |
(a: A, b: B) => f(a)(b) | |
} |
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
def compose[A,B,C](f: B => C, g: A => B): A => C = { | |
(a: A) => f(g(a)) | |
} |
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
3 // ;-) |
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
def tail[A](as: List[A]): List[A] = { | |
as match { | |
case Nil => Nil | |
case Cons(_, t) => t | |
} | |
} |
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
def setHead[A](as: List[A], h:A): List[A] = { | |
as match { | |
case Nil => Cons(h, Nil) // List(h) as well | |
case Cons(_, t) => Cons(h, t) | |
} | |
} |
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
def drop[A](as: List[A], n:Int): List[A] = { | |
as match { | |
case Nil => Nil | |
case Cons(_, t) if n == 0 => as | |
case Cons(_, t) => drop(t, n-1) | |
} | |
} |
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
def dropWhile[A](as: List[A], f: A => Boolean): List[A] = { | |
as match { | |
case Nil => Nil | |
case Cons(h, t) if !f(h) => as | |
case Cons(h, t) => dropWhile(t, f) | |
} | |
} |
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
def length[A](as: List[A]): Int = { | |
foldRight(as, 0)((_, acc) => 1+acc) | |
} |
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
@annotation.tailrec | |
def foldLeft[A,B](as: List[A], z: B)(f:(B, A) => B) : B = { | |
as match { | |
case Nil => z | |
case Cons(x, xs) => foldLeft(xs, f(z, x))(f) | |
} | |
} |
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
def sum(ints:List[Int]): Int = foldLeft(ints, 0)(_ + _) | |
def product(ints:List[Int]): Int = foldLeft(ints, 1)(_ * _) | |
def length[A](as:List[A]): Int = foldLeft(as, 0)((acc, _) => acc+1) |
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
def reverse[A](as:List[A]): List[A] = | |
foldLeft(as, Nil:List[A])((acc, a) => Cons(a, acc)) |
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
def append[A](a1: List[A], a2: List[A]): List[A] = | |
foldRight(a1, a2)((a, acc) => Cons(a,acc)) |
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
def concat[A](aas: List[List[A]]): List[A] = | |
foldRight(aas, Nil:List[A])(append) |
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
def addOne(ints: List[Int]): List[Int] = | |
foldRight(ints, Nil:List[Int])((a, acc) => Cons(a+1, acc)) |
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
def doubleToString(doubles: List[Double]): List[String] = | |
foldRight(doubles, Nil:List[String])((d, acc) => Cons(d.toString, acc)) |
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
def map[A, B](as: List[A])(f: A => B): List[B] = | |
foldRight(as, Nil:List[B])((a, bs) => Cons(f(a), bs)) |
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
def filter[A](as:List[A])(f: A => Boolean): List[A] = | |
foldRight(as, Nil:List[A])((a, acc) => if (f(a)) Cons(a,acc) else acc) |
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
def flatMap[A,B](as:List[A])(f: A => List[B]): List[B] = | |
foldRight(as, Nil:List[B])((a,acc) => append(f(a),acc)) |
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
def filter[A](as:List[A])(f: A => Boolean): List[A] = { | |
flatMap(as)(a => if (f(a)) List(a) else Nil) | |
} |
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
def zip(int1:List[Int], int2:List[Int]): List[Int] = { | |
(int1, int2) match { | |
case (a,Nil) => a | |
case (Nil,b) => b | |
case (Cons(h1,t1),Cons(h2,t2)) => append(List(h1 + h2), zip(t1, t2)) | |
} | |
} |
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
def zipWith[A](a1:List[A], a2:List[A])(f: (A, A) => A): List[A] = | |
(a1, a2) match { | |
case (a,Nil) => a | |
case (Nil,b) => b | |
case (Cons(h1,t1),Cons(h2,t2)) => append(List(f(h1,h2)), zipWith(t1, t2)(f)) | |
} |
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
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = { | |
def _match[A](as:List[A], seq:List[A]): Boolean = { | |
(as, seq) match { | |
case (_, Nil) => true | |
case (Nil, _) => false | |
case (Cons(h1, t1), Cons(h2, t2)) if (h1 == h2) => _match(t1, t2) | |
case (Cons(h1, t1), Cons(h2, t2)) if (h1 != h2) => _match(t1, sub) | |
} | |
} | |
_match(sup, sub) | |
} |
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
def size[A](tree:Tree[A]): Int = | |
tree match { | |
case Leaf(_) => 1 | |
case Branch(left, right) => 1 + size(left) + size(right) | |
} |
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
def maximum(tree:Tree[Int]): Int = | |
tree match { | |
case Leaf(a) => a | |
case Branch(l, r) => maximum(l) max maximum(r) | |
} |
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
def depth[A](tree:Tree[A]): Int = | |
tree match { | |
case Leaf(a) => 1 | |
case Branch(l, r) => 1 + (depth(l) max depth(r)) | |
} |
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
def map[A, B](tree:Tree[A])(f:A => B): Tree[B] = { | |
def mapT = map(_:Tree[A])(f) | |
tree match { | |
case Leaf(a) => Leaf(f(a)) | |
case Branch(l, r) => Branch(mapT(l), mapT(r)) | |
} | |
} |
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
def size[A](tree:Tree[A]): Int = fold(tree)(Function.const(1))((a,b) => 1 + size(a) + size(b)) | |
def maximum(tree:Tree[Int]): Int = fold(tree)(identity)((a, b) => maximum(a) max maximum(b)) | |
def depth[A](tree:Tree[A]): Int = fold(tree)(Function.const(1))((a,b) => 1 + (depth(a) max depth(b))) | |
def map[A, B](tree:Tree[A])(f:A => B): Tree[B] = fold(tree)(a => Leaf(f(a)):Tree[B])((a,b) => Branch(map(a)(f), map(b)(f))) | |
def fold[A, B](tree:Tree[A])(f1: A => B)(f2: (Tree[A], Tree[A]) => B): B = { | |
tree match { | |
case Leaf(a) => f1(a) | |
case Branch(left, right) => f2(left, right) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment