読者です 読者をやめる 読者になる 読者になる

ScalaでBinary Tree

scala

Scalaを始めてみました。

実のところOOPとFPの融合という点で「使いこなせないのではなかろうか?」という不安が結構あったので、ちょっと消極的だったのですが、色々な人に「仕事でJava、趣味でOCaml?じゃあScalaでしょう」と言われる機会があり、やってみようかなぁと。

しかしこのご時世、たとえ素人の手慰み的な趣味であっても「OCamlやってます」等というと、即フルボッコにされそうなので気をつけないといけませんね。

で、試しにScalaの仕様がよく解っていないまま(とくにTraitとか解らん)、何か書いてみようかと思い二分木でも書いてみました。

sealed abstract class Tree

case class Br(x:Int, left:Tree, right:Tree) extends Tree
case class Lf() extends Tree

object TreeSample {
  def listToTree(xs:List[Int], t:Tree):Tree =
    xs match {
      case Nil => t
      case hd::tl =>
        def createTree(x:Int, t:Tree):Tree = {
          t match {
            case Lf() =>
              Br(x=hd, left=Lf(), right=Lf())
            case Br(x, l, r) =>
              if (hd < x) Br(x, createTree(hd, l), r)
              else        Br(x, l, createTree(hd, r))
          }
        }
        listToTree(tl, createTree(hd, t))
    }

  def treeToList(t:Tree, xs:List[Int]):List[Int] =
    t match {
      case Lf() => xs
      case Br(x, l, r) => treeToList(r, treeToList(l, xs):::List(x))
    }

  def main(args:Array[String]) = {
    val tree = listToTree(List(5, 2, 7, 3, 9, 1, 8, 4, 6), Lf())
    println(treeToList(tree, Nil))
  }
}

実行させると以下。

komamitsu@onion:~/lab/scala/tree$ scalac TreeSample.scala
komamitsu@onion:~/lab/scala/tree$ scala TreeSample
List(1, 2, 3, 4, 5, 6, 7, 8, 9)

何というかScalaっぽいコードとは何か?が全然解らないまま適当に書いているので、こんな感じで良いのかよく解りません><

とりあえず、OCamlのvariantはsealed classを継承したcase classで代用できそうなので、少し一安心。