すごいH本の 「ヒースロー空港からロンドンへ」を Scala でやってみた
すごいH本の 「ヒースロー空港からロンドンへ」をScalaでやってみました。
ほとんど Haskellそのままです。
英語版はWebで公開されていてココに。
data で定義している Section は case class で定義してみました。
case class Section(getA: Int, getB: Int, getC: Int)
Label は 列挙型をつかって
object Label extends Enumeration { val A,B,C = Value }
として定義し、指定する場合は Label.A Label.B のように使います。 列挙型にしておくと もし Label.D のように定義していない 値を指定すると
scala> Label.D
<console>:9: error: value D is not a member of object Label
Label.D
のようにエラーになります。
Pathの定義は 迷ったのですが、Haskellのように
Type ではやりにくかったので case class で中身を Path として定義して
case class Path(label: Label.Value, cost: Int)
List[Path] としてみました。 つかうときに (List[Path],List[Path])のタプル型のデータを使うようにしてみたのですが、 動作的にはいいのですが、いまいち見通しが悪い気がする。。。
ソース
case class Section(getA: Int, getB: Int, getC: Int) type RoadSystem = List[Section] val heathrowToLondon: RoadSystem = List(Section(50,10,30),Section(5,90,20),Section(40,2,25),Section(10,8,0)) object Label extends Enumeration { val A,B,C = Value } case class Path(label: Label.Value, cost: Int) def roadStep(p:(List[Path],List[Path]))(s:Section):(List[Path],List[Path]) = { val priceA = p._1.map{x => x.cost}.sum val priceB = p._2.map{x => x.cost}.sum val forwardPriceToA = priceA + s.getA val crossPriceToA = priceB + s.getB + s.getC val forwardPriceToB = priceB + s.getB val crossPriceToB = priceA + s.getA + s.getC val newPathToA = if (forwardPriceToA <= crossPriceToA) {Path(Label.A,s.getA)::p._1} else {Path(Label.C,s.getC)::Path(Label.B,s.getB)::p._2} val newPathToB = if (forwardPriceToB <= crossPriceToB) {Path(Label.B,s.getB)::p._2} else {Path(Label.C,s.getC)::Path(Label.A,s.getA)::p._1} (newPathToA,newPathToB) } def optimalPath(r:RoadSystem):List[Path] = { // val (bestAPath, bestBPath) = r.foldLeft((List():List[Path],List():List[Path])){(x,y) => roadStep(x)(y)} val (bestAPath, bestBPath) = (((List():List[Path],List():List[Path])) /: r){(x,y) => roadStep(x)(y)} if (bestAPath.map(_.cost).sum <= bestBPath.map(_.cost).sum) bestAPath.reverse else bestBPath.reverse } /* def groupsOf[A](i:Int)(l:List[A]):List[List[A]] = { (i,l) match { case (_,List()) => List() case (0,_) => List() case _ => l.take(i) :: groupsOf(i){l.drop(i)} } } */ val bestway = optimalPath(heathrowToLondon) println("The best path to take is: %s".format(bestway.map(_.label).mkString)) println("The price is: %s".format(bestway.map(_.cost).sum))
- 作者: Miran Lipovaca
- 出版社/メーカー: オーム社
- 発売日: 2012/09/21
- メディア: Kindle版
- 購入: 3人 クリック: 6回
- この商品を含むブログを見る