sudoku-solver

あいだが空いてしまった。ちょうど1週間だ。5月の連休中から Scala のエントリを1月以上も連続で更新してたのに。まぁ、別にいいんだけど。

で、今日から再開ということで Scala をやろうと思ったんだけど、事情があって Haskell だ。

数独っていうパズルがある。ナンプレともいう、マス目に 1 から 9 の数字を入れていくアレだ。暇つぶしにやってたんだけど、入門編の問題くらいはともかく、それ以上になると途端に難しくなる。向いてないのかもしれない。

ともかく、こんなのやってられねーっというわけで、問題を解くプログラムを作ってみたわけ。Haskell で。

作ったものは GitHub にあげたので見てほしい。

 cf. takatoh / sudoku-solver

使い方はこんな感じ。

^o^ > type example2.txt
     87
928    15
     1
14    8
   485
  6    43
   5
51    924
  92

^o^ > sudoku example2.txt
431658792
928734615
675921438
147362859
392485167
856197243
284519376
513876924
769243581

問題は 9 × 9 マスに入っている数字を 9 文字 × 9 行のテキストファイルにして、sudoku プログラムにファイル名を渡してやるだけ。

「数独 難問」でググって出てきた問題でもあっという間に解ける。ああ、気持ちいい。

カテゴリー: Haskell | コメントする

Implicit Conversion

Implicit Conversion とは、暗黙の型変換をユーザが定義できるようにする機能、だそうだ。例えば、真偽値が必要なところにユーザ定義型が来たとき、その型を真偽値に変換する Implicit Conversion が定義されていれば、エラーにならずに変換される、ってことらしい。

Implicit Conversion の定義は implicit キーワードをつけたメソッド定義だと思えばいい。あとは引数が1つであることくらいか。Int を Boolean に変換する Implicit Conversion の定義はこんな感じ。

scala> implicit def intToBoolean(arg: Int): Boolean = arg != 0
warning: there was one feature warning; for details, enable :setting -feature' or:replay -feature'
intToBoolean: (arg: Int)Boolean

メソッド名はたぶん何でもいい。重要なのは引数の型と返り値の型。次の例のように、Boolean でなければいけないところ(if の条件式)に Int が来たとき、Scala は Implicit Conversion を探して、あてはまるものが見つかったらそれを適用してくれる。その結果、次のようになる。

scala> if (1) {
     |     println("1 is true.")
     | }
1 is true.

本来、if の条件式は Boolean でなければならないけど、暗黙の型変換が働いて Int を Boolean に変換した結果、1 is true. と出力されている。

もっとも、この使い方はあまり好ましくないようだ。

もうひとつの使い方は、pimp my library パターンとよばれ、既存のクラスにメソッドを追加して拡張するように見せかける使い方だ。例として、文字列の最後にスマイルマーク :-) をくっつけて返す Implicit Conversion を考えよう。

scala> class RichString(val src: String) {
     |     def smile: String = src + ":-)"
     | }
defined class RichString

scala> implicit def enrichString(arg: String): RichString = new RichString(arg)
warning: there was one feature warning; for details, enable :setting -feature' or:replay -feature'
enrichString: (arg: String)RichString

enrichString が Implicit Conversion だ。String を RichString に変換する。次のように使う。

scala> "Hi, ".smile
res2: String = Hi, :-)

“Hi, ” は String なので smile なんていうメソッドは持っていない。だけど Implicit Conversion のおかげで暗黙に RichString に変換されて、smile メソッドが呼ばれている。

さて、上の例は Scala 2.10 以降では Implicit Class という機能で実現できる。

scala> implicit class RichString(val src: String) {
     |     def smile: String = src + ":-)"
     | }
defined class RichString

scala> "Hi, ".smile
res0: String = Hi, :-)

Implicit Class は pimp my library 専用の機能なので、通常はこっちを使うといいようだ。

カテゴリー: Scala | コメントする

Try

Try には Either と同じように2つの値がある。Success と Failure だ。Either と違うのは、Failure には Throwable の値しか入れられないことだ。こんな感じ。

