2012年6月27日水曜日

Stateもなど

Stateモナドの有用性を考えるために書いてみます。

case class Range(node: Node, offset: Int)
def getRange = IO(Range(<p>{ Random.nextString(5) }</p>, Random.nextInt(5)))
def nextNode(node: Node) = IO(<p>{ Random.nextString(5) }</p>)
def prevNode(node: Node) = IO(<p>{ Random.nextString(5) }</p>)
def move(range: Range) = IO(())
view raw dom.scala hosted with ❤ by GitHub

Rangeオブジェクトはカーソルが指すNodeとoffsetを持っています。
getRangeは現在のRangeを返すものとします。
moveはそのRangeにカーソル移動するものとします。
nextNodeとprevNodeはそれぞれ次のNodeと前のNodeを返します。

getRange,nextNode,prevNode,moveは擬似的なものなので、定義は気にしないで下さい。
この4つの関数は参照透過とかそんなわけないのでIOを返します。

これらに対して、4方向にカーソルを動かす関数を定義します。

def moveLeft = for {
r <- getRange
} yield move(r.copy(offset = r.offset.pred))
def moveRight = for {
r <- getRange
} yield move(r.copy(offset = r.offset.succ))
def moveUp = for {
r <- getRange
n <- prevNode(r.node)
} yield move(r.copy(node = n))
def moveDown = for {
r <- getRange
n <- nextNode(r.node)
} yield move(r.copy(node = n))
view raw move1.scala hosted with ❤ by GitHub

IOはモナドなのでforが使えます。
predとsuccはscalaz.Enumのシンタックスでデクリメントとインクリメントのようなものです。

実際には移動するときに、offsetなどを調べるものですが、OptionT[IO, Unit]などと複雑になるので省略します。
これらの関数を組み合わせてみます。

def movemovemove = moveLeft >> moveRight >> moveUp >> moveDown
view raw comp1.scala hosted with ❤ by GitHub

さて、これらの関数、ちょっと冗長ですね。
いちいちmoveを実行しているところもいただけません。

これらをStateを使って書きなおしてみます。

def moveLeft = State[Range, Range](r => r.copy(offset = r.offset.pred).squared)
def moveRight = State[Range, Range](r => r.copy(offset = r.offset.succ).squared)
def moveUp = StateT[IO, Range, Range](r => prevNode(r.node) map (n => r.copy(node = n).squared))
def moveDown = StateT[IO, Range, Range](r => nextNode(r.node) map (n => r.copy(node = n).squared))
view raw move2.scala hosted with ❤ by GitHub

squaredは値をペアにして返します。

同じように、合成したStateとそれを使って移動する関数を定義します。

def movemovemove = for {
_ <- moveLeft.lift[IO]
_ <- moveRight.lift[IO]
_ <- moveUp
r <- moveDown
} yield r
def run = getRange >>= movemovemove.eval >>= move
view raw comp2.scala hosted with ❤ by GitHub

getRangeとmoveの呼び出しは1回で済むようになりました。
movemovemoveというStateを使い回すことも出来ます。

さらに、Stateモナドであることを活かして、次のようなStateを定義することが出来ます。

def moveDownStart = for {
r <- moveDown
rr <- List.fill(r.offset)(moveLeft).foldRight(State.init[Range])(_ >> _).lift[IO]
} yield rr
view raw state.scala hosted with ❤ by GitHub

移動した直後の状態を扱えるのがStateモナドの利点ですね。



最近は大学生がなかなか忙しいです。
俺、定期試験が終わったらScalaz勉強会開くんだ・・・・・

2012年6月23日土曜日

Pythonの復習

最近Pythonさわってなかったので。

FizzBuzz


def fizzbuzz(n):
if n % 15 == 0:
return "FizzBuzz"
elif n % 3 == 0:
return "Fizz"
elif n % 5 == 0:
return "Buzz"
else:
return n
view raw fizzbuzz1.py hosted with ❤ by GitHub

なんのへんてつもないコード。

yield使って、generatorにしてみる。

def fizzbuzz_iter():
n = 1
while True:
yield fizzbuzz(n)
n += 1
view raw fizzbuzz2.py hosted with ❤ by GitHub

このケースならitertoolsを使ったほうがカッコイイ。

import itertools
def fizzbuzz_iter():
return map(fizzbuzz, itertools.count(1))
view raw fizzbuzz3.py hosted with ❤ by GitHub

