2

私の教授が言語SMLに関して与えたいくつかのメモを調べていますが、関数の1つは次のようになっています。

fun max gt = 
    let fun lp curr [] = curr
           | lp curr (a::l) = if gt(a,curr)
                             then lp a l
                             else lp curr l
in
    lp
end

誰かがこれが何をしているのか説明するのを手伝ってもらえますか?私が最も混乱しているのは、次の行です。

    let fun lp curr [] = curr

これは正確にはどういう意味ですか?私が知る限り、という関数がありますlpが、curr []どういう意味ですか?これらの議論はありますか?もしそうなら、あなたはsmlで1つのパラメータだけを許可されていませんか?

4

2 に答える 2

8

これはlp、2つのパラメーターを受け取る関数であることを意味します。最初のパラメーターとcurr2番目のパラメーターは、論理的には空([])または少なくとも1つの要素を含む可能性のあるリストです(a::l)はリストのパターンですa。頭、そしてリストの残りはlです。

FPコードのそのビットを特定のよく知られた命令型言語に翻訳すると、次のようになります。

function lp(curr, lst) {
  if (lst.length == 0) {  
    return curr;
  } else {
    var a = lst[0];                   // first element
    var l = lst.slice(1, lst.length); // the rest
    if (gt(a, curr)) {
      return lp(a, l);
    } else {
      return lp(curr, l)
    }
  }
}

かなり一口ですが、それは忠実な翻訳です。

関数型言語はラムダ計算に基づいており、関数は正確に1つの値を取り、1つの結果を返します。SMLおよびその他のFP言語はこの理論に基づいていますが、実際にはかなり不便であるため、これらの言語の多くでは、カリー化と呼ばれるものを介して関数に複数のパラメーターを渡すことを表現できます。

そうです、ML関数では実際には1つの値しか取りませんが、カリー化すると複数の引数をエミュレートできます。

add2つの数値を加算する、という関数を作成しましょう。

fun add a b = a + b

それを行う必要がありますが、2つのパラメーターを定義しました。の種類はadd何ですか?REPLを見てみると、ですval add = fn : int -> int -> intこれは、 「addは、intを受け取り、別の関数(intを受け取り、intを返す)を返す関数です」と読みます。

したがって、次のように定義することもできますadd

fun add a = 
  fn b => a + b

そして、あなたはそれらが似ていることがわかります。実際、ある意味で前者は後者の糖衣構文であると言っても過言ではありません。したがって、MLで定義するすべての関数は、複数の引数を持つ関数であっても、実際には1つの引数を持つ関数であり、2番目の引数を受け入れる関数を返します。最初は慣れるのが少し難しいですが、すぐに第二の性質になります。

fun add a b = a + b  (* add is of type  int -> int -> int *)

add 1 2 (* returns 3 as you expect *)

(* calling add with only one parameter *)

val add1 = add 1

なにadd1?これは、渡した単一の引数に追加する関数です。1

add1 2 (* returns 3 *)

これは部分適用の例であり、関数を少しずつ呼び出し、一度に1つの引数を呼び出し、毎回戻って、残りの引数を受け入れる別の関数を呼び出します。

また、複数の引数の外観を与える別の方法があります。タプル:

(1, 2);     (* evaluates to a tuple of (int,int) *)

fun add (a,b) = a + b;

add (1, 2)  (* passing a SINGLE argument to a function that
               expects only a single argument, a tuple of 2 numbers *)

あなたの質問では、次のように実装するlp こともできlp (curr, someList)ます:

fun max gt curr lst = 
    let fun lp (curr, []) = curr
          | lp (curr, (a::l)) = if gt(a,curr) then lp (a, l)
                                else lp (curr, l)
in
    lp (curr, lst)
end

この場合、!maxとして宣言する必要があることに注意してください。max gt curr lst

あなたが投稿したコードでlpは、カリー化で明確に実装されています。そして maxそれ自体のタイプはでしたfn: ('a * 'a -> bool) -> 'a -> 'a list -> 'a。それを分解する:

('a * 'a -> bool) ->  (* passed to 'max' as 'gt' *)   
    'a ->             (* passed to 'lp' as 'curr' *)
       'a list ->     (* passed to 'lp' as 'someList' *)
          'a          (* what 'lp' returns (same as what 'max' itself returns) *)

のタイプ、:gtへの最初の引数に注意してください。これは1つの引数の関数であり、2つの'のタプルであり、を返します。だからここではカリー化しないでください。maxfn : (('a * 'a) -> bool)('a * 'a)'a'a

どちらを使用するかは、好み、慣習、および実用上の考慮事項の両方の問題です。

お役に立てれば。

于 2013-01-21T07:39:28.960 に答える
4

ファイズの優れた答えから、カリー化について少し明確にするために。

前に述べたように、SMLは関数が1つの引数を取ることのみを許可します。これは、関数fun foo x = xが実際には(構文糖衣構文)の派生形式であるためval rec foo = fn x => xです。実際、これは完全に真実ではありませんが、少しの間単純にしておこう

ここで、このべき関数を例にとってみましょう。ここでは、「2つの引数を取る」関数を宣言します

fun pow n 0 = 1 
  | pow n k = n * pow n (k-1)

上で述べたように、fun ...は派生形式であり、したがって、べき関数の同等の形式は次のようになります。

val rec pow = fn n => fn k => ...

ここでわかるように、元の関数宣言の2つの異なるパターン一致を表現する際に問題が発生するため、「単純」に保つことができなくなり、fun宣言の実際の同等の形式は次のようになります。

val rec pow = fn n => fn k =>
    case (n, k) of 
      (n, 0) => 1
    | (n, k) => n * pow n (k-1)

完全を期すために、caseは実際には派生形式でもあり、同等の形式として無名関数を使用します

val rec pow = fn n => fn k => 
    (fn (n,0) => 1
      | (n,k) => n * pow n (k-1)) (n,k)

(n,k)これは、最も内側の無名関数に直接適用されることに注意してください。

于 2013-01-21T12:41:37.377 に答える