scala> import scala.util.Try
import scala.util.Try

scala> val v: Try[Int] = Try(throw new RuntimeException("to be caught"))
v: scala.util.Try[Int] = Failure(java.lang.RuntimeException: to be caught)

Throwable ってなに?ってかんじだけど、Java の例外みたいなものかな。

Failure には Throwable しか入れられないので、Try は1つだけ型パラメータをとって、それが Success の中身の型になる。

scala> val v1 = Try(3)
v1: scala.util.Try[Int] = Success(3)

うーん、まだ消化不良だけど、今日は時間がないのでここまで。

カテゴリー: Scala | コメントする

Either

Option には2つの値 Some と None がある。Some はある種のコンテナで中に別の値を持つことができるけど、None は値を持つことができない。

つまり、エラーが起こったこと自体は None で知らせることができても、どんなエラーなのかはわからないわけだ。そこで Either の登場だ。

Either にも2つの値 Right と Left があって、両方とも中身の値を持つことができる。通常は、正常だった時に Right を、何かエラーがあったときに Left を使う。Either は2つの型パラメータをとる。つまり Either[A, B] で、A は Left の中身の型、B は Right の中身の型だ。

scala> val v1: Either[String, Int] = Right(123)
v1: Either[String,Int] = Right(123)

scala> val v2: Either[String, Int] = Left("abc")
v2: Either[String,Int] = Left(abc)

もちろん、パターンマッチもできる。

scala> v1 match {
     |     case Right(i) => println(i)
     |     case Left(s)  => println(s)
     | }
123
カテゴリー: Scala | コメントする

Option

今日から Scala のエラーを表すデータ型を見ていく。

最初は Option 型だ。Option は言ってみれば値を1つだけ入れられるコンテナで、値の入っている Some と何もないっていないことを表す None の2つの値がある。

っていうか、これ、OCmal の Option と同じだよね。Haskell で言えば Maybe だ。

Option は、たとえば次のように作れて、動作する。

scala> val o1: Option[String] = Option("hoge")
o1: Option[String] = Some(hoge)

scala> o1.isEmpty
res0: Boolean = false

scala> o1.isDefined
res1: Boolean = true

scala> o1.get
res2: String = hoge

Option はコンテナなので型パラメータを持つ。上の例では String だ。で、持っている値は get メソッドで取得できる。

じゃあ、null を入れた場合はどうだろう。

scala> val o2: Option[String] = Option(null)
 o2: Option[String] = None

scala> o2.isEmpty
res3: Boolean = true

scala> o2.isDefined
res4: Boolean = false

scala> o2.get
java.util.NoSuchElementException: None.get
  at scala.None$.get(Option.scala:349)
  at scala.None$.get(Option.scala:347)
  … 36 elided

null を入れると Option の値としては None になる。っていうか null ってなに?Java の null?

まあいいか。とにかく中身の値がないので、get メソッドではエラーになっている。

None も Option の値なので、isEmpty とか isDefined とかのメソッドに対してはちゃんと値を返している。もうひとつ、Option には便利な getOrElse メソッドがあって None だった場合には別の値を返すことができるようになっている。

scala> o2.getOrElse("no value")
res6: String = no value

最後に、パターンマッチを見よう。

scala> val s: Option[String] = Option("hoge")
s: Option[String] = Some(hoge)

scala> val result = s match {
     |     case Some(str) => str
     |     case None => "not matched"
     | }
result: String = hoge

Option は例外と違ってふつうのデータ型なので、パターンマッチができる。例外処理を書くんではなくて、ほかのデータ型と同じような処理をかけるわけだ。

カテゴリー: Scala | コメントする

部分関数

よくわからないものが出てきた。説明の前に使い方を見てみよう。

scala> List(1,2,3,4,5).collect { case i if i % 2 == 1 => i * 2 }
res0: List[Int] = List(2, 6, 10)

リストの collect メソッドは match 式の { } で囲まれたブロックの部分だけを引数にとって、条件に合う要素だけを抜き出し、=> の右の式を適用した新しいリストを返す(でいいのかな)。この引数が部分関数(PartialFunction)らしい。

