3

99個のscala問題には次の質問があります：

リスト要素の連続した複製をサブリストにパックします。リストに繰り返し要素が含まれる場合、それらは別々のサブリストに配置する必要があります。

Example:

scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

上記の問題を解決するための末尾再帰的な方法を理解しています。中間結果が共通要素のリストである scanLeft を使用して上記を達成する方法があるかどうか疑問に思っていましたか?

4

5 に答える 5

1

これが使用する解決策foldLeftです：

def pack[A](l:List[A]): List[List[A]] = l match {
  case head :: tail =>
    tail.foldLeft(List(List(head))) { (collector:List[List[A]], elem:A) =>
      if (collector.head.head == elem)
        (elem +: collector.head) +: collector.tail
      else
        List(elem) +: collector
    }.reverse
  case _ => List.empty
}

これはリストに対してのみ機能します。MultiSetsScalaの実装を見つけるのは難しいですが、より良い解決策はおそらくを使用するでしょう。

于 2012-12-12T17:38:48.607 に答える
1

簡潔だが最適化されていないバージョンは次のようになります。

val l = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
for (i <-l.distinct) yield l.filter(_ == i)

res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a, 'a, 'a), List('b), List('c, 'c), List('d), List('e, 'e, 'e, 'e))
于 2014-06-17T13:14:13.700 に答える
1

を開始するとScala 2.13、以下と組み合わせることができるビルダーがList提供されるようになりました。unfoldList::span

// val list = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
List.unfold(list) {
  case Nil  => None
  case rest => Some(rest.span(_ == rest.head))
}
// List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

Scala 2.13または代わりに、のOption#unlessビルダーと組み合わせて:

List.unfold(list) {
  rest => Option.unless(rest.isEmpty)(rest.span(_ == rest.head))
}

詳細：

  • Unfold は内部状態を使用しますが、この場合はlistto splitで初期化されますList('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
  • 各反復でspan、同じシンボルを含む接頭辞を見つけるために、その内部状態を調べます。l.span(_ == l.head)これは最初の反復中にl.span(_ == 'a)あり、(List('a, 'a, 'a, 'a),List('b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
  • 最初の部分が構築中のリストに追加する新しい要素 (こちら) であり、2 番目の部分が内部状態の新しい値(こちら) であるタプルのunfold反復ごとに予想されるように、そのスパンはまさにその要件に適合します。OptionList('a, 'a, 'a, 'a)List('b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
  • 内部リストが空になるまで同じステップを繰り返しunfoldますNone。
于 2018-10-14T07:41:36.063 に答える
0

いいえ、scanLeftこの場合は適切な方法ではありません。scanLeftリスト内の値ごとに 1 つの要素と、指定した初期値を含む結果のコレクションが生成されます。たとえば、scanLeftonList(1,2,3,4)を使用すると、常に 5 つの要素を持つ結果が得られます。

例えば

scala> List(1,2,3,4).scanLeft(">"){case (last, x) => last + x}
res7: List[String] = List(>, >1, >12, >123, >1234)
于 2012-12-13T00:03:29.643 に答える
0

scanLeft は、プレフィックスの合計を計算するのに役立ちますが、これは問題には当てはまりません。他の呼び出しと組み合わせてみることもできますが、問題を解決する良い方法ではないと思います。

このタスクには、foldLeft の方が便利なようです。

def pack[T](list: Seq[T]) = list.foldLeft(new ArrayBuffer[ArrayBuffer[T]])((ret, el) => {
    if (ret.isEmpty || ret.last.head != el)
      ret.append(new ArrayBuffer[T])
    ret.last.append(el)
    ret
  })

好奇心旺盛な読者のために、2 つの簡単なタスクが残されています。

  • List prepending を使用して純粋に機能させる
  • 正しい戻り値の型を作る
于 2012-12-12T17:34:11.267 に答える