木勉強メモ
木構造の取扱はプログラマなら基本なのかもだけれど、アルゴリズムとデータ構造をちゃんと勉強したことなかったので、必要ベースで勉強していく。
用語
用語 説明 根(root) 親を持たないノード。1つの木に対して1つ根。 辺(edge) 親から子へのリンク。 葉(leaf) 子を持たないノード。 兄弟(siblings) 親が同じ子たち。 祖先(ancestor) p → q への経路がある場合、pをqの祖先と呼ぶ。 子孫(descendant) p → q への経路がある場合、qをpの子孫と呼ぶ。 レベル(level) ある木の深さの全ノードの集合を木のレベルと呼ぶ。 (ノードの)深さ(depth) 根からノードまでの経路の長さ。 (ノードの)高さ(height) ノードから、一番深いノードまでの経路の長さ 木の高さ(Height of the tree)
木の深さ(depth of the tree)木の全ノードの最大の高さ。 ノードのサイズ 自分自身を含めた子孫の数
二分木
どのノードも、子を、1または2しか持たない時、二分木(binary tree)と呼ぶ。
二分木の構造はデータフィールドの脇に左右の子を指すリンクを持たせる形。参考資料に合わせてCだと下記のようになる。
struct BinaryTreeNode { int data; struct BinaryTreeNode *left; struct BinaryTreeNode *right; };
Scalaの場合は、left と right プロパティとして自身と同じ型の値を持つと考えて。
case class BinaryTreeNode( data: Int, left: Option[BinaryTreeNode], right: Option[BinaryTreeNode] )
二分木の演算
二分木には基本演算と補助的演算が存在する
基本演算
- 木に要素を挿入
- 木から要素を削除
- 要素を探索
- 木を横断
補助的演算
- 木のサイズを求める
- 木の高さを求める
- 最大和をもつレベルを求める
- あるノード対の最小共通祖先（LCA）を求める。など。
二分木を横断する
前順序横断
- 根を訪問
- 前順序で左部分木を横断
- 前順序で右部分木を横断
Cでの実装（Cちゃんと書いたことないから変かもしれない）
#include <stdio.h> struct BinaryTreeNode { int data; struct BinaryTreeNode *left; struct BinaryTreeNode *right; }; void PreOrder(struct BinaryTreeNode *root) { if (root) { printf("%d", root->data); PreOrder(root->left); PreOrder(root->right); } } struct BinaryTreeNode makeBinaryTreeNode(int data, struct BinaryTreeNode *left, struct BinaryTreeNode *right) { struct BinaryTreeNode temp; temp.data = data; temp.left = left; temp.right = right; return temp; } int main() { struct BinaryTreeNode node7 = makeBinaryTreeNode(7, NULL, NULL); struct BinaryTreeNode node6 = makeBinaryTreeNode(6, NULL, NULL); struct BinaryTreeNode node5 = makeBinaryTreeNode(5, NULL, NULL); struct BinaryTreeNode node4 = makeBinaryTreeNode(4, NULL, NULL); struct BinaryTreeNode node3 = makeBinaryTreeNode(3, &node6, &node7); struct BinaryTreeNode node2 = makeBinaryTreeNode(2, &node4, &node5); struct BinaryTreeNode node1 = makeBinaryTreeNode(1, &node2, &node3); PreOrder(&node1); return 0; } // 実行結果 // 1245367</pre>
Scalaで同じことをする。
def preOrder(root: BinaryTreeNode): Unit = { print(root.data) root.left.foreach(preOrder) root.right.foreach(preOrder) } val node7 = BinaryTreeNode(7, None, None) val node6 = BinaryTreeNode(6, None, None) val node5 = BinaryTreeNode(5, None, None) val node4 = BinaryTreeNode(4, None, None) val node3 = BinaryTreeNode(3, Some(node6), Some(node7)) val node2 = BinaryTreeNode(2, Some(node4), Some(node5)) val node1 = BinaryTreeNode(1, Some(node2), Some(node3)) preOrder(node1) // 1245367
もう少し、Scalaらしく書いて見る。Scalaで二分木を表現するならば、sealed trait を用いて
sealed trait Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Branch[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]</pre>
のように表現できる。trait Tree のメソッドとして preOrder を定義すると
sealed trait Tree[+A] { def preOrder: Unit = this match { case Leaf(value) => print(value) case Branch(value, left, right) => print(value) left.preOrder right.preOrder } } val leaf7 = Leaf(7) val leaf6 = Leaf(6) val leaf5 = Leaf(5) val leaf4 = Leaf(4) val branch3 = Branch(3, leaf6, leaf7) val branch2 = Branch(2, leaf4, leaf5) val branch1 = Branch(1, branch2, branch3) branch1.preOrder // 1245367 branch2.preOrder // 245 branch3.preOrder // 367</pre>
全要素を走査できるならば、map が定義できそう。
sealed trait Tree[+A] { ... def map[B](f: A => B): Tree[B] = this match { case Leaf(value) => Leaf(f(value)) case Branch(value, left, right) => Branch(f(value), left.map(f), right.map(f)) } } branch1.map(v => v * 10).preOrder // 10204050306070</pre>
foreach を定義してあげれば、preOrder 不要。
sealed trait Tree[+A] { ... def foreach[U](f: A => U): Unit = { this match { case Leaf(value) => f(value) case Branch(value, left, right) => f(value) left.foreach(f) right.foreach(f) } } }
二分木で要素を探索する。C言語版。要素が存在したら、1を返し、無ければ0を返す。
int FindInBinaryTreeUsingRecursion(struct BinaryTreeNode *root, int data) { int temp; if (root == NULL) return 0; else { if (data == root->data) return 1; else { temp = FindInBinaryTreeUsingRecursion(root->left, data); if (temp != 0) return temp; else return (FindInBinaryTreeUsingRecursion(root->right, data)); } } }
これを参考にScala版。引数に A を引数にとって Boolean を返す関数をとり、Option[A] を返す。左から順に調べる。
def find(f: A => Boolean): Option[A] = { this match { case Leaf(value) => if (f(value)) Some(value) else None case Branch(value, left, right) => if (f(value)) Some(value) else { val temp = left.find(f) if (temp.isDefined) temp else right.find(f) } } }
参考
Haskell 勉強メモ8
高階関数
Haskell は関数を引数にとったり、返り値として関数を返すことができる。このような関数を高階関数と呼ぶ。Scalaにもある。
カリー化関数
Haskellの全ての関数は、引数を1つだけ取る。今まで、複数引数を取っているように見えたものは全てカリー化された関数だ。
Prelude> :t max max :: Ord a => a -> a -> a Prelude> max 4 5 5
max 関数は2つの引数を取り、大きい方を返す関数のように見えるが実際はカリー化された関数。まず、max 4 が適用され、max 4 は1つの値を引数にとる別の関数を返す。返ってきた関数に対して、5が適用されるという流れだ。
Prelude> let max' = max 4 Prelude> :t max' max' :: (Ord a, Num a) => a -> a Prelude>
Scalaもカリー化できる。
def max(a: Int)(b: Int): Int = if (a >= b) a else b max(4)(5) val res0: Int = 5 val max2 = max(4)(_) // val max2: Int => Int = <function>
Scalaの場合はHaskellほど素直ではなく、適用しない部分には _ を入れる必要があるようだ。また、関数部分適用はカリー化されていなくてもできて
def multiThree(x: Int, y: Int, z: Int): Int = x * y * z val m2 = multiThree(3, _, _) // val m2: (Int, Int) => Int = <function> m2(2, 4) // val res2: Int = 24
のように書くこともできる。
今度は、Int を引数にとって100と比較する関数を作る。これは単純に書くとこうだが
compareWithHundred :: Int -> Ordering compareWithHundred x = compare 100 x *Main> compareWithHundred 99 GT
実際には下記のように書くことができる
compareWithHundred :: Int -> Ordering compareWithHundred = compare 100
compare 100 が引数を一つとって、Ordering を返す関数であるからだ。
Apache POI 調査
Excelを操作したいみたいな状況は割とよくある。Pythonとかのスクリプト言語だと結構対処法をが見つかるけど、Scalaだと、Java資産のApache POIくらいしかない上に情報もそんなにない（poi.scala のようなラッパーライブラリもあるようだけど、プロダクションで使うには早計感ある）。Apache POIの使い方を調べて、人並みに使えるようになろうと思う。参考記載のJavaでのApache POIの使い方を元に、Scalaで書いて感じを掴む。
準備
必要なライブラリを build.sbt に追記する。
libraryDependencies ++= Seq(
"org.apache.poi" % "poi" % "5.0.0",
"org.apache.poi" % "poi-ooxml" % "5.0.0"
)
- https://mvnrepository.com/artifact/org.apache.poi/poi/5.0.0
- https://mvnrepository.com/artifact/org.apache.poi/poi-ooxml/5.0.0
Excelファイルの作成
build.sbt の準備ができたら、Excelファイルを作成していく。
XLS ファイルの作成
今だと使う機会は少ないかもしれないが一応。XLSファイルを扱うのは、上記のライブラリのうち poi の方だ。
package dev.tchiba.researchApachePoi import org.apache.poi.hssf.usermodel.HSSFWorkbook import java.io.FileOutputStream import scala.util.{Failure, Success, Try} object XLS { def main(args: Array[String]): Unit = { val fileName = "demo.xls" val workbook = new HSSFWorkbook() // XLSにはHSSFWorkbookを使う workbook.createSheet("Tab1") Try(new FileOutputStream(fileName)) match { case Failure(exception) => exception.printStackTrace() case Success(outputStream) => workbook.write(outputStream) println(s"An Excel file $fileName has been created") workbook.close() } } }
XLSX ファイルの作成
XLSXファイルを作成するには、build.sbt 記載のライブラリのうち、後者の poi-ooxml が必要だ。処理はほとんど同じで、生成するインスタンスのクラスのみが異なる。
package dev.tchiba.researchApachePoi import org.apache.poi.xssf.usermodel.XSSFWorkbook import java.io.FileOutputStream import scala.util.{Failure, Success, Try} object XLSX { def main(args: Array[String]): Unit = { val fileName = "demo.xlsx" val workbook = new XSSFWorkbook() // XLSX を生成する場合は、XSSFWorkbookを使う workbook.createSheet("Tab1") Try(new FileOutputStream(fileName)) match { case Failure(exception) => exception.printStackTrace() case Success(outputStream) => workbook.write(outputStream) println(s"An Excel file $fileName has been created") workbook.close() } } }
Excelファイルにデータを書き込む
空のExcelファイルが作れても一ミリも嬉しくないので、データを書き込んでいこう。サンプルに下記のようなデータモデルを用意する。
case class Person(
firstName: String,
lastName: String,
birthDay: LocalDate,
email: String,
phoneNumber: String,
married: Boolean
)
これをExcelに書き込むクラスを用意しよう。参考がJavaなので、あんまり Scala っぽくないけど、下手に外れると詰まるから諦める。
package dev.tchiba.researchApachePoi import models.Person import org.apache.poi.ss.usermodel.{Sheet, Workbook} import org.apache.poi.xssf.usermodel.{XSSFSheet, XSSFWorkbook} import java.io.FileOutputStream import scala.util.{Failure, Success, Try} class PersonExcelWriter { def write(fileName: String, personList: List[Person]): Unit = { val workbook = prepareWorkbook(personList) Try(new FileOutputStream(fileName)) match { case Failure(exception) => exception.printStackTrace() case Success(outputStream) => workbook.write(outputStream) println(s"An Excel file $fileName has been created") workbook.close() } } private def prepareWorkbook(personList: List[Person]): Workbook = { val workbook: XSSFWorkbook = new XSSFWorkbook() val personSheet: XSSFSheet = workbook.createSheet("Persons") prepareHeader(personSheet) prepareTable(personSheet, personList) workbook } private def prepareHeader(personSheet: Sheet): Unit = { // ヘッダー行を作成する val headerRow = personSheet.createRow(0) // セルを作成する val firstNameHeaderCell = headerRow.createCell(0) val lastNameHeaderCell = headerRow.createCell(1) val birthdayHeaderCell = headerRow.createCell(2) val emailHeaderCell = headerRow.createCell(3) val phoneNumberCell = headerRow.createCell(4) val marriedHeaderCell = headerRow.createCell(5) // セルに値をセットする firstNameHeaderCell.setCellValue("First name") lastNameHeaderCell.setCellValue("Last name") birthdayHeaderCell.setCellValue("Birthday") emailHeaderCell.setCellValue("Email") phoneNumberCell.setCellValue("Phone number") marriedHeaderCell.setCellValue("Married") } private def prepareTable(personSheet: Sheet, personList: List[Person]): Unit = { personList.zipWithIndex.foreach { case (person, index) => // 行を作成する val row = personSheet.createRow(index + 1) // セルを作成する val firstNameCell = row.createCell(0) val lastNameCell = row.createCell(1) val birthdayCell = row.createCell(2) val emailCell = row.createCell(3) val phoneNumberCell = row.createCell(4) val marriedCell = row.createCell(5) // セルに値をセットする firstNameCell.setCellValue(person.firstName) lastNameCell.setCellValue(person.lastName) birthdayCell.setCellValue(person.birthDay.toString) emailCell.setCellValue(person.email) phoneNumberCell.setCellValue(person.phoneNumber) marriedCell.setCellValue(person.married) } } }
手順としては
- ワークブックを用意する
- シートを用意する
- カラムにデータを埋めていく
- 最後に、ワークブックをファイルに保存する
となる。
これを使う処理を書こう。
package dev.tchiba.researchApachePoi import models.Person import java.time.LocalDate object Main { def main(args: Array[String]): Unit = { val person1 = Person( firstName = "太郎", lastName = "田中", birthDay = LocalDate.of(1990, 2, 2), email = "taro.tanaka@xxx.com", phoneNumber = "090XXXXXXX", married = true ) val person2 = Person( firstName = "花子", lastName = "佐藤", birthDay = LocalDate.of(1992, 9, 9), email = "hanako.sato@xxx.com", phoneNumber = "090YYYYYYY", married = false ) val personList = List(person1, person2) val writer = new PersonExcelWriter() writer.write("person.xlsx", personList) } }
実行して出力されたファイルを開いてみると、（私のPCにはExcel入っていないので、Numbersを利用）、想定通りに値が入っていることが分かる。
参考
Apache POI に関する体系的な情報が探しづらいなか、下記の本がKindle Unlimited にあったのが救いだった。
Haskell勉強メモ 7
クイックソート
といっても、私はアルゴリズムをちゃんと勉強したことないので名前しか知らないのだけれど。。
これを関数型ではどうやって解くのかを見ていく。
が、先に手続き型ではどうやるのか。アルゴリズム本を見ながら慣れてるScalaで手続き的に書いてみる。
クイックソートとは
配列を分割して、それぞれ再帰的に解いてまとめる分割統治法にのっとったアルゴリズム。
適当にpivotを選び出し、配列全体を「pivot未満のグループ」と「pivot以上のグループ」に分割してそれぞれ再帰的に解く。
def quickSort(xs: Array[Int]): Array[Int] = {
def swap(i: Int, j: Int): Unit = {
val t = xs(i)
xs(i) = xs(j)
xs(j) = t
}
def sort(left: Int, right: Int): Unit = {
val pivot = xs((left + right) / 2)
var i = left
var j = right
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (left < j) sort(left, j)
if (j < right) sort(i, right)
}
sort(0, xs.length - 1)
xs
}
写経してみたが、手続き的な実装はいまいち分からん。。
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x : xs) =
let smallerOrEqual = [a | a <- xs, a <= x]
larger = [a | a <- xs, a > x]
in quicksort smallerOrEqual ++ [x] ++ quicksort larger
*Main> quicksort [10,8,1,3,4,12,4,1,3,9,8]
[1,1,3,3,4,4,8,8,9,10,12]
なんと分かりやすいことか。。ピボット a より小さいものと大きいものに分けてそれを再帰する。とても分かりやすい。
これをScalaで書いてみる。
def quickSort(list: List[Int]): List[Int] = {
list match {
case Nil => Nil
case ::(x, xs) =>
val smallerOrEqual = for (a <- xs; if a <= x) yield a
val larger = for (a <- xs; if a > x) yield a
quickSort(smallerOrEqual) ++ List(x) ++ quickSort(larger)
}
}
ロジックがそのまま記述されており、手続き的な実装と比べて明らかに読みやすい。
Haskell 勉強メモ6
再帰
最大値を求める関数を考えてみる。命令的に考えると、現在の最大値を保持する変数を用意し、リストの全ての要素についてループして、変数を更新していく形になる。Scalaで書いてみると
def maximum(list: List[Int]): Int = {
var max = list.head
list.foreach { v =>
if (v > max) max = v
}
max
}
となる。再帰的に書く場合最初に基底部（解を明示的に定義しなければならないケース）を定義しなければならない。単一要素のリストに対する最大値は、その唯一の要素と同じ値である。それ以上の場合は、リストの先頭要素と残りのリストの最大値でどちらが大きいかを見る。Scalaで書いてみる。
def maximum(list: List[Int]): Int = {
def max(a: Int, b: Int): Int = if (a >= b) a else b
list match {
case Nil => throw new IllegalArgumentException
case ::(head, next) if list.size == 1 => head
case ::(head, next) => max(head, maximum(next))
}
}
要素が1つのみの表現がわからなかったので、ガードでかいた。
Haskellでは
maximum' :: (Ord a) => [a] -> a maximum' [] = error "maximun of empty list!" maximum' [x] = x maximum' (x : xs) = max x (maximum' xs) *Main> maximum' [1, 3, 5, 0, 13, 11, 12] 13
replicate
Int と値をとり、その値を指定された数だけ繰り返したリストを返す。
Haskell には元々ある。
*Main> replicate 3 5 [5,5,5]
基底部を考える。0 以下の回数だけ複製することはできないので、この際は空のリストを返す。
replicate' :: Int -> a -> [a] replicate' n x | n <= 0 = [] | otherwise = x : replicate' (n - 1) x
Scalaで書く場合
def replicate[T](n: Int)(x: T): List[T] =
n match {
case k if k <= 0 => Nil
case k => x +: replicate(n - 1)(x)
}
replicate(3)(5) // val res2: List[Int] = List(5, 5, 5)
Scala側はカリー化する必要はあまりないが、Haskell と合わせている。
take
takeは指定されたリストから指定された数を返す。
take' :: Int -> [a] -> [a] take' n _ | n <= 0 = [] take' _ [] = [] take' n (x : xs) = x : take' (n -1) xs *Main> take' 3 [1,2,3,4,5] [1,2,3]
Scalaでの記述
def take[T](n: Int)(xs: List[T]): List[T] =
(n, xs) match {
case (k, _) if k <= 0 => Nil
case (_, Nil) => Nil
case (k, ::(head, next)) => head +: take(k-1)(next)
}
take(2)(List(1,2,3,4,5)) // val res3: List[Int] = List(1, 2)
Scalaのリストメソッドには、takeはあらかじめ実装されているので実用上はわざわざ作る必要はない。
override def take(n: Int): List[A] = if (isEmpty || n <= 0) Nil else { val h = new ::(head, Nil) var t = h var rest = tail var i = 1 while ({if (rest.isEmpty) return this; i < n}) { i += 1 val nx = new ::(rest.head, Nil) t.next = nx t = nx rest = rest.tail } releaseFence() h }
手続き的な実装にはなっているが。
reverse
関数をリストに取り、逆順のリストを返す
reverse' :: [a] -> [a] reverse' [] = [] reverse' (x : xs) = reverse' xs ++ [x]
Scala だと
def reverse[T](xs: List[T]): List[T] = xs match {
case Nil => Nil
case ::(head, next) => reverse(next) :+ head
}
reverse(List(1,2,3,4,5)) // val res3: List[Int] = List(5, 4, 3, 2, 1)
repeat
受け取った要素から無限リストを作る関数。Haskellは基本遅延評価だから、無限リストでも途中で切るようにとれば問題ない。
*Main> take 3 (repeat 5) [5,5,5]
再帰的実装は
repeat' :: a -> [a] repeat' x = x : repeat' x *Main> take 3 (repeat' 3) [3,3,3]
Scalaの通常のListは遅延評価ではないから、真似はできないか調べたら LazyList っていうのがあるのを知った。
val lazyList: LazyList[Int] = LazyList.continually(1).take(15)
var count = 0
lazyList.foreach { v => count += v}
println(count) // 15
API ドキュメントに記載されているサンプルが分かりやすい。
val fibs: LazyList[Int] = {
0 #:: 1 #:: fibs.zip(fibs.tail).map { n =>
println(s"Adding ${n._1} and ${n._2}")
n._1 + n._2
}
}
fibs.take(5).foreach(println)
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3
fibs.take(6).foreach(println)
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5
アクセスされて初めて評価されていることが分かる。
zip
2つのリストを引数にとり、これらを綴じ合わせて返す。
Prelude> zip [1,2] ['a', 'b', 'c'] [(1,'a'),(2,'b')]
List(1,2,3).zip(List("a", "b")) // val res9: List[(Int, String)] = List((1,a), (2,b))
実装。どちらか一方が空のリストの時は、空のリストを返す。
どちらの先頭要素もあれば、先頭要素をとったタプルを作り、再帰する
zip' :: [a] -> [b] -> [(a, b)] zip' _ [] = [] zip' [] _ = [] zip' (x:xs) (y:ys) = (x, y) : zip' xs ys
Scalaで書くと
def zip[A, B](a: List[A])(b: List[B]): List[(A, B)] =
(a, b) match {
case (_, Nil) => Nil
case (Nil, _) => Nil
case (::(x, xs), ::(y, ys)) => (x, y) +: zip(xs)(ys)
}
zip(List(1, 2, 3))(List("a", "b")) // val res11: List[(Int, String)] = List((1,a), (2,b))
elem
値とリストを受け取り、その値がリストに含まれるか調べる関数
*Main> 1 `elem` [2,3,4] False
Scalaだと contains にあたるかなと。
List(2,3,4).contains(1)
Haskell 再帰での実装。基底部は空のリストを受け取った時のFalse。リストに要素がある場合は、先頭と値を比較して一致しなければ、残りの要素に対して再帰する。
elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs
Scalaでの実装
@tailrec
def elem[A](a: A)(list: List[A]): Boolean = (a, list) match {
case (_, Nil) => false
case (a, ::(x, _)) if a == x => true
case (a, ::(_, xs)) => elem(a)(xs)
}
elem(1)(List(2,3,4)) // val res13: Boolean = false
elem(1)(List(2,1,3)) // val res14: Boolean = true
Haskell 勉強メモ5
let式
let 式は変数を束縛する。 let 式自身も式。式であるとは、「値を持つ」ということ。
円柱の表面積を求める。
cylinder :: Double -> Double -> Double
cylinder r h =
let sideArea = 2 * pi * r * h
topArea = pi * r ^ 2
in sideArea + 2 * topArea
*Main> cylinder 4 10
351.85837720205683
let は式であるので、コードの中のどんなところでも使える。
*Main> 4 * (let a = 9 in a + 1) + 2 42 -- ローカルスコープに関数を作る *Main> [let square x = x * x in (square 5, square 3, square 2)] [(25,9,4)] -- タプル要素を分解してそれぞれの名前に束縛する *Main> (let (a, b, c) = (1, 2, 3) in a + b + c) * 100 600
case 式
パターンマッチで使う。
head' :: [a] -> a head' xs = case xs of [] -> error "No head for empty lists" (x : _) -> x *Main> head' [] *** Exception: No head for empty lists CallStack (from HasCallStack): error, called at baby.hs:3:9 in main:Main *Main> head' [1, 2] 1 *Main>
case 式の構文は下記
case expression of pattern -> result
pattern -> result
pattern -> result
式に合致した最初のパターンが使われる。
case 式はどこでも使える。
describeList :: [a] -> String
describeList ls =
"The list is "
++ case ls of
[] -> "empty"
[x] -> "a singleton list"
xs -> "a longer list"
*Main> describeList []
"The list is empty"
*Main> describeList [1, 2]
"The list is a longer list"
*Main> describeList [1]
"The list is a singleton list"
Haskell 勉強メモ4
関数を書くための構文
パターンマッチ
Scala でもたくさん使うパターンマッチ。Haskell版も見てく。
渡された数が7かどうかを判別する関数。
lucky :: Int -> String lucky 7 = "LUCKY NUMBER SEVEN!" lucky x = "Sorry, you're out of luck, pal!" *Main> lucky 8 "Sorry, you're out of luck, pal!" *Main> lucky 7 "LUCKY NUMBER SEVEN!"
lucky を呼ぶと、パターンが上から下の順で試される。
def lucky(n: Int): String = n match {
case 7 => "LUCKY NUMBER SEVEN!"
case _ => "Sorry, you're out of luck, pal!"
}
lucky(8) // val res11: String = Sorry, you're out of luck, pal!
lucky(7) // val res12: String = LUCKY NUMBER SEVEN!
階乗計算するプログラムをパターンマッチを使って、再帰的に書く。
factorial :: Int -> Int factorial 0 = 1 factorial n = n * factorial (n - 1)
Scalaの場合
def factorial(n: Int): Int = n match {
case 0 => 1
case k => k * factorial(k-1)
}
タプルのパターンマッチもできる。
２次元ベクトルの足し算。
addVectors :: (Double, Double) -> (Double, Double) -> (Double, Double) addVectors a b = (fst a + fst b, snd a + snd b) -- これだと読みづらい。 addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2) -- こう書くと直感的
リスト内包表記でもパターンマッチが使える。
*Main> let xs = [(1,3),(4,3),(2,4),(5,3),(5,6),(3,1)] *Main> [a + b | (a, b) <- xs] [4,7,6,8,11,4] -- マッチしない要素は結果に反映されない。 *Main> [x*100 + 3 | (x, 3) <- xs] [103,403,503]
val list = Seq((1,3),(4,3),(2,4),(5,3),(5,6),(3,1)) for ((a, b) <- list) yield a + b // val res13: Seq[Int] = List(4, 7, 6, 8, 11, 4) for ((x, 3) <- list) yield x*100 + 3 // val res14: Seq[Int] = List(103, 403, 503)
リストもパターンマッチで使える。空のリスト [] または、: を含むパターンと合致させることができる。x:xs というパターンは、リストの先頭要素を x に束縛し、リストの残りを xs に束縛する。
head' :: [a] -> a head' [] = error "Can't call head on an empty list, dummy!" head' (x: _) = x *Main> head' [] *** Exception: Can't call head on an empty list, dummy! CallStack (from HasCallStack): error, called at baby.hs:40:12 in main:Main *Main> head' [2,3,4] 2
Scalaのパターンマッチの場合は下記。
def head[T](list: List[T]): T = list match {
case x::_ => x
case Nil => throw new IllegalArgumentException
}
head(List(2,3,4)) // val res0: Int = 2
head(List()) // java.lang.IllegalArgumentException
asパターン
Haskellには as パターン という特殊なパターンがある。値をパターンに分解しつつ、パターンマッチの対象になった値自体も参照したいときに使う。@ を使うことで、元のリスト全体にアクセスすることができる。
firstLetter :: String -> String firstLetter "" = "Empty string whoops!" firstLetter all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x] *Main> firstLetter "Dracula" "The first letter of Dracula is D"
知らなかったが Scala でも同じことができるらしい。参考
上と似たことをScalaでやると。
def firstLetter(letters: List[Char]): String = {
letters match {
case Nil => "Empty string whoops!"
case all @ (x::xs) => s"The first letter of ${all} is $x"
}
}
firstLetter("Dracula".toList) // val res3: String = The first letter of List(D, r, a, c, u, l, a) is D
@ を使うことで、元の要素にアクセスできていることが分かる。Scalaの場合は、元の要素をそのまま使えばいいんじゃとか思うけど、何か違うのだろうか。。？
ガード
引数の値が満たす性質で場合分けするとき。
bmiTell :: Double -> String bmiTell bmi | bmi <= 18.5 = "underweight." | bmi <= 25.0 = "normal" | bmi <= 30.0 = "fat" | otherwise = "Are you Whale?"
参考本のサンプルはもっと毒々しかったけど、書くの面倒だった。bmi の値で場合分けしている。
Scalaで書く場合は
def bmiTell(bmi: Double): String = bmi match { case v if v <= 18.5 => "underweight" case v if v <= 25.0 => "normal" case v if v <= 30.0 => "fat" case v => "Are you whale?" }
複数引数でも可能。
bmiTell :: Double -> Double -> String bmiTell weight height | weight / height ^ 2 <= 18.5 = "underweight." | weight / height ^ 2 <= 25.0 = "normal" | weight / height ^ 2 <= 30.0 = "fat" | otherwise = "Are you Whale?"
where
命令型のプログラミング言語なら、同じ値を何度を計算するのを避けるため、変数に格納するやることが一般的。Haskellでは、where キーワードをつかて計算の中間結果に名前をつける。さっきの bmiTell だと where /height ^ 2 を何度も書く&再評価するのは無駄が多い。下記のように修正する。
bmiTell :: Double -> Double -> String bmiTell weight height | bmi <= 18.5 = "underweight." | bmi <= 25.0 = "normal" | bmi <= 30.0 = "fat" | otherwise = "Are you Whale?" where bmi = weight / height ^ 2
where のなかでパターンマッチを使うこともできる。
initials :: String -> String -> String
initials firstname lastname = [f] ++ " " ++ [l] ++ "."
where
(f : _) = firstname
(l : _) = lastname
where ブロック内では、定数だけでなく関数も定義できる。
calcBmis :: [(Double, Double)] -> [Double] calcBmis xs = [bmi w h | (w, h) <- xs] where bmi weight height = weight / height ^ 2
