Scalaで入門関数プログラミング

WEB+DB Press vol.67 の入門関数プログラミング、をScalaでやってみました。特に赤黒木の実装が勉強になりました。



記事ではHaskellがターゲットですが、Scalaでもやってみました。淡々とscalaコンソールのログを貼り付けます。解説は書籍を参照。
実際やってみると、Haskellほどきれいに書けず悩むところもありましたが、なるべく翻訳するような感じでやってみました。

第2章

mul関数で、mapに渡すPartialFunctionを意識しなければならないところがちょっとScala臭い感じ。あとは無限配列Stream。

>scala
Welcome to Scala version 2.8.1.final (Java HotSpot(TM) Client VM, Java 1.6.0_30).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val nums = (10 to 50 by 10)
nums: scala.collection.immutable.Range = Range(10, 20, 30, 40, 50)

scala> val zips = Stream.from(0) zip nums toList
zips: List[(Int, Int)] = List((0,10), (1,20), (2,30), (3,40), (4,50))

scala> val mul: ((Int,Int)) => Int = { case (a,b) => a*b }
mul: ((Int, Int)) => Int = <function1>

scala> val mulzips = zips map mul toList
mulzips: List[Int] = List(0, 20, 60, 120, 200)

scala> mulzips.foldLeft(0){ (sum,n) => sum + n }
res0: Int = 400

scala> ( 0 /: mulzips )(_+_)
res1: Int = 400

scala> val calc : (Seq[Int]) => Int =
     |     (xs) => ( (Stream.from(0) zip xs) map mul ).foldLeft(0)(_+_)
calc: (Seq[Int]) => Int = <function1>

scala> calc(nums)
res2: Int = 400

第3章

PartialFunction.andThenを使った関数合成

scala> val makeString : (Char) => (Int) => String =
     |     (c) => (n) => n match {
     |       case 0 => ""
     |       case _ => c + makeString(c)(n-1)
     |     }
makeString: (Char) => (Int) => String = <function1>

scala> makeString('w')(10)
res3: String = wwwwwwwwww

scala> val tails : (String) => List[String] =
     |     (s) => s.toList match {
     |       case h::ts => (h::ts).mkString :: tails( ts.mkString )
     |       case Nil => List("")
     |     }
tails: (String) => List[String] = <function1>

scala> val sort = (list:List[String]) => list.sorted
sort: (List[String]) => List[String] = <function1>

scala> ( tails andThen sort )( "banana" )
res4: List[String] = List(, a, ana, anana, banana, na, nana)

scala> val makePair = (xs:Seq[String]) => xs.zip(xs.tail)
makePair: (Seq[String]) => Seq[(String, String)] = <function1>

scala> makePair(List("boo","foo","woo"))
res5: Seq[(String, String)] = List((boo,foo), (foo,woo))

scala> val pairEq : ((Char,Char)) => Boolean = { case (x,y) => x == y }
pairEq: ((Char, Char)) => Boolean = <function1>

scala> "world" zip "word"
res6: scala.collection.immutable.IndexedSeq[(Char, Char)] = Vector((w,w), (o,o), (r,r), (l,d))

scala> "word" zip "world" takeWhile pairEq
res7: scala.collection.immutable.IndexedSeq[(Char, Char)] = Vector((w,w), (o,o), (r,r))

scala> val comlen = (xs:String,ys:String) => xs zip ys takeWhile pairEq length
comlen: (String, String) => Int = <function2>

scala> comlen("word","world")
res8: Int = 3

scala> val lenstr = (xs:String,ys:String) => (comlen(xs,ys),xs)
lenstr: (String, String) => (Int, String) = <function2>

scala> lenstr("word","world")
res9: (Int, String) = (3,word)

scala> val calcLen  = (pairs: Seq[(String,String)]) => pairs.map{ case (p,q) => lenstr(p,q) }
calcLen: (Seq[(String, String)]) => Seq[(Int, String)] = <function1>

scala> val chooseMax = (list:Seq[(Int,String)]) => list.sortBy(_._1).last
chooseMax: (Seq[(Int, String)]) => (Int, String) = <function1>

scala> chooseMax( Seq( (1,"boo"),(3,"foo"),(2,"woo") ) )
res10: (Int, String) = (3,foo)

scala> val extract : ((Int,String)) => String = { case (n,s) => s.take(n) }
extract: ((Int, String)) => String = <function1>

scala> extract(3,"boofoo")
res11: String = boo

scala> val maxDupStr = tails andThen sort andThen makePair andThen calcLen andThen chooseMax andThen extract
maxDupStr: (String) => String = <function1>

scala> maxDupStr("mississippi")
res12: String = issi

第4章 赤黒木の実装

今日はコレをやってみたかったんでした。
自分はこういったアルゴリズムやサイエンス的なものは避けて通ってきた方なのですが、アラフォーを向かえて「もうちょっとトライしとけばよかった><」と思い始めているのは、Scalaを触っている効果です。


object Color extends Enumeration {
  val Red, Black = Value
}

class RBTree[ K <% Ordered[K], V ] {
  import Color._

  trait Hash[K,V]
  case class Leaf() extends Hash[K,V]
  case class Node[K,V](color:Color.Value, left:Hash[K,V], kv:(K,V), right:Hash[K,V] ) extends Hash[K,V]
  
  def empty:Hash[K,V] = Leaf()
  
  def insert( kv:(K,V), t:Hash[K,V] ) : Hash[K,V] =
    turnB( _insert( kv._1, kv._2, t ) )
  
