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

Scala

最長重複文字列問題

WEB+DB PRESS vol.67 の[入門]関数プログラミングをScalaでごにょごにょしてみる。

読んで字のごとく、最も重複している部分文字列を探す問題です。

*Main> maxDupStr "mississippi"
"issi"
*Main> maxDupStr "Ask not what your country can do for you, but what you can do for your country."
" can do for you"

どんどんHaskellより見た目が複雑になっていく…。calcLen = map lenStr ってやりたい。でも同じような関数があらかた揃っているから真似はしやすかったな。
ScalaDocでListとStringBuilderを眺めていれば欲しいものは大体見つかった。

object MaxDupStr {
    
    def main( args:Array[String] ){
       println( maxDupStr( args(0) ) )
    }

    //-- 最長重複文字列を計算する
    def maxDupStr( x:String ):String = {
        val sl = x.tails.toList.sortWith( _ < _ )
        extract(chooseMax (calcLen (makePair( sl ))))
    }
   
    //-- 隣り合う要素を組にする
    def makePair( xs:List[String] ) = xs zip xs.tail


    //-- 文字列の共通部分の長さを求める
    def calcLen( xs:List[(String, String)] ):List[(Int, String)] = xs map lenStr

    def lenStr( x:(String, String) ) = ( comlen(x), x._1 )

    def comlen( x:(String, String) ):Int = {
        def pairEq( x:(Char, Char) ) = x._1 == x._2
        (x._1 zip x._2) takeWhile pairEq length
    }

    //-- 共通部分が一番長い要素を取り出す
    def chooseMax( xs:List[(Int, String)] ):(Int, String) = {
        xs maxBy( _._1 )
    }

    //-- 共通部分のみを残す
    def extract( x:(Int, String) ):String = x._2 take x._1
}

おまけ・tailsの再発明

tailsって絶対あるだろ…と思いつつも実装してみたらやっぱり見つかったのでお蔵入りになったtails。

//def tails( x:String ): List[String] = {
//    def tailsIter( str:String, xs:List[String] ):List[String] = {
//        if ( str == "" ) {
//            return xs.reverse
//        } else {
//            tailsIter( str.tail, str :: xs )
//        }
//    }
//    val l = List[String]()
//    return tailsIter( x, l )
//}