これは、私が今まで考えた中で最も最小限の再帰的な max の実装です:
def max(xs: List[Int]): Option[Int] = xs match {
case Nil => None
case List(x: Int) => Some(x)
case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}
リストの最初の 2 つの要素を比較し、小さい方 (両方が等しい場合は最初の要素) を破棄し、残りのリストで自分自身を呼び出すことによって機能します。最終的に、これはリストを最大でなければならない 1 つの要素に減らします。
例外をスローせずに空のリストが与えられた場合に対処するオプションを返します。これにより、呼び出し元のコードがその可能性を認識して処理するようになります (例外をスローする場合は、呼び出し元まで)。
より一般的なものにしたい場合は、次のように記述する必要があります。
def max[A <% Ordered[A]](xs: List[A]): Option[A] = xs match {
case Nil => None
case x :: Nil => Some(x)
case x :: y :: rest => max( (if (x > y) x else y) :: rest )
}
Orderedこれは、トレイトを拡張するか、スコープ内でからAへの暗黙的な変換がある任意の型で機能します。scala.Predef がそれらの変換を定義しているため、Ordered[A]デフォルトでは、、などで機能します。IntBigIntCharString
次のように、さらに一般的になることができます。
def max[A <% Ordered[A]](xs: Seq[A]): Option[A] = xs match {
case s if s.isEmpty || !s.hasDefiniteSize => None
case s if s.size == 1 => Some(s(0))
case s if s(0) <= s(1) => max(s drop 1)
case s => max((s drop 1).updated(0, s(0)))
}
これは、リストだけでなく、ベクトルや、Seq特性を拡張するその他のコレクションでも機能します。シーケンスが実際に明確なサイズを持っているかどうかを確認するチェックを追加する必要があったことに注意してください。これは無限ストリームである可能性があるため、そうである可能性がある場合は元に戻します。ストリームが明確なサイズを持つことが確実な場合は、この関数を呼び出す前にいつでもそれを強制することができます - とにかくストリーム全体で機能します。ただし、無期限のストリームに戻りたくない理由については、最後のメモを参照してください。Noneここでは単純化のためにこれを行っています。
ただし、これはセットとマップでは機能しません。何をすべきか？次の一般的なスーパータイプは ですがIterable、これはサポートしていませんupdated。私たちが構築したものは、実際の型に対して非常にパフォーマンスが悪い可能性があります。したがって、ヘルパー関数を使用しないクリーンな再帰は失敗します。ヘルパー関数の使用に変更することもできますが、他の回答には多くの例があり、1 つの単純な関数アプローチに固執するつもりです。したがって、この時点で、次のように切り替えることができます(ここで、「Traversable」を選択して、すべてのコレクションreduceLeftに対応しましょう):
def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = {
if (xs.hasDefiniteSize)
xs reduceLeftOption({(b, a) => if (a >= b) a else b})
else None
}
しかし、reduceLeft を再帰的と見なさない場合は、次のようにすることができます。
def max[A <% Ordered[A]](xs: Traversable[A]): Option[A] = xs match {
case i if i.isEmpty => None
case i if i.size == 1 => Some(i.head)
case i if (i collect { case x if x > i.head => x }).isEmpty => Some(i.head)
case _ => max(xs collect { case x if x > xs.head => x })
}
コンビネータを使用して、 andcollectから新しい Iterator を差し出す不器用な方法を回避します。xs.headxs drop 2
これらのいずれも、順序があるもののほとんどすべてのコレクションで安全に機能します。例:
scala> max(Map(1 -> "two", 3 -> "Nine", 8 -> "carrot"))
res1: Option[(Int, String)] = Some((8,carrot))
scala> max("Supercalifragilisticexpialidocious")
res2: Option[Char] = Some(x)
Scala のより専門的な知識が必要なため、通常はこれらの例を挙げません。
また、基本的なTraversableトレイトはmaxメソッドを提供することを覚えておいてください。したがって、これはすべて練習用です ;)
注: 私のすべての例が、case 式のシーケンスを慎重に選択することで、個々の case 式をできるだけ単純にすることができることを示していることを願っています。
より重要な注意:ああ、また、私はNoneの入力に対して非常に快適に戻ることができますがNil、実際には、 に対して例外をスローする傾向が強くありますhasDefiniteSize == false。まず、有限ストリームは、純粋に評価のシーケンスに依存する明確なサイズまたは非明確なサイズを持つ可能性があり、この関数はそのようなOption場合に事実上ランダムに返されます-追跡に長い時間がかかる可能性があります. Nil第二に、合格したことと真のリスク入力 (つまり、無限の流れ) を合格したことを人々が区別できるようにしてほしいと思います。Optionコードをできるだけ単純にするために、これらのデモンストレーションに戻っただけです。
TraversableOnce最も簡単な方法は、次のように、traitの max 関数を使用することです。
val list = (1 to 10).toList
list.max
空虚を防ぐために、次のようなことができます。
if(list.empty) None else Some(list.max)
上記はあなたにOption[Int]
私の2番目のアプローチは、foldLeft
(list foldLeft None)((o, i) => o.fold(Some(i))(j => Some(Math.max(i, j))))
または、空のリストの場合に返されるデフォルト値がわかっている場合、これはより簡単になります。
val default = 0
(list foldLeft default)(Math.max)
とにかく、あなたの要件は再帰的に行うことなので、次のことを提案します。
def recur(list:List[Int], i:Option[Int] = None):Option[Int] = list match {
case Nil => i
case x :: xs => recur(xs, i.fold(Some(x))(j => Some(Math.max(j, x))))
}
またはデフォルトのケースとして、
val default = 0
def recur(list:List[Int], i:Int = default):Int = list match {
case Nil => i
case x :: xs => recur(xs, i.fold(x)(j => Math.max(j, x)))
}
であることに注意してくださいtail recursive。したがって、スタックも保存されます。
この問題に対する機能的なアプローチが必要な場合は、次を使用しますreduceLeft。
def max(xs: List[Int]) = {
if (xs.isEmpty) throw new NoSuchElementException
xs.reduceLeft((x, y) => if (x > y) x else y)
}
int のリストに固有のこの関数。より一般的なアプローチが必要な場合は、型クラスを使用しOrderingます。
def max[A](xs: List[A])(implicit cmp: Ordering[A]): A = {
if (xs.isEmpty) throw new NoSuchElementException
xs.reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
}
reduceLeft(A, A) => Aこの場合は 2 つの int を取り、それらを比較して大きい方を返します。
そのようなパターンマッチングを使用できます
def max(xs: List[Int]): Int = xs match {
case Nil => throw new NoSuchElementException("The list is empty")
case x :: Nil => x
case x :: tail => x.max(max(tail)) //x.max is Integer's class method
}
折り畳みは次のことに役立ちます。
if(xs.isEmpty)
throw new NoSuchElementException
else
(Int.MinValue /: xs)((max, value) => math.max(max, value))
リストとパターン マッチング (更新、@x3ro に感謝)
def max(xs:List[Int], defaultValue: =>Int):Int = {
@tailrec
def max0(xs:List[Int], maxSoFar:Int):Int = xs match {
case Nil => maxSoFar
case head::tail => max0(tail, math.max(maxSoFar, head))
}
if(xs.isEmpty)
defaultValue
else
max0(xs, Int.MinValue)
}
Option(このソリューションは毎回インスタンスを作成しません。また、末尾再帰であり、命令型ソリューションと同じくらい高速です。)
これが私のコードです（私は関数型プログラミングの初心者です）。この質問にたどり着く人は誰でも私のような人になると思います。一番の答えは素晴らしいですが、初心者には少し多すぎます! だから、ここに私の簡単な答えがあります。頭と尾だけを使用してこれを行うように (コースの一部として) 求められたことに注意してください。
/**
* This method returns the largest element in a list of integers. If the
* list `xs` is empty it throws a `java.util.NoSuchElementException`.
*
* @param xs A list of natural numbers
* @return The largest element in `xs`
* @throws java.util.NoSuchElementException if `xs` is an empty list
*/
@throws(classOf[java.util.NoSuchElementException])
def max(xs: List[Int]): Int = find_max(xs.head, xs.tail)
def find_max(max: Int, xs: List[Int]): Int = if (xs.isEmpty) max else if (max >= xs.head) find_max(max, xs.tail) else find_max(xs.head, xs.tail)
いくつかのテスト:
test("max of a few numbers") {
assert(max(List(3, 7, 2)) === 7)
intercept[NoSuchElementException] {
max(List())
}
assert(max(List(31,2,3,-31,1,2,-1,0,24,1,21,22)) === 31)
assert(max(List(2,31,3,-31,1,2,-1,0,24,1,21,22)) === 31)
assert(max(List(2,3,-31,1,2,-1,0,24,1,21,22,31)) === 31)
assert(max(List(Int.MaxValue,2,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,222,3,-31,1,2,-1,0,24,1,21,22)) === Int.MaxValue)
}
list.sortWith(_ > ).head & list.sortWith( > _).reverse.head for greatest and smallest number