scala を左傾化させる話

Scala exercises for beginners を foldLeft で解いてみた。

  // 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)

参考文献

• A tutorial on the universality and expressiveness of fold

蛇足ですが、上記文献の fold == 遅延評価版のfoldRight に相当します。「5.1 The foldl」が foldLeft の話です。