3

指定された空でない整数のリストで最大値を見つけたいとします。次に、リスト内の要素を比較する必要があります。データ値はシーケンスとして与えられるため、リストの最初または最後から比較を行うことができます。両方の方法で定義します。a) 最初からの比較 b) 最後からの比較 (データ値がリストにある場合、どのようにこれを行うことができますか?)

私がやったことは、最初から比較して最大の数を見つけることです。

どうしたら最後までできるでしょうか？どのようなロジックを適用する必要がありますか?

最初から比較するための私のコードは次のとおりです。

- fun largest[x] = x
= | largest(x::y::xs) =
= if x>y then largest(x::xs) else largest(y::xs)
= | largest[] = 0;
val largest = fn : int list -> int


output

- largest [1,4,2,3,6,5,4,6,7];
val it = 7 : int
4

5 に答える 5

6

関数では、リストの最初の 2 つの要素が比較され、大きい方の値が残りの要素と比較されます。最後から比較するということは、リストの末尾の最大数を最初に見つけて、後で先頭の要素と比較することを意味すると思います。

fun largest [] = raise Empty 
 | largest [x] = x
 | largest (x::xs) =
      let 
        val y = largest xs
      in
        if x > y then x else y
      end

必須ではありませんが、完全を期すために空のリストのケースを処理する必要があります。また、関数を使用する場合は、関数を短縮できmaxます。

fun largest [] = raise Empty 
 | largest [x] = x
 | largest (x::xs) = max(x, largest xs)

正直なところ、末尾再帰的なバージョンの方がいいと思います (大きなリストでスタックを破壊しません)。私の関数は、他の回答が示したように末尾再帰に書き直すことができますが、確かにあなたの関数よりも洗練されています。

于 2012-09-21T06:20:07.937 に答える
4

@pad が彼のコードで示しているように、適用すべきロジックは、関数の現在のスコープの問題を解決する前にサブ問題を再帰的に解決する再帰呼び出しを行うことです。

の場合largest、コードを「手動で」実行すると明らかになるスタック領域を単に使用するため、逆方向に解決しても意味がありません。ただし、設計パターンは他の状況でも役立ちます。という関数を想像してくださいzip:

(* zip ([1,2,3,4], [a,b,c]) = [(1,a),(2,b),(3,c)] *)
fun zip (x::xs, y::ys) = (x,y) :: zip (xs, ys)
  | zip _ = []

この関数は、2 つのリストのタプルを多数のタプルのリストに変換し、残りの値を破棄します。状況によっては役立つかもしれませんし、それを定義することもそれほど悪くはありません。ただし、対応する を作成するのunzipは少しトリッキーです。

(* unzip ([(1,a),(2,b),(3,c)] = ([1,2,3],[a,b,c]) *)
fun unzip [] = ([], [])
  | unzip ((x,y)::xys) =
    let
      val (xs, ys) = unzip xys
    in
      (x::xs, y::ys)
    end

通常の "最初から"-largest を手動で実行すると、次のようになります。

   largest [1,4,2,3,6,5,4,6,7]
~> largest [4,2,3,6,5,4,6,7]
~> largest [4,3,6,5,4,6,7]
~> largest [4,6,5,4,6,7]
~> largest [6,5,4,6,7]
~> largest [6,4,6,7]
~> largest [6,6,7]
~> largest [6,7]
~> largest [7]
~> 7

すべてのインデント レベルで関数呼び出しの現在のコンテキストをスタック メモリに保存し、新しい関数を呼び出して矢印の後に結果を返す必要があると想像して、「最後から」最大のものを手動で実行すると、次の~>ようになります。

largest [1,4,2,3,6,5,4,6,7] ~> 7
 \_
   largest [4,2,3,6,5,4,6,7] ~> 7
    \_
      largest [2,3,6,5,4,6,7] ~> 7
       \_
         largest [3,6,5,4,6,7] ~> 7
          \_
            largest [6,5,4,6,7] ~> 7
             \_
               largest [5,4,6,7] ~> 7
                \_
                  largest [4,6,7] ~> 7
                   \_ 
                     largest [6,7] ~> 7
                      \_
                        largest [7] ~> 7

では、単純により多くのメモリを使用する場合、初期の再帰呼び出しを有用にするこれらの非末尾再帰関数がなぜ役立つのでしょうか? に戻ってunzip、この厄介な「逆の考え方」をせずに解決したい場合、x と y を配置する場所がないため、タプルである新しい結果を構築する際に問題が発生します。

(* Attempt 1 to solve unzip without abusing the call stack *)
fun unzip [] = ([], [])
  | unzip ((x,y)::xys) = ...something with x, y and unzip xys...

そのような場所を作成するための 1 つのアイデアは、ビルドxsとys. xys リストの最後に到達すると、それらの値が返されます。

(* Attempt 2 to solve unzip without abusing the call stack *)
local
  fun unzipAux ([], xs, ys) = (xs, ys)
    | unzipAux ((x,y)::xys, xs, ys) = unzipAux (xys, x::xs, y::ys)
in
  fun unzip xys = unzipAux (xys, [], [])
end

(xs, ys)しかし、結果が逆になることに気付いたかもしれません。これを修正する簡単な方法はrev、一度だけ使用することです。これは、基本ケースで最もよく達成されます。

(* Attempt 3 to solve unzip without abusing the call stack *)
local
  fun unzipAux ([], xs, ys) = (rev xs, rev ys)
    | unzipAux ((x,y)::xys, xs, ys) = unzipAux (xys, x::xs, y::ys)
in
  fun unzip xys = unzipAux (xys, [], [])
end

これは興味深い質問をもたらします:どのようにrev実装されていますか?

于 2012-09-21T20:08:56.227 に答える
1

現在の最大値をアキュムレータとして渡す末尾再帰ヘルパーを使用することをお勧めします。

local
    fun helper max [] = max
      | helper max (n::ns) = helper (if n > max then n else max) ns
in
    fun largest ns = helper 0 ns
end;
于 2012-09-22T04:22:18.637 に答える