Skip to content

Instantly share code, notes, and snippets.

@akihiro4chawon
Created May 15, 2011 09:12
Show Gist options
  • Save akihiro4chawon/972989 to your computer and use it in GitHub Desktop.
Save akihiro4chawon/972989 to your computer and use it in GitHub Desktop.
My `foldLeft` solution to Tony's scala excersize for beginners
// My `foldLeft` solution to http://blog.tmorris.net/scala-exercises-for-beginners/
object FoldExercises {
// Exercise 2
def sum(x: List[Int]): Int =
x.foldLeft(0){_ + _}
// Exercise 3
def length[A](x: List[A]): Int =
x.foldLeft(0){(sum, _) => sum + 1}
// Exercise 4
def map[A, B](x: List[A], f: A => B): List[B] =
x.foldLeft(identity: List[B] => List[B]){(kacc, h) => racc => kacc(f(h) :: racc)}(Nil)
// Exercise 5
def filter[A](x: List[A], p: A => Boolean): List[A] =
x.foldLeft(identity: List[A] => List[A]){(kxs, x) => (if (p(x)) xs => kxs(x :: xs) else kxs)}(Nil)
// Exercise 6
def append[A](x: List[A], y: List[A]): List[A] =
x.foldLeft(identity: List[A] => List[A]){(kxs, x) => xs => kxs(x :: xs)}(y)
// Exercise 7
def concat[A](x: List[List[A]]): List[A] =
x.foldLeft(identity: List[A] => List[A]){(kxs, x) => xs => kxs(append(x, xs))}(Nil)
// Exercise 8
def concatMap[A, B](x: List[A], f: A => List[B]): List[B] =
x.foldLeft(identity: List[B] => List[B]){(kxs, x) => xs => kxs(append(f(x), xs))}(Nil)
// Exercise 9
/** raise error if the list is empty */
def maximum(x: List[Int]): Int =
x.reduceLeft{_ max _}
//x.foldLeft(Int.MinValue){_ max _}
// Exercise 10
def reverse[A](x: List[A]): List[A] =
x.foldLeft(List[A]()){(acc, e) => e :: acc}
def foldRight[A, B](x: List[A], acc: B, f: (A, B) => B): B =
x.foldLeft(identity: B => B){(kacc, h) => racc => kacc(f(h, racc))}(acc)
}
object FoldExercisesTest {
import org.scalacheck._
import Arbitrary.arbitrary
import Prop._
import FoldExercises._
val prop_sum = forAll ((xs: List[Int]) => sum(xs) == xs.sum)
val prop_length = forAll((xs: List[Int]) => length(xs) == xs.length)
val prop_map = forAll((xs: List[Int], f: Int => String) => map(xs, f) == xs.map(f))
val prop_filter = forAll((xs: List[Int], f: Int => Boolean) => filter(xs, f) == xs.filter(f))
val prop_append = forAll((xs: List[Int], ys: List[Int]) => append(xs, ys) == xs ++ ys)
val prop_concat = forAll((xs: List[List[Int]]) => concat(xs) == xs.flatten)
val prop_concatMap = forAll((xs: List[Int], f: Int => List[String]) => concatMap(xs, f) == xs.flatMap(f))
val prop_maximum = forAll((xs: List[Int]) => xs.nonEmpty ==> (maximum(xs) == xs.max))
val prop_reverse = forAll((xs: List[Int]) => reverse(xs) == xs.reverse)
val prop_foldRight = forAll ((xs: List[Int], i: Int, f: (Int, Int) => Int) => foldRight(xs, i, f) == xs.foldRight(i)(f))
val props = Seq(
prop_sum,
prop_length,
prop_map,
prop_filter,
prop_append,
prop_concat,
prop_concatMap,
prop_maximum,
prop_reverse,
prop_foldRight)
def main(args: Array[String]) {
//prop_add.check(Test.Params(minSuccessfulTests=3))
props foreach (_.check)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment