Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

fpinscala読書会#3

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

2.5 Polymorphic functions: abstracting over types

多相関数。 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の型推論はそんなに親切じゃない。→うまい付き合い方を見ていく。

2.6 Following types to implementations

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

EXERCISE 2.3 Currying

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

3 Functional data structures

  • functional programming において、データ型がどのように定義されるかを見ていく。
  • パターンマッチの手法を学ぶ。
  • 例題の回答は github にあるよ。

3.1 Defining functional data structures

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

3.2 Pattern matching

和と積をパターンマッチで定義

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)

EXERCISE 3.1 どれにマッチする?

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 になる。

追加問題1: 以下を評価するとどうなる?

List("hoge","fuga","hoga") match {
  case "hoge" => 1
  case _ => 2
}

追加問題2: 関数lengthをパターンマッチでつくれ

  • length[A](as: List[A]): Int
  • 以下を満たすこと
  • length(Nil) = 0
  • length(List("one", "two", "three")) = 3

追加問題3: 関数takeをパターンマッチでつくれ

  • 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.