最長重複文字列問題 in Scala

.groovy .scala

Clojure 編につづき Scala 編へ

Scala は Haskell の多くの関数が用意されているので Haskell からの書き換えるのには有利だ。

def makePair [T](xs: Seq[Seq[T]])          = xs zip xs.tail
def comlen   [T](p: (Seq[T],Seq[T]))       = p.zipped takeWhile(x => x._1 == x._2) size
def lenstr   [T](p: (Seq[T],Seq[T]))       = (comlen(p), p._1)
def calcLen  [T](xs: Seq[(Seq[T],Seq[T])]) = xs map lenstr
def chooseMax[T](xs: Seq[(Int,Seq[T])])    = xs maxBy(_._1)
def extract  [T](p: (Int,Seq[T]))          = p._2 take p._1
def maxDupStr[T <% Ordered[T]](xs: Seq[T]) = extract(chooseMax(calcLen(makePair(xs.tails.toSeq.sorted(seqAsc[T])))))

def seqAsc[T <% Ordered[T]]: Ordering[Seq[T]] = new Ordering[Seq[T]] {
  def compare(x: Seq[T], y: Seq[T]) = x.view.zip(y).map(p => p._1 compare p._2)
                                       .find(_ != 0).getOrElse(x.size.compareTo(y.size))
}

assert( maxDupStr("mississippi").mkString == "issi" )
assert( maxDupStr(List(8,10,8,10,12,8,10,8,10,12,8)) == List(8,10,8,10,12,8) )
assert( maxDupStr(Array(8,10,8,10,12,8,10,8,10,12,8)) sameElements Array(8,10,8,10,12,8) )

List の Comparator は最初は trampoline のバージョンを移植したのだが Ideone.com - HKjoN - Online Scala Compiler & Debugging Tool のものを見つけたのでこれを使った。
ただ知らない機能だったので、可視境界を使うように変更した。
Scala でこのような機能を調べるときにどうすればよいか分からないのだが今回は運よくすぐ見つけられた。

Context Bound は 2.8 からの機能なので持っている『Scala スケーラブルプログラミング』には載っていなかったのだ。

implicit conversion

Scala 版はこの時点で文字列で渡すことに成功している。
これは Groovy でいうところのカテゴリの機能が効いているためである。
implicit conversion は Java のオートボクシングのようにラッパー型に変換する機能である。
しかもラッパー型に変換する関数も指定できる。
あるスコープ内だけ使えるメソッドが増えるという意味では Groovy のカテゴリと同じ効果がある。


implicit conversion の効果は Groovy のカテゴリなのだが、個人的なイメージではダックタイピングのように思える。

  • 同じ名前のメソッドがあれば同じように扱っていいだろう
  • ある型に変更してもよいなら変更して扱ってもいいだろう


ラッパー型と変換する関数を用意するのでいまいちオープンクラスと同じといわれてもピンとこないのだがそれっぽいものを見つけた。
変換関数で特異オブジェクトを生成する方法

しかしバージョン 2.10 ではラッパー型自体で変換できるみたいだ。

ただ今回は == は Any のメソッドで String 型を要求されないので mkString が必要になった。

関数プログラミングっぽくない？

Scala 版、関数合成つかってなくない？
合成しようと思えばできますとも。

def maxDupStr[T <% Ordered[T]](xs: Seq[T]) = (extract[T] _ compose chooseMax[T] compose calcLen[T] compose makePair[T])(xs.tails.toSeq.sorted(seqAsc[T]))


メソッドの中で合成するのですか？それはポイントフリースタイルではありません。
それは = の左から xs を消せということですか？
できますとも！

