3

次の要件を満たす、リストから要素の範囲を抽出したい:

  • 範囲の最初の要素は、特定の条件に一致する要素の前の要素である必要があります
  • 範囲の最後の要素は、特定の条件に一致する要素の次の要素である必要があります
  • 例: リスト (1,1,1,10,2,10,1,1,1) とx >= 10取得したい条件 (1,10,2,10,1)の場合

これは命令的にプログラムするのは非常に簡単ですが、それを達成するためのスマートな Scala 関数の方法があるかどうか疑問に思っています。それは...ですか？

4

4 に答える 4

3

それをscala標準ライブラリに保持し、再帰を使用してこれを解決します：

def f(_xs: List[Int])(cond: Int => Boolean): List[Int] = {
  def inner(xs: List[Int], res: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x :: y :: tail if cond(y) && res.isEmpty => inner(tail, res ++ (x :: y :: Nil))
    case x :: y :: tail if cond(x) && res.nonEmpty => res ++ (x :: y :: Nil)
    case x :: tail if res.nonEmpty => inner(tail, res :+ x)
    case x :: tail => inner(tail, res)
  }

  inner(_xs, Nil)
}

scala> f(List(1,1,1,10,2,10,1,1,1))(_ >= 10)
res3: List[Int] = List(1, 10, 2, 10, 1)

scala> f(List(2,10,2,10))(_ >= 10)
res4: List[Int] = List()

scala> f(List(2,10,2,10,1))(_ >= 10)
res5: List[Int] = List(2, 10, 2, 10, 1)

このソリューションで思いつかなかったこと、または誤解していたことがあるかもしれませんが、基本的な考え方は理解できると思います。

于 2013-09-13T10:32:48.957 に答える
2

優れた機能的アルゴリズム設計の実践とは、複雑な問題をより単純なものに分解することです。その原則は分割統治法と呼ばれます。

主題の問題から 2 つの単純な下位問題を抽出するのは簡単です。

  1. この一致する要素が前にあり、その前にある要素が前にある、一致する要素の後のすべての要素のリストを取得します。

  2. 一致する最新の要素までのすべての要素のリストを取得し、その後に一致する要素とその後の要素を取得します。

名前付きの問題は、適切な機能を実装するのに十分単純であるため、細分化は必要ありません。

最初の関数の実装は次のとおりです。

def afterWithPredecessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: tail if test( a ) => Nil // since there is no predecessor
      case a :: b :: tail if test( b ) => a :: b :: tail
      case a :: tail => afterWithPredecessor( tail )( test )
    }

2 番目の問題は最初の問題の直接の逆と見なすことができるため、入力と出力を逆にすることで簡単に実装できます。

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = afterWithPredecessor( elements.reverse )( test ).reverse

しかし、これの最適化されたバージョンは次のとおりです。

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: b :: tail if test( a ) => 
        a :: b :: beforeWithSuccessor( tail )( test )
      case a :: tail => 
        beforeWithSuccessor( tail )( test ) match {
          case Nil => Nil
          case r => a :: r
        }
    }

最後に、上記の関数を一緒に構成して、問題を解決する関数を生成することは非常に簡単になります。

def range[ A ]( elements : List[ A ] )( test : A => Boolean ) : List[ A ] 
  = beforeWithSuccessor( afterWithPredecessor( elements )( test ) )( test )

テスト:

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 10 )
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 1 )
res1: List[Int] = List()

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ == 2 )
res2: List[Int] = List(10, 2, 10)

述語を満たす最も外側の要素には先行要素 (または後続要素) がないため、2 番目のテストは空のリストを返します。

于 2013-09-15T21:04:23.337 に答える
1

zip とマップで救出

val l = List(1, 1, 1, 10, 2, 1, 1, 1)

def test (i: Int) = i >= 10

((l.head :: l) zip (l.tail :+ l.last)) zip l filter {
  case ((a, b), c) => (test (a) || test (b) || test (c) )
} map { case ((a, b), c ) => c }

それはうまくいくはずです。私は自分のスマートフォンしか持っておらず、これをテストできる場所から何マイルも離れているため、タイプミスや軽微な構文エラーについてお詫び申し上げます

編集：現在動作します。私のソリューションがリストを右と左にシャッフルして、2 つの新しいリストを作成することが明らかであることを願っています。これらを一緒に圧縮し、元のリストで再度圧縮すると、結果はタプルのリストになり、それぞれに元の要素とその隣接要素のタプルが含まれます。これをフィルタリングして単純なリストに戻すのは簡単です。

これをより一般的な関数にします (そしてcollect、フィルター -> マップではなく使用します)...

def filterWithNeighbours[E](l: List[E])(p: E => Boolean) = l match {
  case Nil => Nil
  case li if li.size < 3 => if (l exists p) l else Nil
  case _ => ((l.head :: l) zip (l.tail :+ l.last)) zip l collect {
    case ((a, b), c) if (p (a) || p (b) || p (c) ) => c
  }
}

これは再帰的ソリューションよりも効率的ではありませんが、テストがより単純で明確になります。パターンは元のデータではなく、選択された実装の形状を表すことが多いため、再帰的なソリューションでパターンの正しいシーケンスを一致させることは困難な場合があります。シンプルな機能ソリューションにより、各要素は隣接する要素と明確かつ単純に比較されます。

于 2013-09-14T15:34:36.687 に答える
1 
def range[T](elements: List[T], condition: T => Boolean): List[T] = {
   val first = elements.indexWhere(condition)
   val last  = elements.lastIndexWhere(condition)

   elements.slice(first - 1, last + 2)
}

scala> range[Int](List(1,1,1,10,2,10,1,1,1), _ >= 10)
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range[Int](List(2,10,2,10), _ >= 10)
res1: List[Int] = List(2, 10, 2, 10)

scala> range[Int](List(), _ >= 10)
res2: List[Int] = List()
于 2013-09-13T12:08:04.943 に答える