Scala で Builder Pattern
ScalaでJava like なBuilder Patternを書く機会は自分の場合あまり無い（Static Factoryで事足りることが多い）のですが、少し古いJavaのプロダクトのリファクタをした際にBuilder Patternで生成処理を書き直したので、Scalaの場合はどうなるのか見ていこうと思います。
Generalized Typed Constraint の勉強にも一部なるところもあったりします。
JavaにおけるBuilder Pattern
JavaにおけるBuilder Pattern は GoF と Effective Java が有名かなと思います。Builder Patternの説明としては、Effective Javaの方が使い所とかが個人的には分かりやすい気がします。コードとしても、Effective Javaの書き方の方が、コードが散らばらないので好みですね。※Effective Javaはクラス内に `static class` として、`Builder` クラスを定義するが、GoFの方は、`Person` クラスと別に、`PersonBuilder` のようなクラスを作る。
JavaにおけるBuilder Pattern を使いたくなるときと、BuilderPattern以前の書き方
Builder Patternが使いたくなるのは、必須では無いけれど場合に応じて外から値を渡してオブジェクトを生成したい時、オプショナルパラメータが多い時に使いたくなります。オプショナルパラメータが多い時に選択される伝統的なパターンとして、Effective Javaではテレスコーピング・コンストラクタ（Telescoping Constructor）とJavaBeansパターンが紹介されていました。
テレスコーピング・コンストラクタは、単純にコンストラクタを複数用意するパターンです。
6個のパラメータでこれなので、コンストラクタがいくつあっても足りないですし、上から順番にしか対応できてないので、例えば、`carbohydrate` は設定したいけど、他のパラメータはデフォルトパラメータで良いとかには対応できません。
私がこの業界に入った時にはすでにJavaBeansパターンは廃れてましたが、古いプロダクトだとやはりよく使われています。JavaBeans パターンは setter を使って行うパターンです。そもそも不変でないので、バグが入り込みやすいですし、Scalaではまず出会わないですね。でもやっぱり古いJavaのプロダクトだとよく見ます。setterを排除したい時に、Builder Patternに置き換えるのはリファクタとしてはやりやすいなと思います。
Scalaを使っていると、ほぼ直面しない、値がミュータブルな状態なってしまうのがJavaBeansパターンの最悪の欠点ですね。最新のJavaは知らないですが、基本的に値がミュータブルになってるJavaといえど、イミュータブルの方が扱いやすいことには変わりありません。しかし、JavaBeansパターンはテレスコーピングパターンよりも柔軟です。値変えたいもののsetterのみを呼び出せば良いわけなので。
Builder Pattern （Java）
テレスコーピングパターンも、JavaBeansパターンもどちらも使いづらい。そこで使われるのがBuilder Patternです。（Effective Java ver.）
呼び出しのところを見ればわかるように、Builderからメソッドチェーンのように生成処理が書けます。
ScalaにおけるBuilder Pattern
Javaの方を見てわかるように、基本的にはオプショナルパラメータはデフォルト値で良くて、時々オプショナルパラメータの値を外部から渡したい。そしてそのようなオプショナルパラメータが多い時にBuilder Patternは活躍します。
case class のデフォルトパラメータを使う
Scalaでデフォルトパラメータを使う場合は、すごく簡単にかけます。
JavaのBuilder Patternとこれで同じことができています。コード量、可読性、段違いですね。
呼び出しも、オプショナルのところは名前付きで渡してあげれば自由に書けます。
Java likeに書いてみる
上のように簡単に書けるのはわかりましたが、Javaっぽく書くとどうなるのかも簡単に見ておきます。
`static class` だった `Builder` がScalaの場合はコンパニオンオブジェクトに移動するくらいですね。Javaと違って面倒なだけで、特に恩恵がないです。
Generalized type constrains
なんならここからが本題。Generalized type constrains を利用してさらにレベルアップさせます。
Scala 系のブログを漁ってたら少し古い下記の記事を見つけて知りました。コップ本にも、多分載って無い内容ですね。なので使い道とか調べるの難しい。。
上記の記事に記載がありますが
Scala2.8から、Predefに<:<とか=:=とかが定義されていて、これなんだろ?とずーっと疑問だった訳ですよ。で、ついったーで質問投げてたらやっと理解できました。
"generalized type constraints"というヤツで、型パラメータに与えられた型が、特定の条件を満たす場合にのみ呼び出せるメソッドを定義できるというものです。しかもコンパイル時に静的にチェックされる!! これはスゴい!!
https://yuroyoro.hatenablog.com/entry/20100914/1284471301
type-safe builder
すこし話は戻って、オブジェクトの生成時に、例えば特定の順序で初期化する必要があったりすることがあります（あるそうです。自分はそういうシーンにはまだ遭遇したことがない）。これまでの Builder Pattern の実装では、実行時にしかそのことを検証できませんでしたが、type-safe builder と呼ばれる実装方法を使うと、コンパイル時に検証できるようになります。
これで、例えば setFirstName を抜いて build しようとしてもIntelliJ なら静的解析の段階でエラーを出してくれますし、当然コンパイルエラーにもなります。順序を保証したい時とかに便利ですね。
最後に
Java like なBuilder PatternをScalaで使うことは基本的にはそんななく、多くはstatic factoryや、case class のデフォルトパラメータで十分だろうなと思います。type-safe builder に関してなかなかこれが必要な制約下になることはあんまり想像つきませんが、有用かなと思います。
Haskell 勉強メモ9
セクション
中置関数に対して、セクションという機能を使って部分適用をすることができる。
divideByTen :: (Floating a) => a -> a divideByTen = (/10) *Main> divideByTen 30 3.0
これは 30 / 10 と同義。
高階関数
関数を受け取り、２回適用する関数を書いてみる。先にScalaで書いてみよう。
def applyTwice[T](f: T => T)(x: T): T = f(f(x))
applyTwice { v: Int => v * 2 }(10) // 40
これを Haskell で書くとこうなる。
applyTwice :: (a -> a) -> a -> a applyTwice f x = f (f x) *Main> applyTwice (\a -> a * 2) 10 40
`(\a -> a * 2)` は Haskell の無名関数。
zipWith
標準ライブラリの zipWith
まずはHaskell標準の zipWith の挙動を確認する。
*Main> :t zipWith zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith は 2つの引数をとって1つの値を返す関数と、2つのリストを引数に取り、2つのリストの各要素に関数を適用することで、1つに結合する。
*Main> zipWith (\a b -> a + b) [1,2,3] [4,5,6] [5,7,9]
Scalaには zipWith に相当するものはないが、zip メソッドが collection 系には実装されている
List(1, 2, 3) zip List(2, 3, 4) // res2: List[(Int, Int)] = List((1,2), (2,3), (3,4))
2つのリストを引数にとって、前から順に同じ位置にある要素で構成されたタプルのリストを作って返す。これに map を適用してあげれば、先程の haskell の zipWith 相当のことが可能だ。
List(1, 2, 3) zip List(2, 3, 4) map { case (a, b) => a + b } // res2: List[Int] = List(3, 5, 7)
zipWith を実装してみる。※ 途中で、gist を使えば haskell もsyntax highlight いけることに気づいたので少し行数があるやつは試しに。
Scalaで同じようなことを書くとこんな感じ。最初の zip と map を連携させる方が読みやすいし書きやすい。
flip
普段Scalaを使っていて、さっきの zipWith なんかは似たようなもの、似たようなことを Scala でもやったことがあるが、これはhaskell本で初めてみる。
flip は関数を引数にとり、引数が入れ替わった関数を返す。※正直、何が嬉しいのか全く分からない。
Main> :t flip flip :: (a -> b -> c) -> b -> a -> c
*Main> zip [1,2,3,4,5] "hello"
[(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')]
*Main> flip zip [1,2,3,4,5] "hello"
[('h',1),('e',2),('l',3),('l',4),('o',5)]
zip は1つ目の配列と2つ目の配列の同じ位置にある要素で作ったタプルのリストを返す関数だ。1つ目の通常の zip では左の配列にあったものがタプルの左に、右の配列にあったものがタプルの右側にあるのが分かる。
flip を適用した zip はそれが逆になっている。:t で見てみるとよく分かるが、引数が入れ替わっていることが分かる。
*Main> :t zip zip :: [a] -> [b] -> [(a, b)] *Main> :t flip zip flip zip :: [b] -> [a] -> [(a, b)]
自分で実装すると下記のようになる。
木勉強メモ
木構造の取扱はプログラマなら基本なのかもだけれど、アルゴリズムとデータ構造をちゃんと勉強したことなかったので、必要ベースで勉強していく。
用語
用語 説明 根(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