val makePair  = (xs:Seq[Seq[Any]])            => xs zip xs.tail
val comlen    = (p:(Seq[Any],Seq[Any]))       => p.zipped takeWhile(x => x._1 == x._2) size
val lenstr    = (p:(Seq[Any],Seq[Any]))       => (comlen(p), p._1)
val calcLen   = (xs:Seq[(Seq[Any],Seq[Any])]) => xs map lenstr
val chooseMax = (xs:Seq[(Int,Seq[Any])])      => xs maxBy(_._1)
val extract   = (p:(Int,Seq[Any]))            => p._2 take p._1
val maxDupStr = extract compose chooseMax compose calcLen compose makePair
assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" )


Scala は静的型付け言語なのです。Any を使わないでいきましょう。
しかし、Char と Int をどうすれば同じように扱えるのですか？


型パラメータを使いましょう。
使いました。大量にコンパイルエラーが発生しました。
存在型がバナナでないことは知っていますが、型パラメータにする方法は知りません。

どうして型パラメータが使えないのか？

Scala には難解な用語がでてきますが要は Java なのです。
Groovy プログラマは Java を知っています。Java で考えればよいのです。

// Comparable で考える
interface Comparable<T>

// Any と書けるということは Object と書けるということ
new Comparable<Object>() {
  @Override int compareTo(Object a, Object b) { ... }
}

// こんな風には Java でも書かない
new Comparable<T>() {
  @Override int compareTo(T a, T b) { ... }
}


T で書くにはどうすればよいでしょう？

// 型ではなく式で考える
{ 2*it }(1)

// 定数ではなく変数を使いたいとしたら
{ 2*it }(x)

// こうするしかない
{ x -> { 2*it }(x) }

クラスを使って型を遅延評価する

class SeqOps[T] {
  val makePair  = (xs:Seq[Seq[T]])          => xs zip xs.tail
  val comlen    = (p:(Seq[T],Seq[T]))       => p.zipped takeWhile(x => x._1 == x._2) size
  val lenstr    = (p:(Seq[T],Seq[T]))       => (comlen(p), p._1)
  val calcLen   = (xs:Seq[(Seq[T],Seq[T])]) => xs map lenstr
  val chooseMax = (xs:Seq[(Int,Seq[T])])    => xs maxBy(_._1)
  val extract   = (p:(Int,Seq[T]))          => p._2 take p._1
  val maxDupStr = extract compose chooseMax compose calcLen compose makePair
}

def seqAsc[T <% Ordered[T]]: Ordering[Seq[T]] = new Ordering[Seq[T]] {
  def compare(x: Seq[T], y: Seq[T]) = x.view.zip(y).map(p => p._1 compare p._2)
                                       .find(_ != 0).getOrElse(x.size.compareTo(y.size))
}

{
  val charOps = new SeqOps[Char]
  import charOps._
  assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" )
}

{
  val intOps = new SeqOps[Int]
  import intOps._
  assert( maxDupStr(List(8,10,8,10,12,8,10,8,10,12,8).tails.toSeq.sorted(seqAsc[Int]).map(_.toSeq)) == List(8,10,8,10,12,8) )
}

これで型安全な合成ができるようになった。

Scala の import は、オブジェクトも import できる。これは Groovy の with に近い。
ただし import new とは書けなかった。


毎回、インスタンスを生成する必要はないので保存場所をさがす。
Scala には static がないのでシングルトンオブジェクトを利用する。

object SeqOps {
  val charOps = new SeqOps[Char]
  val intOps  = new SeqOps[Int]
}

{
  import SeqOps.charOps._
  assert( maxDupStr("mississippi".tails.toSeq.sorted.map(_.toSeq)).mkString == "issi" )
}

終わりに

次は Scheme かと思ったのだけどうまく書けそうに無いのでリスペクトだけで。
Groovy から見た Clojure と Scala という視点で書いてみた。

2012-05-12 修正

maxDupStr を SeqOps の中に入れた

2012-05-18 追記

object SeqOps {
  object Char extends SeqOps[Char]
  object Int  extends SeqOps[Int]
}

武田氏の赤黒木を見ていたら StringTree を object で宣言されていた。
型なので大文字ではじめられるように object で宣言した方がいいかもしれない。