リストの最大値をスカラーで再帰的に見つける

Question

私はScalaを初めて使いました。可能な限り最も基本的な知識でこれを表現するより良い方法がありますか？

def findMax(xs: List[Int]): Int = { 
     xs match { 
     case x :: tail => (if (tail.length==0) x else (if(x>findMax(tail)) x else (findMax(tail)))) 
     } 
    } 

Answer 1

ここでは2つの問題があります。まずを呼び出します。これはO(N)の操作です。最悪の場合、これはN * N個のステップを必要とします。ここで、Nはシーケンスの長さです。もう1つは、関数が末尾再帰的ではないということです。findMaxを「外側から内側に」呼び出すことができます。

正しい再帰関数を記述するために通常の戦略は、それぞれの可能なパターンの場合について考えて

• である：ここでは、空のリストNilまたは非空のリストhead :: tailのいずれかを持っています。これはあなたの最初の問題を解決します。
• この関数の別の引数として、一時的な結果（ここでは最大値の現在の推測）を持ちます。これはあなたの2番目の問題を解決します。

これは与える：

import scala.annotation.tailrec 

@tailrec 
def findMax(xs: List[Int], max: Int): Int = xs match { 
    case head :: tail => findMax(tail, if (head > max) head else max) 
    case Nil => max 
} 

val z = util.Random.shuffle(1 to 100 toList) 
assert(findMax(z, Int.MinValue) == 100) 

あなたは、この追加の引数を公開したくない場合は、補助内部関数を書くことができます。

def findMax(xs: List[Int]): Int = { 
    @tailrec 
    def loop(ys: List[Int], max: Int): Int = ys match { 
    case head :: tail => loop(tail, if (head > max) head else max) 
    case Nil => max 
    } 
    loop(xs, Int.MinValue) 
} 

val z = util.Random.shuffle(1 to 100 toList) 
assert(findMax(z) == 100) 

簡略化のため、リストが空の場合はInt.MinValueを返します。この場合、例外をスローする方がよい場合があります。

---

ここ@tailrec注釈は、それは単に私たちが実際に末尾再帰関数を定義していることを保証し、オプションです。これは、リストが極端に長い場合にスタックオーバーフローを生成できないという利点があります。

Answer 2

コレクションを1つの値に減らす場合は、明示的な再帰の代わりにfoldのいずれかの関数を使用することを検討してください。再帰パターンマッチングを使用

List(3,7,1).fold(Int.MinValue)(Math.max) 
// 7 

Answer 3

、

def top(xs: List[Int]): Int = xs match { 
    case Nil  => sys.error("no max in empty list") 
    case x :: Nil => x 
    case x :: xs => math.max(x, top(xs)) 
} 

パターンマッチングは、ヘッド、残りにリストを分解するために使用されます。 1つの要素リストはx :: Nilと表示されます。リストの残りの部分について再帰的に反復し、各再帰的段階でリストの先頭項目の最大値を比較します。ケースを網羅的にするため（明確な関数を作るために）、空リスト（Nil）も考慮します。

Answer 4

def maxl(xl: List[Int]): Int = { 
    if ((xl.head > xl.tail.head) && (xl.tail.length >= 1)) 
    return xl.head 
    else 
    if(xl.tail.length == 1) 
     xl.tail.head 
    else 
     maxl(xl.tail) 
}