  def fromList( kvs:Seq[(K,V)] ) :  Hash[K,V] =
    kvs.foldLeft(empty){ (node,kv) => insert(kv,node) }
  
  def search( k:K, tree:Hash[K,V] ) : Option[V] = (k,tree) match {
    case (kx, leaf:Leaf) => None
    case (kx, Node(c,l, (k,v), r) ) =>
      if( kx < k ) search(kx,l)
      else if( kx > k ) search(kx,r)
      else Some(v)
  }

  private def _insert( k:K, v:V, t:Hash[K,V] ) : Hash[K,V] =
    (k,v,t) match {
      case (kx,vx, leaf:Leaf) =>
        Node(Red,leaf,(kx,vx),leaf)
      case (kx,vx, Node(c,l,(k,v),r) ) =>
        if( kx < k )
          balance(c,_insert(kx,vx,l),(k,v),r )
        else if( kx > k )
          balance(c,l,(k,v),_insert(kx,vx,r))
        else
          Node(c,l,(k,v),r)
    }
  private def balance( color:Color.Value, left:Hash[K,V], kv:(K,V), right:Hash[K,V] ) :Hash[K,V] =
    (color,left,kv,right) match {
      case (Black,Node(Red,Node(Red,a,x,b),y,c),z,d) =>
        Node(Red,Node(Black,a,x,b),y,Node(Black,c,z,d) )
      case (Black,Node(Red,a,x,Node(Red,b,y,c)),z,d) =>
        Node(Red,Node(Black,a,x,b),y,Node(Black,c,z,d) )
      case (Black,a,x,Node(Red,b,y,Node(Red,c,z,d))) =>
        Node(Red,Node(Black,a,x,b),y,Node(Black,c,z,d) )
      case (Black,a,x,Node(Red,Node(Red,b,y,c),z,d)) =>
        Node(Red,Node(Black,a,x,b),y,Node(Black,c,z,d) )
      case _ =>
        Node(color,left,kv,right)
    }
  
  private def turnB( h:Hash[K,V] ) = h match {
    case Node(_,l,kv,r) => Node(Black,l,kv,r)
    case h => h
  }
}

scalaコンソールに上記のobject/classをloadして(コピペでOK)簡単に仕様確認。


scala>  object StringTree extends RBTree[Int,String]
defined module StringTree

scala> import StringTree._
import StringTree._

scala> insert( (1,"a"), empty)
res10: StringTree.Hash[Int,String] = Node(Black,Leaf(),(1,a),Leaf())

scala> insert( (2,"b"), insert( (1,"a"), empty) )
res11: StringTree.Hash[Int,String] = Node(Black,Leaf(),(1,a),Node(Red,Leaf(),(2,b),Leaf()))

scala> val hash = fromList( Seq((1,"a"),(2,"b")) )
hash: StringTree.Hash[Int,String] = Node(Black,Leaf(),(1,a),Node(Red,Leaf(),(2,b),Leaf()))

scala> search( 1, hash )
res12: Option[String] = Some(a)

scala> search( 3, hash )
res13: Option[String] = None

scala本体でもTreeMapなどに赤黒木が実装されていて、ソースはscala.collection.immutable.RedBlackにあります。

一回自分で書いてみるとこういうソースも読めるようになるもんですね。関数型言語は理屈がそのままコードになるので、アルゴリズムの本質的な箇所だけに注力できるで勉強しやすいことを実感しました。やってみるもんだ。

第5章のCSVパーサは、「scala csv parser combinator」とかでコードスニペットいっぱい出てくるので割愛。
HaskellがわからなくてWEB+DBの記事が読みにくい人には「ふつうのHaskellプログラミング」お勧め。これ一読してからScalaに戻ると、また一段とScalaがわかりやすくなります(自分がそうでした)。



同じカテゴリのエントリ
1.Lift再入門 / 8.javascriptからsubmitできない / 7.Ajax Form / 6.Radio、Checkboxについて / 5.行列型の編集FORM / 4.サーバーサイドバリデーションとサーバサイド関数 / 3.ログインFORM - S.param使ったら負け / 2.Snippetメソッドとして許される型 / sbt0.12.xで依存jar抽出タスク / scala2.10+lift2.5+NetBeans7.2 / Scalaで入門関数プログラミング / reactive-webを試してみました / Lift2.2M1のテンプレート機能 / Scala Compiler Plugin / View Bound/Context Bound / ScalaZa01参加してきました / Akka Frameworkチュートリアルの次 / Akka Frameworkチュートリアルその2 / Akka Frameworkチュートリアル / LiftでJCaptcha / Url Rewrite Filter / sbt-android-plugin / Android SDK for Scala / 祝Lift2.0リリース / Liftの携帯対応まとめ / Scala2.8への移行 / Lift 2.0-scala280-SNAPSHOT/sbt0.7.1 / Scalaお絵かき環境 - Kojo / Lift+Quartzでバッチ / Scala&Liftを採用した理由 / Liftでdate_select系ヘルパーを作る / LiftでAjax / LiftのSubmitかしこい / lift-mapperのpaginateを使う / snippetをspecする / Lift Mapperを拡張する / LiftのDBをMySQLに / Liftプロジェクト環境を整える / Scala本読み比べてみました / NetBeans6.7&scala / じつはScalaはライトな言語 / Scalaバザ~ル / lift1.0所感 / specsを読む / implicit def / ScalaならNetBeansがサイコー / scala勉強会@東北がスタート / それでも俺はLiftをやるってのか / Scala&Liftセットアップ / ブログリニューアル /
コメント

コメントしてください

closed.