引数、とさらっと言ったけど、引数はカッコに囲まれていない。あっちゃダメなのかと思ったらそうでもないようだ。

scala> List(1,2,3,4,5).collect({ case i if i % 2 == 1 => i * 2 })
res1: List[Int] = List(2, 6, 10)

collect メソッドの動作はわかるんだけど、その引数が部分関数だといわれてもちょっとピンとこない。部分関数ってどうして部分?

もうちょっと厳密に言うと、引数に書いてあるブロック式自体は部分関数ではなくて、この式から部分関数が生成されるようだ。一般には case が複数あって、どれかのパターンにマッチしたときだけ新しい値がつくられてリストの要素になる。

てことは、こんなふうにも書けるわけだ。

scala> List(1,2,3,4,5).collect {
     |     case i if i % 2 == 0 => i * 2
     |     case i if i % 2 == 1 => i * i
     | }
res2: List[Int] = List(1, 4, 9, 8, 25)

うん、期待通りの動作はしてる。

でも、やっぱりなんで部分関数っていうんだかわからないなぁ。

カテゴリー: Scala | コメントする

ケースクラスによって自動生成されるもの

ケースクラス(case class )を宣言すると、ふつうのクラス(class)宣言に加えて、以下のものが追加で生成される。

  • プライマリコンストラクタ引数を公開する(クラス宣言の引数に val をつけたように動作する)
  • インスタンス同士の同値比較ができるように、equals()、hashCode()、canEqual()が定義される
  • 型とプライマリコンストラクタ引数を使った toString() が定義される
  • コンパニオンオブジェクトに apply() が定義される

ちょっと試してみよう。

scala> case class Point(x: Int, y: Int)
defined class Point

プライマリコンストラクタ引数が公開されるので、x や y フィールドにアクセスできる。

scala> val p1 = new Point(1, 3)
p1: Point = Point(1,3)

scala> p1.x
res0: Int = 1

scala> p1.y
res1: Int = 3

コンパニオンオブジェクトに apply() が定義されるので、new キーワードなしでインスタンスを生成できる。

scala> val p2 = Point(1, 3)
p2: Point = Point(1,3)

すでに上の実行例で出てきているけど、toString() で見やすい形で出力される。

scala> p1.toString()
res2: String = Point(1,3)

同値比較。

scala> p1.equals(p2)
res3: Boolean = true

ハッシュコード。これはオブジェクトごとに一意に決まるハッシュ値みたいなものかな。

scala> p1.hashCode()
res4: Int = -1062267453

scala> p2.hashCode()
res5: Int = -1062267453

別のオブジェクトでも同値だとハッシュコードも同じになるみたいだ。

hasEqual() は使い方がわからなかった。

カテゴリー: Scala | コメントする

変数宣言におけるパターンマッチング

パターンマッチングは match 式の中だけじゃなく、変数宣言においても使用できる。

例えばケースクラス Point があったとして

scala> case class Point(x: Int, y: Int)
defined class Point

こんなふうに変数宣言すると

scala> val Point(x, y) = Point(10, 20)
x: Int = 10
y: Int = 20

変数 x と y に値が束縛される。

scala> x
res0: Int = 10

scala> y
res1: Int = 20

ちなみに、パターンがマッチしない場合には例外が発生するので、変数宣言でのパターンマッチングは型が合うことが確実な場合にだけ使うように、と資料には書いてある。

カテゴリー: Scala | コメントする

ケースクラスとパターンマッチング(2)

パターンマッチングの威力は、昨日見たような型による分岐にとどまらない。というのも各パターンは(ケースクラスがパラメータを持つならば)パラメータを持つこともできるからだ。これでほぼ Haskell のパターンマッチングと同様のことができる。

例として、整数の四則演算を表す構文木を考えよう。各ノードは Exp を継承し(つまりすべては式である)、2項演算を表す部分木(2つの子を持つ)と整数リテラルを表す葉からなる。各クラスの定義はこうだ。

