Takuya71 のぶろぐ

外資系ソフトウェア会社で働いてます、認定スクラムマスター

すごい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))

gist

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!