Contents
- 2 Getting started with functional programming in Scala
- 2.5 Polymorphic functions: abstracting over types
- 2.6 Following types to implementations
- 3 Functional data structures
- 3.1 Defining functional data structures
- 3.2 Pattern matching
多相関数。 cf. template programming in C++
Monomorphic function to find a String in an array
def findFirst(ss: Array[String], key: String): Int = {
@annotation.tailrec
def loop(n: Int): Int =
if (n >= ss.length) -1
else if (ss(n) == key) n
else loop(n + 1)
loop(0)
}
見付かったらそのindexを、見付からなかったら-1を返す
scala> findFirst(Array("Java", "Clojure", "Scala"), "Scala")
res0: Int = 2
scala> findFirst(Array("Java", "Clojure", "Groovy"), "Scala")
res1: Int = -1
配列から一致するものを探すというのはString以外にも拡張できる。
def findFirst[A](as: Array[A], p: A => Boolean): Int = {
@annotation.tailrec
def loop(n: Int): Int =
if (n >= as.length) -1
else if (p(as(n))) n
else loop(n + 1)
loop(0)
}
[A]の部分を type parameter declaration と呼ぶ。- as は a ∈ A の複数形を意図している。(xs とか ys もよく使う)
- p は predicate の頭文字と思われる。
String にも Int にも使える。
scala> def isScala(lang: String): Boolean = lang == "Scala"
isScala: (lang: String)Boolean
scala> findFirst(Array("Java", "Clojure", "Scala"), isScala)
res1: Int = 2
scala> findFirst(Array("Java", "Clojure", "Groovy"), isScala)
res2: Int = -1
scala> def isThree(n: Int): Boolean = n == 3
isThree: (n: Int)Boolean
scala> findFirst(Array(0, 1, 2, 3, 4), isThree)
res3: Int = 3
scala> findFirst(Array(0, 1, 2), isThree)
res4: Int = -1
EXERCISE 2.2 ソートされているかどうかを返す関数
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
@annotation.tailrec
def loop(n: Int): Boolean =
if (n >= as.length - 1) true
else if (!ordered(as(n),as(n+1))) false
else loop(n + 1)
loop(0)
}
使ってみる。
scala> def le(a: Int, b: Int): Boolean = a <= b
le: (a: Int, b: Int)Boolean
scala> isSorted(Array(1,2,3), le)
res0: Boolean = true
scala> isSorted(Array(1,3,2), le)
res1: Boolean = false
scala> def le(a: String, b: String): Boolean = a <= b
le: (a: Int, b: Int)Boolean
scala> isSorted(Array("aa","ab","c"), le)
res2: Boolean = true
scala> isSorted(Array("ab","c","aa"), le)
res3: Boolean = false
いちいち関数定義をするのが面倒なことがある → そこで anonymous function (lambda 式)
scala> (x: Int, y: Int) => x <= y
res0: (Int, Int) => Boolean = <function2>
scala> isSorted(Array(1,2,3), res0)
res1: Boolean = true
scala> isSorted(Array(1,2,3), (x: Int, y: Int) => x <= y)
res2: Boolean = true
引数の型を省略できるか？
scala> isSorted(Array(1,2,3), (x, y) => x <= y)
<console>:9: error: missing parameter type
isSorted(Array(1,2,3), (x, y) => x <= y)
^
<console>:9: error: missing parameter type
isSorted(Array(1,2,3), (x, y) => x <= y)
^
scala> isSorted(Array(1,2,3), (x: Int, y) => x <= y)
<console>:9: error: missing parameter type
isSorted(Array(1,2,3), (x: Int, y) => x <= y)
^
scala> isSorted(Array(1,2,3), (x: Int, y: Int) => x <= y)
res4: Boolean = true
Scalaの型推論はそんなに親切じゃない。→うまい付き合い方を見ていく。
partial application (部分適用)
def partial1[A,B,C](a: A, f: (A,B) => C): B => C
パラメータ二つの関数の一つ目のパラメータを潰し、パラメータ一つの関数を得る。 partial1 の実装は型シグネチャから自然に導ける。
def partial1[A,B,C](a: A, f: (A,B) => C): B => C =
(b: B) => f(a, b)
cala> partial1(1, (x: Int, y: Int) => x + y)
res0: Int => Int = <function1>
scala> res0(5)
res1: Int = 6
scala> res0(10)
res2: Int = 11
A => (B => C) とか A => (B => (C => D)) のようにパラメータを一つずつ潰して行ける形の関数を
カリー化された関数という。パラメータ二つの関数をカリー化する高階関数 curry は次のように書ける
def curry[A,B,C](f: (A, B) => C): A => (B => C) =
(a: A) => ((b: B) => f(a, b))
で、何が嬉しいの？
def isSorted2[A](as: Array[A])(ordered: (A, A) => Boolean): Boolean =
curry(isSorted[A])(as)(ordered)
scala> isSorted2(Array(1,2,3))((x, y) => x <= y)
res0: Boolean = true
型推論が効く!
EXERCISE 2.4, 2.5 も型から実装が自然に導けるという例。
def uncurry[A,B,C](f: A => B => C): (A, B) => C
def compose[A,B,C](f: B => C, g: A => B): A => C
- functional programming において、データ型がどのように定義されるかを見ていく。
- パターンマッチの手法を学ぶ。
- 例題の回答は github にあるよ。
immutable なデータ型
scala> 4 + 5
res0: Int = 9
scala> "abc" + "def"
res1: String = abcdef
scala> List(1,2,3) ++ List(4,5,6)
res2: List[Int] = List(1, 2, 3, 4, 5, 6)
list.scala
package fpinscala.datastructures
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
% scalac list.scala
% ls fpinscala/datastructures/
Cons$.class Cons.class List.class Nil$.class Nil.class
% file fpinscala/datastructures/*
fpinscala/datastructures/Cons$.class: compiled Java class data, version 50.0 (Java 1.6)
fpinscala/datastructures/Cons.class: compiled Java class data, version 50.0 (Java 1.6)
fpinscala/datastructures/List.class: compiled Java class data, version 50.0 (Java 1.6)
fpinscala/datastructures/Nil$.class: compiled Java class data, version 50.0 (Java 1.6)
fpinscala/datastructures/Nil.class: compiled Java class data, version 50.0 (Java 1.6)
% scala
Welcome to Scala version 2.11.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_40).
Type in expressions to have them evaluated.
Type :help for more information.
scala> import fpinscala.datastructures._
import fpinscala.datastructures._
scala> Nil
res0: fpinscala.datastructures.Nil.type = Nil
scala> Cons(1, Nil)
res1: fpinscala.datastructures.Cons[Int] = Cons(1,Nil)
scala> Cons(1, Cons(2, Nil))
res2: fpinscala.datastructures.Cons[Int] = Cons(1,Cons(2,Nil))
ちなみに +A の + を付けないと...
scala> Cons(1, Nil)
<console>:11: error: type mismatch;
found : fpinscala.datastructures.Nil.type
required: fpinscala.datastructures.List[Int]
Note: Nothing <: Int (and fpinscala.datastructures.Nil.type <: fpinscala.datastructures.List[Nothing]), but trait List is invariant in type A.
You may wish to define A as +A instead. (SLS 4.5)
Cons(1, Nil)
^
Nilは A によらない空リストを表す(定義に現れたNothing型は全ての型のサブタイプ)。- 参考: http://kmizu.hatenablog.com/entry/20091130/1259557761
和と積をパターンマッチで定義
object List {
def sum(ints: List[Int]): Int = ints match {
case Nil => 0
case Cons(x, xs) => x + sum(xs)
}
def product(ds: List[Double]): Double = ds match {
case Nil => 1.0
case Cons(0.0, _) => 0.0
case Cons(x, xs) => x * product(xs)
}
}
- ここで出てくる object List は companion object と呼ばれる
- 上から順にマッチングしていき、マッチしたところの
=>の右が返り値になる
scala> List.sum(Nil)
res0: Int = 0
scala> List.sum(Cons(1, Cons(2, Cons(3, Nil))))
res1: Int = 6
scala> List.product(Nil)
res2: Double = 1.0
scala> List.product(Cons(1, Cons(2, Cons(3, Nil))))
res3: Double = 6.0
scala> List.product(Cons(1, Cons(0, Cons(3, Nil))))
res4: Double = 0.0
apply
object List {
def apply[A](as: A*): List[A] =
if (as.isEmpty) Nil
else Cons(as.head, apply(as.tail: _*))
}
- variadic function (可変個引数の関数)
A*はSeq[A](http://mng.bz/f4k9) の syntactic sugar- 2.5 のコラムに書いてあるが、object 名を関数名とすると apply が呼び出される
インスタンスを簡単に作れるようになった。
scala> List.apply()
res0: fpinscala.datastructures.List[Nothing] = Nil
scala> List()
res1: fpinscala.datastructures.List[Nothing] = Nil
scala> List(1)
res2: fpinscala.datastructures.List[Int] = Cons(1,Nil)
scala> List(1,2,3)
res3: fpinscala.datastructures.List[Int] = Cons(1,Cons(2,Cons(3,Nil)))
パターンマッチの練習 (warning: match may not be exhaustive.はひとまず気にしない)
scala> List(1,2,3) match { case _ => 42 }
res0: Int = 42
scala> List(1,2,3) match { case Cons(h, _) => h }
res1: Int = 1
scala> List(1,2,3) match { case Cons(_, t) => t }
res2: fpinscala.datastructures.List[Int] = Cons(2,Cons(3,Nil))
scala> List(1,2,3) match { case Nil => 42 }
scala.MatchError: Cons(1,Cons(2,Cons(3,Nil))) (of class fpinscala.datastructures.Cons)
val x = List(1,2,3,4,5) match {
case Cons(x, Cons(2, Cons(4, _))) => x
case Nil => 42
case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
case Cons(h, t) => h + sum(t)
case _ => 101
}
scala> List(1,2,3,4,5)
res0: fpinscala.datastructures.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil)))))
→ 3つ目にマッチし、x = 1, y = 2 なので、右辺は x + y = 3 になり、定数 x は 3 になる。
List("hoge","fuga","hoga") match {
case "hoge" => 1
case _ => 2
}
length[A](as: List[A]): Int- 以下を満たすこと
length(Nil) = 0length(List("one", "two", "three")) = 3
take[A](n: Int, as: List[A]): List[A]- 以下を満たすこと：
take(3, List(1,2,3,4,5)) = Cons(1,Cons(2,Cons(3,Nil)))take(3, List(1,2)) = Cons(1,Cons(2,Nil))