scala> sealed abstract class Exp
defined class Exp

scala> case class Add(lhs: Exp, rhs: Exp) extends Exp
defined class Add

scala> case class Sub(lhs: Exp, rhs: Exp) extends Exp
defined class Sub

scala> case class Mul(lhs: Exp, rhs: Exp) extends Exp
defined class Mul

scala> case class Div(lhs: Exp, rhs: Exp) extends Exp
defined class Div

scala> case class Lit(value: Int) extends Exp
defined class Lit

これを組み合わせて、(1 + ((2 * 3) / 2)) という式の構文木を作るとこうなる。

scala> val example = Add(Lit(1), Div(Mul(Lit(2), Lit(3)), Lit(2)))
example: Add = Add(Lit(1),Div(Mul(Lit(2),Lit(3)),Lit(2)))

さて、ここからが本番。この構文木を評価する評価器(メソッド)を作ろう。

scala> def eval(exp: Exp): Int = exp match {
     |     case Add(l, r) => eval(l) + eval(r)
     |     case Sub(l, r) => eval(l) - eval(r)
     |     case Mul(l, r) => eval(l) * eval(r)
     |     case Div(l, r) => eval(l) / eval(r)
     |     case Lit(v) => v
     | }
eval: (exp: Exp)Int

このパターンマッチングでは、

  1. ノードの種類と構造によって分岐し
  2. ネストしたノードを分解し
  3. 分解した結果を変数に束縛する

ということがいっぺんに行われている。もちろん束縛した変数は評価に使うことができる。

さて、それじゃ上の構文木 example を評価してみよう。

scala> eval(example)
res2: Int = 4

ちゃんと (1 + ((2 * 3) / 2)) の計算結果である 4 が得られた。

カテゴリー: Scala | コメントする

ケースクラスとパターンマッチング

ケースクラス(case class)は、Scala の強力なパターンマッチングのために必要なものらしい。普通のクラス(class)とどう違うのかよくわからないけど、パターンマッチングに使いたければケースクラスにしておけ、くらいに覚えておく(とりあえず)。

ケースクラスは次のように case キーワードをつけて宣言する。

scala> sealed abstract class DayOfWeek
defined class DayOfWeek

scala> case object Sunday extends DayOfWeek
defined object Sunday

scala> case object Monday extends DayOfWeek
defined object Monday

scala> case object Tuesday extends DayOfWeek
defined object Tuesday

scala> case object Wednesday extends DayOfWeek
defined object Wednesday

scala> case object Thursday extends DayOfWeek
defined object Thursday

scala> case object Friday extends DayOfWeek
defined object Friday

scala> case object Saturday extends DayOfWeek
defined object Saturday

クラスだと言っておきながらオブジェクト(object)なんだけど、どっちでもいいってことなんだろうか。ともかくこれらは次のようにパターンマッチングに使える。

scala> val x: DayOfWeek = Tuesday
x: DayOfWeek = Tuesday

scala> x match {
     |     case Sunday => 0
     |     case Monday => 1
     |     case Tuesday => 2
     |     case Wednesday => 3
     |     case Thursday => 4
     |     case Friday => 5
     | }
<console>:19: warning: match may not be exhaustive.
It would fail on the following inputs: Saturday
       x match {
       ^
res1: Int = 2

曜日を表すオブジェクトに対応する整数を返すコードだけど、今日(x)は火曜日なので 2 が返ってきている。

警告が出ているのは、マッチの分岐が完全じゃないかもしれないってこと。実際 Saturday が抜けている。これは、スーパークラス/トレイトの宣言に sealed 修飾子をつけるとその(直接の)サブクラス/トレイト(オブジェクトも?)は同じファイル内にしか宣言できない、という性質を利用して実現されている。

sealed 修飾子はこの用途以外ではめったに使われないので、ケースクラスのスーパークラス/トレイトには sealed をつけておくものだと覚えておこう。

パターンマッチングはもっと強力なんだけど、今日のところはこのへんで。

カテゴリー: Scala | コメントする