ゆろよろ日記

ちょっとした問題。Listから要素を検索して残りの要素数を返す。どう書く?

scala | 18:56 |

ちょっと面白い問題を見つけたので、俺も解いてみました。

Blogger: ブログが見つかりません

仕様はこうです。

1. あるListから要素を探し、該当する要素を除いた残りの要素数を返す。
2. ただし、要素がListに存在しない場合は-1を返す。

1の仕様だけなら、単純にList#dropWhileしてlengthを返すだけでしょうが、2を考えるとそうも行きません。

存在しない場合もListの末尾に該当する場合もともに結果が0になってしまうからです。

実行結果はこんな感じになります。

scala> val list = List("World", "is", "not", "enough")
list: List[java.lang.String] = List(World, is, not, enough)

scala> remainsLength( list , "is")
res1: Int = 2

scala> remainsLength( list , "foo")
res2: Int = -1

scala> remainsLength( list , "enough")
res3: Int = 0

俺はScalaで解きましたが、他の言語でやってみるのも面白いかとおもいます。

ストレートにやってみる

List#dropWhileだけではダメなら、最初に要素が存在するかList#findで検索して、結果のOption型をmatchで分けてやればよいと考えたのが以下のものです。

def remainsLength[T]( l:List[T],v:T ) = l.find{ v == } match { 
  case Some(_) => l.dropWhile{  v!= }.size - 1
  case None => -1 
}

よく考えたら、List#indexOfでいんじゃまいかと思って書いたのが以下のものです。考え方自体はfindと変わってないです。

def remainsLength[T]( l:List[T],v:T ) = l.indexOf( v ) match {
  case -1 => -1
  case n  => l.drop( n + 1 ).length
}

ただ、どっちも matchを使ってるんでいまいちな感じ。

再帰でやってみる

再帰でやるなら、Listのパターンマッチで、先頭要素が該当するまで再帰で頭からListを喰っていけばよいはずです。

def remainsLength[T]( l:List[T],v:T ):Int = l match {
  case Nil => -1 
  case `v` ::xs => xs.length
  case x::xs => search( xs , v)
}

caseに書くセレクタで`(バッククォート)で囲むと、パターンマッチ変数にならずに評価されるというのは初めて知りました。

このパターンマッチは以外と有用かも?

追記

@ymnkさんにもっとエレガントな回答を頂きました。

def search[T](l: Seq[T], s:T)=l.dropWhile(s!=_).length-1 

dropWhileで返す要素が、検索対象を含む場合は最小で1、含まない場合は0だから、単純にlength-1をするだけでおけと。

追記その2 無理矢理なimplicit conversionでOptionを拡張してみた

Optionに、Someだったら中身を引数の関数に渡して、Noneだったらdefaultを返すような関数が無かったので、無理矢理implicit conversionで対応してみたのがこれ。

class MapOrElseOption[A]( o:Option[A] ){

  def mapOrElse[B]( default : => B)( f:(A) => B ) = o match {
    case None => default
    case Some(x) => f(x)
  }
}

implicit def option2MapOrElseOption[A]( o:Option[A] ) = new MapOrElseOption( o )


def remainsLength[T]( l:List[T],v:T ) = l.find{ v == }.mapOrElse( -1 ){ _ => l.dropWhile{  v!= }.size - 1 }

ツイートする