2

リストで最大サイズの整数を返す必要がある次の再帰関数が Scala にあります。最大値が返されない理由を教えてくれる人はいますか?

  def max(xs: List[Int]): Int = {
    var largest = xs.head
    println("largest: " + largest)
    if (!xs.tail.isEmpty) {
      var next = xs.tail.head
      println("next: " + next)
      largest = if (largest > next) largest else next
      var remaining = List[Int]()
      remaining = largest :: xs.tail.tail
      println("remaining: " + remaining)
      max(remaining)
    }
    return largest
  }

Print out ステートメントは、List 内の最大値を head として正常に戻すことができたことを示しています (これは私が望んでいたことです) が、関数は依然としてリスト内の元の head を返します。これは、xs の参照がまだ元の xs リストを参照しているためだと推測しています。問題は、それが val であるため、それをオーバーライドできないことです。

私が間違っていることはありますか？

4

8 に答える 8

3

max への内部呼び出しの戻り値を使用し、それをローカルの最大値と比較する必要があります。次のようなもの (読みやすくするために println を削除しました):

def max(xs: List[Int]): Int = {
    var largest = xs.head
    if (!xs.tail.isEmpty) {
      var remaining = List[Int]()
      remaining = largest :: xs.tail
      var next = max(remaining)
      largest = if (largest > next) largest else next
    }
    return largest
  }

さよなら。

于 2013-09-17T21:41:36.707 に答える
2

以下は、この種の問題を解決する典型的な方法です。追加の「アキュムレータ」値を含む内側の末尾再帰関数を使用します。この場合、これまでに見つかった最大値を保持します。

def max(xs: List[Int]): Int = {
  def go(xs: List[Int], acc: Int): Int = xs match {
    case Nil => acc // We've emptied the list, so just return the final result
    case x :: rest => if (acc > x) go(rest, acc) else go(rest, x) // Keep going, with remaining list and updated largest-value-so-far
  }

  go(xs, Int.MinValue)
}
于 2013-09-17T21:47:57.563 に答える
0

問題を解決したことは気にしないでください...

私は最終的に思いついた：

  def max(xs: List[Int]): Int = {
    var largest = 0
    var remaining = List[Int]()
    if (!xs.isEmpty) {
      largest = xs.head
      if (!xs.tail.isEmpty) {
        var next = xs.tail.head
        largest = if (largest > next) largest else next
        remaining = largest :: xs.tail.tail
      }
    }
    if (!remaining.tail.isEmpty) max(remaining) else xs.head
  }

ループがあるのはちょっとうれしいです - これは非常に複雑な解決策であり、私の意見では理解するのが難しいです。再帰呼び出しが関数の最後のステートメントであることを確認するか、配列に2番目のメンバーがない場合は xs.head が結果として返されるようにすることで問題を解決しました。

于 2013-09-17T21:40:32.820 に答える
0

私の答えは、再帰を使用することです。

def max(xs: List[Int]): Int =
  xs match {
    case Nil => throw new NoSuchElementException("empty list is not allowed")
    case head :: Nil => head
    case head :: tail =>
      if (head >= tail.head)
        if (tail.length > 1)
            max(head :: tail.tail)
        else
          head
      else
        max(tail)
  }
}
于 2016-09-15T13:58:17.787 に答える
0

私が今まで見た中で最も簡潔で明確なバージョンは次のとおりです。

def max(xs: List[Int]): Int = {
    def maxIter(a: Int, xs: List[Int]): Int = {
        if (xs.isEmpty) a
        else a max maxIter(xs.head, xs.tail)
    }
    maxIter(xs.head, xs.tail)
}

これは、ソリューションから Scala 公式 Corusera コースの宿題に適用されています: https://github.com/purlin/Coursera-Scala/blob/master/src/example/Lists.scala

ただし、ここでは豊富な演算子を使用してmax、2 つのオペランドのうち最大のものを返します。def maxこれにより、ブロック内でこの関数を再定義する必要がなくなります。

于 2013-12-13T06:49:06.080 に答える
0

これはどうですか ？

 def max(xs: List[Int]): Int = {
    var largest = xs.head
    if( !xs.tail.isEmpty ) {
      if(xs.head < max(xs.tail)) largest = max(xs.tail)     
    }  
    largest
  }
于 2014-07-08T06:38:43.643 に答える
0

これはどうですか？

def max(xs: List[Int]): Int = {
    maxRecursive(xs, 0)
  }

  def maxRecursive(xs: List[Int], max: Int): Int = {
    if(xs.head > max && ! xs.isEmpty)
       maxRecursive(xs.tail, xs.head)
    else
      max

  }
于 2014-04-26T10:53:22.637 に答える