countはnからstep(デフォルトは1)づつ増えていくgeneratorを作る関数です。
mapはいつの間にかイテレータに対応してくれてました。

素数


判定を書く

import functools
import operator
def isprime(n):
return all(map(functools.partial(operator.mod, n), range(2, n - 1)))
view raw prime1.py hosted with ❤ by GitHub

functoolsとoperatorで関数型っぽく書けて素敵ですね。
functools.partialは部分適用、operator.modは剰余です。

素数列を作る

def primes():
return filter(isprime, itertools.count(2))
view raw prime2.py hosted with ❤ by GitHub

なかなかいい感じ。

フィボナッチ数列


n番目のフィボナッチ数を返す関数

def fibonacci(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibonacci(n - 2) + fibonacci(n - 1)
view raw fibonacci1.py hosted with ❤ by GitHub

dict使って分岐する

def fibonacci(n):
return {0: lambda: 1, 1: lambda: 1}.get(n, lambda: fibonacci(n - 2) + fibonacci(n - 1))()
view raw fibonacci2.py hosted with ❤ by GitHub

switch的なものはdictで代用できるのでもーまんたいですね。
getの第二引数はキーが存在しない場合返ります。

イテレータ版

def fibonacci_iter():
return map(fibonacci, itertools.count(1))
view raw fibonacci3.py hosted with ❤ by GitHub

Pythonはなかなか関数型言語ちっくに書けて素敵ですね。
Rから始まる4文字のプログラミング言語より関数型っぽいです。

2012年6月10日日曜日

Proof with Scala

※今回はScala2.10.0-M3を使います。

ある型クラスのインスタンスを定義するとき、何らかの規則を満たす必要があるときがあります。

例えばMonadだとモナド則。
bind,returnを定義するときに、以下のものが満たされないといけません。

bind (return a) f = f a
bind m return = m
bind (bind m f) g = bind m (fun x => bind (f x) g)

しかし、Scalazの型クラスなどはモナド則を満たしているかどうかを検査してくれるわけではありません。

そこで、コンパイル時に規則を満たしているかどうかを検査するように型クラスを定義してみます。

Monoidを例に考えます。

trait Monoid[M] {
type Zero <: M
type Append[A <: M, B <: M] <: M
def zero: Zero
def append[A <: M, B <: M](a1: A, a2: B): Append[A, B]
}
view raw monoid1.scala hosted with ❤ by GitHub

ScalazのMonoidの定義と違うところは、ある型のサブクラスも許容しているところです。

Monoidは以下のものを満たす必要があります。

append zero a = a
append a zero = a
append a (append b c) = append (append a b) c

これをScalaで記述すると

trait Monoid[M] extends MonoidLow[M] {
type Zero <: M
type Append[A <: M, B <: M] <: M
def zero: Zero
def append[A <: M, B <: M](a1: A, a2: B): Append[A, B]
}
trait MonoidLow[M] { self: Monoid[M] =>
def leftIdentity[A <: M](a: Append[Zero, A]): A
def rightIdentity[A <: M](a: Append[A, Zero]): A
def associativity[A <: M, B <: M, C <: M](a: Append[A, Append[B, C]]): Append[Append[A, B], C]
}
view raw monoid2.scala hosted with ❤ by GitHub

となります。

型が命題でプログラムが証明になります。
つまり、leftIdentity,rightIdentity,associativityを定義出来れば証明できたことになります。
カリー=ハワード同型対応!

自然数を定義します。

sealed trait Nat {
type +[N <: Nat] <: Nat
def +[N <: Nat](n: N): +[N]
}
sealed trait _0 extends Nat {
type +[N <: Nat] = N
def +[N <: Nat](n: N) = n
}
case object _0 extends _0
case class S[N <: Nat](n: N) extends Nat {
type +[M <: Nat] = S[N# + [M]]
def +[M <: Nat](m: M) = S(n + m)
}
view raw monoid3.scala hosted with ❤ by GitHub

自然数をMonoidのインスタンスにします。

object NatInstance extends Monoid[Nat] {
type Zero = _0
type Append[A <: Nat, B <: Nat] = A# + [B]
def zero = _0
def append[A <: Nat, B <: Nat](a: A, b: B) = a + b
def leftIdentity[A <: Nat](a: Append[Zero, A]) = a
implicit def rightIdentity[A <: Nat](a: Append[A, Zero]) = a
implicit def associativity[A <: Nat, B <: Nat, C <: Nat](a: Append[A, Append[B, C]]) = a
}
view raw monoid4.scala hosted with ❤ by GitHub

コンパイル通ったー!

通らない例を作ってみましょう。

正の整数を定義して、Monoidのインスタンスを考えてみます。

sealed trait Pos {
type +[P <: Pos] <: Pos
def +[P <: Pos](p: P): +[P]
}
sealed trait _1 extends Pos {
type +[P <: Pos] = S[P]
def +[P <: Pos](p: P) = S(p)
}
case object _1 extends _1
case class S[P <: Pos](p: P) extends Pos {
type +[Q <: Pos] = S[P# + [Q]]
def +[Q <: Pos](q: Q) = S(p + q)
}
object PosInstance extends Monoid[Pos] {
type Zero = _1
type Append[A <: Pos, B <: Pos] = A# + [B]
def zero = _1
def append[A <: Pos, B <: Pos](a: A, b: B) = a + b
def leftIdentity[A <: Pos](a: Append[Zero, A]) = a
implicit def rightIdentity[A <: Pos](a: Append[A, Zero]) = a
implicit def associativity[A <: Pos, B <: Pos, C <: Pos](a: Append[A, Append[B, C]]) = a
}
view raw monoid5.scala hosted with ❤ by GitHub

この定義では当然コンパイルは通りませんね。

コンパイルが通るように定義することも多分できないと思われます。(asInstanceOfは使っちゃダメですよ。)

これらのコードを書いてる中で疑問が現れました。
NatInstanceのrightIdentityとassociativityです。
このコード、コンパイルは通らないと思っていたのですが、implicitを付けると通りました。
・・・・・なぜ?

2012年6月5日火曜日

わたしのScalazプログラミングその2

型クラスについて。

例によって有理数で。

case class Rational(n: Int, d: Int)
view raw rational1.scala hosted with ❤ by GitHub

Groupのインスタンスを定義します。
Groupとは、結合演算子、単位元、逆元を持つもののことです。

trait RationalInstances {
implicit object rationalInstance extends Group[Rational] {
def zero = Rational(0, 1)
def inverse(r: Rational) = Rational(-r.n, r.d)
def append(r1: Rational, r2: => Rational) =
Rational(r1.n * r2.d + r2.n * r1.d, r1.d * r2.d)
}
}
object Rational extends RationalInstances
view raw rational2.scala hosted with ❤ by GitHub

動かしてみる。

scala> import scalaz._, Scalaz._
import scalaz._
import Scalaz._
scala> Rational(1, 2) |+| Rational(2, 3)
res0: Rational = Rational(7,6)
scala> Rational(1, 2) |-| Rational(2, 3)
res1: Rational = Rational(-1,6)
scala> Rational(1, 2) multiply 2
res2: Rational = Rational(4,4)
scala> -Rational(1, 2)
res3: Rational = Rational(-1,2)
view raw repl1.scala hosted with ❤ by GitHub

Groupのインスタンスを定義するだけでこれだけのことができます。

自分でデータ型を定義するときは、インスタンス自体に関数を定義より、データ型にメソッドとして定義したほうがいいかもしれません。
また、Groupのインスタンスからメソッドが定義できます。

case class Rational(n: Int, d: Int) {
def +(r: Rational) =
Rational(n * r.d + r.n * d, d * r.d)
def -(r: Rational) =
Rational.rationalInstance.minus(this, r)
def unary_- = Rational(-n, d)
}
trait RationalInstances { self: Rational.type =>
implicit object rationalInstance extends Group[Rational] {
def zero = Rational(0, 1)
def inverse(r: Rational) = -r
def append(r1: Rational, r2: => Rational) = r1 + r2
}
}
object Rational extends RationalInstances
view raw rational4.scala hosted with ❤ by GitHub

scala> Rational(1, 2) + Rational(2, 3)
res0: Rational = Rational(7,6)
scala> Rational(1, 2) - Rational(2, 3)
res1: Rational = Rational(-1,6)
view raw repl2.scala hosted with ❤ by GitHub

乗算、除算も定義してみます。

import scalaz._, Scalaz._, Tags._
case class Rational(n: Int, d: Int) {
def +(r: Rational) =
Rational(n * r.d + r.n * d, d * r.d)
def -(r: Rational) =
Rational.rationalInstance.minus(this, r)
def *(r: Rational) =
Rational(n * r.n, r.d * d)
def /(r: Rational): Rational =
Rational.rationalMultiplicationInstance.minus(Tag(this), Tag(r))
def unary_- = Rational(-n, d)
def unary_~ = Rational(d, n)
}
trait RationalInstances { self: Rational.type =>
implicit object rationalInstance extends Group[Rational] {
def zero = Rational(0, 1)
def inverse(r: Rational) = -r
def append(r1: Rational, r2: => Rational) = r1 + r2
}
implicit object rationalMultiplicationInstance extends Group[Rational @@ Multiplication] {
def zero = Tag(Rational(1, 1))
def inverse(r: Rational @@ Multiplication) = Tag(~r)
def append(r1: Rational @@ Multiplication, r2: => Rational @@ Multiplication) =
Tag(r1 * r2)
}
}
object Rational extends RationalInstances
view raw rational5.scala hosted with ❤ by GitHub

scala> import scalaz._, Scalaz._, Tags._
import scalaz._
import Scalaz._
scala> Rational(1, 2) * Rational(2, 3)
res0: Rational = Rational(2,6)
scala> Rational(1, 2) / Rational(2, 3)
res1: Rational = Rational(3,4)
scala> Foldable[List].fold(List(Rational(1, 2), Rational(2, 3)))
res2: Rational = Rational(7,6)
scala> Foldable[List].fold(List(Tag[Rational, Multiplication](Rational(1, 2)), Tag[Rational, Multiplication](Rational(2, 3))))
res3: scalaz.package.@@[Rational,scalaz.Tags.Multiplication] = Rational(2, 6)
view raw repl3.scala hosted with ❤ by GitHub

べんり!

2012年6月2日土曜日

わたしのScalazプログラミング

Scalaはオブジェクト指向言語なのですよ。
知ってました?

重要:これから書くコードはとてもメニアックなので参考にしないようにして下さい。

今日は有理数を定義してみます。


case class Rational(n: Int, d: Int)
view raw rational1.scala hosted with ❤ by GitHub

加算と減算を追加してみる。

case class Rational(n: Int, d: Int) {
def +(r: Rational) = Rational(n * r.d + r.n * d, d * r.d)
def -(r: Rational) = Rational(n * r.d - r.n * d, d * r.d)
}
view raw rational2.scala hosted with ❤ by GitHub

さて、この2つのメソッド、とても似ていますよね。
抽象化してしまいます。

case class Rational(n: Int, d: Int) {
def op(f: (Int, Int) => Int)(r: Rational) =
Rational(f(n * r.d, r.n * d), d * r.d)
lazy val + = op(_ + _)_
lazy val - = op(_ - _)_
}
view raw rational3.scala hosted with ❤ by GitHub

さて、今日の本題はここからです。
この加算と減算を他の数値型に対応させたいとします。
普通はこのようにオーバーロードを使いますよね。

case class Rational(n: Int, d: Int) {
def +(r: Rational) = Rational(n * r.d + r.n * d, d * r.d)
def +(i: Int) = Rational(n + i * d, i * d)
}
view raw rational4.scala hosted with ❤ by GitHub

しかし、+や-はメソッド型ではなく、値型なのでオーバーロードは使用できません。
そこで、オーバーロードを使わず、UnionTypesを使って定義します。

case class Rational(n: Int, d: Int) {
def +[A](a: A)(implicit ev: A ∈ t[Rational]#t[Int]) =
a match {
case Rational(nn: Int, dd: Int) => Rational(n * dd + nn * d, d * dd)
case i: Int => Rational(n + i * d, i * d)
}
}
view raw rational5.scala hosted with ❤ by GitHub

これでもまだ問題があります。
Scalaでは、型パラメータをとる関数を値として定義できません。
そこで、関数のようにふるまう型を自分で定義します。

case class Rational(n: Int, d: Int) {
case class Function(f: (Int, Int) => Int) {
def apply[A](a: A)(implicit ev: A ∈ t[Rational]#t[Int]) = a match {
case Rational(nn: Int, dd: Int) => Rational(f(n * dd, nn * d), d * dd)
case i: Int => Rational(f(n, i * d), i * d)
}
}
lazy val + = Function(_ + _)
lazy val - = Function(_ - _)
}
view raw rational6.scala hosted with ❤ by GitHub

これで+と-の演算を抽象化し、さらに多相に対応しましたね。
めでたしめでたし。

2012年6月1日金曜日

Scalaz7でIterateeとIO

いつものようにTwitterでScalazを検索すると


この様なつぶやきが。

コードはこんな感じ。

import java.io.{ BufferedReader, FileReader }
import scalaz._, Scalaz._
import scalaz.effects._
import IterV._
object App {
def main(args: Array[String]) {
val br = new BufferedReader(new FileReader("test2.txt"))
val io = byEnumerator(br)
io.unsafePerformIO
}
def byEnumerator(br: BufferedReader): IO[Unit] = {
val lineIter: IterV[String, Int] = head[String] map {
lineOpt => (lineOpt map (_.length)) | 0
}
val iter: IterV[String, Stream[Int]] = repeat[String, Int, Stream](lineIter)
val enumerator: EnumeratorM[IO, String] = getReaderLines(br)
val read: IO[Int] = enumerator(iter) map { iter =>
iter.run reduce (_ + _)
}
read map (_.toString) flatMap (putStrLn _)
}
}
view raw App.scala hosted with ❤ by GitHub

fmfm.
先頭行をとって長さをとって行数分ぬりつぶして合計をとっているようですね。

このコードはScalaz6なのですが、Scalaz7でも書けるかなーと思い、ちょっと書いてみました。

import java.io.{ Reader, FileReader }
import scalaz._, Scalaz._
import effect._, IO._
import iteratee._, Iteratee._
object App extends SafeApp{
val separator = sys.props("line.separator").head
override def run(args: ImmutableArray[String]): IO[Unit] = {
val r = new FileReader("test2.txt")
byEnumerator(r)
}
type IEOC = IoExceptionOr[Char]
def byEnumerator(r: Reader): IO[Unit] = {
val lineIter = takeWhile[IEOC, Stream](_ map (_ =/= separator) valueOr false) map (_.length)
val iter = repeatBuild[IEOC, Int, Stream](lineIter).up[IO] map (_.sum)
val enum = enumReader(r)
val read = iter &= enum
(read.run >>= putOut) >> putStrLn("")
}
}
view raw App.scala hosted with ❤ by GitHub

違いを1つ1つみていきます。

まず、Scalaz7ではgetReaderLinesがないので、BufferedReaderではなくReaderを使うようにしました。
なので、1行ずつではなく1文字ずつしかみれなくなります。
そこで、改行コードをみるようにします。
改行コードはシステムプロパティーのline.separatorで取得できるとのことなので、sys.propsから取得します。

もとのコードでは、先頭行を取得する為にheadを使っていますが、このコードではtakeWhileを使います。
ここでは、述語として改行コードかどうかの判定をとります。

さて、肝心のIterateeの要素ですが、IoExceptionOr[Char]となっています。
これはその名の通り、IoExceptionとの和で、どちらかが内包されています。
ここではvalueOrを使い、IoExceptionだった場合の値を決め、値を取得しています。

repeatBuildはScalaz6のscalaz.IterV.repeatと同じです。
on[IO]は、Iteratee[E, A]から、IterateeT[E, IO, A]に変換しています。

enumReaderはReaderからEnumeratorを作り、&=はEnumeratorをIterateeに流し込みます。

最後に実行の部分ですが、mainを定義しているわけではありません。
SafeAppはunsafePerformIOを明示的に呼び出さない仕組みで、runをオーバーライドすることで実行できます。

・・・・・とまあこんな感じなのですが、Scalaz6と比べて、かなり違うことが分かりますね。
とくにIteratee。
IterVとIterateeで別々のものになっていましたが、いまはIterateeTのみで大分使いやすくなった気がします。(Iteratee[E, A]はIteratee[E, Id, A]の別名)
ただ、enumReaderLinesのようなものは欲しかった。

IOはMonadIOとかMonadControlIOとかいろいろ高機能になっているのですが、基本的な機能が少ないので、相変わらず残念です。
せめてSourceとReaderとWriterのインスタンスくらい作ってくれればいいのに。
あと入出力系。

超便利とまでは言えないけれど、将来性はありそうなiterateeとeffect。
一度さわってみてはどうでしょう?