リスト処理 - Life Goes On

関数型言語のいいところは、何といっても高階関数と遅延評価だと思うのです。
というわけで、Scala の高階関数（リスト処理）を見てみました。
まずぱっと思ったのが、zipWith と scanLeft が欲しいということ。
zip → map とするよりは zipWith 一発で書きたいというのと、foldLeft があるのに scanLeft が無いのは片手落ちな気がするからです。
最初に書いた zipWith はこんな感じ。

def zipWith[A,B,C](f:A=>B=>C)(xs:List[A])(ys:List[B]):List[C] = (xs,ys) match {
 case (x::xs1,y::ys1) => f(x)(y) :: zipWith(f)(xs1)(ys1)
 case (_,_) => Nil
}

いちおう動きます。

scala> zipWith ((x:Int)=>((y:Int)=>x+y)) ((0 to 4) toList) ((3 to 100) toList)
res0: List[Int] = List(3, 5, 7, 9, 11)

でも、Scala なんだから zipWith(f)(xs)(ys) ではなくて、xs.zipWith(f)(ys) と書きたい。
あと f は極力簡単に書きたいので、カリー化しない方がいい。
と言うわけで書き直しました。
List クラスは sealed なので、別の MyList クラスを作って Implicit Conversion させました。
ふつうはどうするもんなんだろう。

class MyList[A](xs:List[A]) {

 def zipWith[B,C](f:(A,B)=>C)(ys:List[B]):List[C] = (xs,ys) match {
   case (x::xs1,y::ys1) => f(x,y) :: new MyList(xs1).zipWith(f)(ys1)
   case (_,_) => Nil
 }

 def scanLeft[B](f:(B,A)=>B)(z:B):List[B] = z :: (xs match {
   case (x::xs1) => new MyList(xs1).scanLeft(f)(f(z,x))
   case _ => Nil
 })
}
implicit def list2MyList[A](xs:List[A]):MyList[A] = new MyList(xs)

さっきより Scala らしくなった気がする。引数が複数あると、メソッド呼出の"."を省略できないみたい。
あと無名関数の ":Int" がうっとうしいな。これは書き方次第で消せそうなんだけど。

scala> (0 to 4).toList.zipWith((_:Int).toString+(_:Int).toString)((5 to 9).toList)
res1: List[java.lang.String] = List(05, 16, 27, 38, 49)

scala> (1 to 10).toList.scanLeft((_:Int)*(_:Int))(1)
res1: List[Int] = List(1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800)

これでフィボナッチをと思ったのですが、無限リストのためのクラスは別なので、改めて定義しないといけない。
実装上難しいのだろうけど、やっぱり一つにしてほしいなあ。
書き方は List のときと同じ。ストリームの終端に来たときの処理は省略。ついでに iterate も定義しておこう。

class MyStream[A](xs:Stream[A]) {

 def zipWith[B,C](f:(A,B)=>C)(ys:Stream[B]):Stream[C] =
   Stream.cons(f(xs.head,ys.head), new MyStream(xs.tail).zipWith(f)(ys.tail))

 def scanLeft[B](f:(B,A)=>B)(z:B):Stream[B] =
   Stream.cons(z, new MyStream(xs.tail).scanLeft(f)(f(z,xs.head)))
}
implicit def stream2MyStream[A](xs:Stream[A]):MyStream[A] = new MyStream(xs)

def iterate[A](f:A=>A)(x:A):Stream[A] = Stream.cons(x, iterate(f)(f(x)))

これを使って、フィボナッチを定義。せっかくなので３種類。

lazy val fib1: Stream[Int] = Stream.cons(0,
  Stream.cons(1, fib1.zipWith((_:Int)+(_:Int))(fib1.tail)))

lazy val fib2: Stream[Int] = Stream.cons(0, fib2.scanLeft((_:Int)+(_:Int))(1))

lazy val fib3: Stream[Int] = iterate((x:(Int,Int))=>(x._2,x._1+x._2))(0,1).map(_._1)

めでたく動きました。

scala> fib1.take(10).toList
res3: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

scala> fib2.take(10).toList
res4: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

scala> fib3.take(10).toList
res5: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

けつろん。
zipWith はあまり意味がありませんでした。zip と map でいいと思います。
scanLeft はけっこう使えそう。unfold とかは必要に迫られたら書こう。
やっぱり関数をあれこれ弄くりまわすのには向いてないので、無理に関数型っぽく書こうとするよりは、オブジェクト指向で書いた方が、すっきりしたコードになる気がします。