Scala exercises for beginners をやってみた。

https://gist.github.com/horiuchi/5106615

scalaで何か書いてみようと、手始めに λ Tony's blog λ - Scala exercises for beginners をやってみました。解答は上記のGistに置きました。
問題としては scalaの構文を覚えることと関数型的な書き方に慣れるためのものです。なので、普通に再帰で書く場合と、foldrを使った畳み込みでやる場合の2通りで書いてみました。

Haskellっぽく、解けたので問題自体は難しくなかったです。
書いていて気になったのは、foldrにlambdaを渡す際に引数の型を明示しないとならないのがちょっと違和感。scalaでは型は基本的に明示するものということなんですかね？型推論はそれほど強くないのかな？
今まで Haskell や C# では、特に明示しなくても推論されていたので、違いが気になりました。

解答

まずは準備として共通関数を書いておきます。

  def succ(n: Int) = n + 1
  def pred(n: Int) = n - 1

  def id[A](x:A):A = x

  def foldRight[A, B](x: List[A], f: (A, B) => B, v: B): B = x match {
    case Nil => v
    case a:: tail => f(a, foldRight(tail, f, v))
  }
  def foldLeft[A, B](x: List[A], f: (B, A) => B, v: B): B = x match {
    case Nil => v
    case a :: tail => foldLeft(tail, f, f(v, a))
  }

  def foldLeft2[A, B](x: List[A], f: (B, A) => B, v: B): B = {
    def h(a:A, g:B => B): B => B = (b:B) => g(f(b, a))
    foldRight(x, h, id[B] _)(v)
  }

問題1

「todo: Assume x and y are 0 or positive. Do not use + or - on Int. Only permitted to use succ/pred (above).」
とあるので、単純に再帰で解きました。

  // Exercise 1
  // Relative Difficulty: 1
  // Correctness: 2.0 marks
  // Performance: 0.5 mark
  // Elegance: 0.5 marks
  // Total: 3
  def add(x: Int, y: Int): Int = y match {
    case 0 => x
    case _ => add(succ(x), pred(y))
  }

問題2

Listの合計を求める問題。Exercise1のadd関数を使って解きました。
sum は単純な再帰で、sum2は末尾再帰関数で、sum3はfoldrで。

  // Exercise 2
  // Relative Difficulty: 2
  // Correctness: 2.5 marks
  // Performance: 1 mark
  // Elegance: 0.5 marks
  // Total: 4
  def sum(x: List[Int]): Int = x match {
    case Nil => 0
    case a :: tail => add(a, sum(tail))
  }
  def sum2(x: List[Int]): Int = {
    def f(x: List[Int], r: Int): Int = x match {
      case Nil => r
      case a :: tail => f(tail, add(r, a))
    }
    return f(x, 0)
  }
  def sum3(x: List[Int]): Int = foldRight(x, add, 0)

問題3

Listの長さを求める問題。
lengthは単純な再帰で、length2は他の関数を使って、length3はfoldrで解きました。

  // Exercise 3
  // Relative Difficulty: 2
  // Correctness: 2.5 marks
  // Performance: 1 mark
  // Elegance: 0.5 marks
  // Total: 4
  def length[A](x: List[A]): Int = x match {
    case Nil => 0
    case a :: tail => 1 + length(tail)
  }
  def length2[A](x: List[A]): Int = sum(map(x, (_:A) => 1))
  def length3[A](x: List[A]): Int = foldRight(x, (a:A, b:Int) => 1 + b, 0)

問題4

mapを再定義する問題。map関数は、関数型言語の基本要素の１つですね。
単純な再帰と、foldrでそれぞれ解きました。

  // Exercise 4
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.0 mark
  // Elegance: 1.5 marks
  // Total: 7
  def map[A, B](x: List[A], f: A => B): List[B] = x match {
    case Nil => Nil
    case a :: tail => f(a) :: map(tail, f)
  }
  def map2[A, B](x: List[A], f: A => B): List[B] = foldRight(x, (a:A, l:List[B]) => f(a) :: l, Nil)

問題5

filterを再定義する問題。こちらも、関数型言語の基本要素の１つですね。
また、単純な再帰と、foldrでそれぞれ解きました。

  // Exercise 5
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def filter[A](x: List[A], f: A => Boolean): List[A] = x match {
    case Nil => Nil
    case a :: tail if f(a) => a :: filter(tail, f)
    case a :: tail         => filter(tail, f)
  }
  def filter2[A](x: List[A], f: A => Boolean): List[A] = foldRight(x, (a:A, l:List[A])=> if (f(a)) a :: l else l, Nil)

問題6

ListとListを連結する関数。
単純な再帰と、foldrでそれぞれ解きました。

  // Exercise 6
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def append[A](x: List[A], y: List[A]): List[A] = x match {
    case Nil => y
    case a :: tail => a :: append(tail, y)
  }
  def append2[A](x: List[A], y: List[A]): List[A] = foldRight(x, (a:A, l:List[A]) => a :: l, y)

問題7

ListのListをListに均す関数。
append関数を使って、単純な再帰とfoldrでそれぞれ解きました。

  // Exercise 7
  // Relative Difficulty: 5
  // Correctness: 4.5 marks
  // Performance: 1.5 marks
  // Elegance: 1 mark
  // Total: 7
  def concat[A](x: List[List[A]]): List[A] = x match {
    case Nil => Nil
    case a :: tail => append(a, concat(tail))
  }
  def concat2[A](x: List[List[A]]): List[A] = foldRight(x, append[A], Nil)

問題8

concatする際に単純に均すのではなく、何らかの処理を行う関数。
concatとほぼ同じ処理なのでappend関数を使って、単純な再帰とfoldrでそれぞれ解きました。

  // Exercise 8
  // Relative Difficulty: 7
  // Correctness: 5.0 marks
  // Performance: 1.5 marks
  // Elegance: 1.5 mark
  // Total: 8
  def concatMap[A, B](x: List[A], f: A => List[B]): List[B] = x match {
    case Nil => Nil
    case a :: tail => append(f(a), concatMap(tail, f))
  }
  def concatMap2[A, B](x: List[A], f: A => List[B]): List[B] = foldRight(x, (a:A, l:List[B]) => append(f(a), l), Nil)

問題9

Listの中の最大値を求める関数。
2引数のmax関数を定義して、単純な再帰とfoldrでそれぞれ解きました。
Listが空の場合の指定がなかったので、0を返すようにしてます。

  // Exercise 9
  // Relative Difficulty: 8
  // Correctness: 3.5 marks
  // Performance: 3.0 marks
  // Elegance: 2.5 marks
  // Total: 9
  def maximum(x: List[Int]): Int = x match {
    case Nil => 0
    case a :: tail => max(a, maximum(tail))
  }
  def max(a: Int, b:Int): Int = if (a > b) a else b
  def maximum2(x: List[Int]): Int = foldRight(x, max, 0)

問題10

Listを逆順にする関数。
逆順に処理を行う必要があるので、末尾再帰の形で解きました。
foldrでの解法も、一旦foldlをfoldrで定義してからそれを使ったものになっています。

  // Exercise 10
  // Relative Difficulty: 10
  // Correctness: 5.0 marks
  // Performance: 2.5 marks
  // Elegance: 2.5 marks
  // Total: 10
  def reverse[A](x: List[A]): List[A] = {
    def rev[A](y: List[A], r:List[A]): List[A] = y match {
      case Nil => r
      case a :: tail => rev(tail, a :: r)
    }
    rev(x, Nil)
  }
  def reverse2[A](x: List[A]): List[A] = foldLeft2(x, (l:List[A], a:A) => a :: l, Nil)

以上です。