2

試験の準備をしている間、F# のいくつかの課題に苦労しています。

割り当ては次のように述べています。

次の F# 宣言を検討してください。

let rec f i = 
    function
    | [] -> [i]
    | x::xs -> i+x :: f (i+1) xs

の型はfですint -> int list -> int list。式f 10 [0;1;2;3]は値を返します[10;12;14;16;14]。

関数fは末尾再帰ではありません。累積パラメーターfAを使用する末尾再帰バリアント を宣言します。f

と

の継続ベースの末尾再帰バリアント 、 を宣言しfCますf。

これまでのところ、次のようなことを試しました：

let fA i = 
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (i+x::acc) xs
    loop i []

しかし、なぜこれらで動作しないのかわかりません。私はこれについてより深い理解を欠いていることを知っているので、ここですべての頭脳を試してみます.

4

2 に答える 2

1

アキュムレータ

さて、あなたはほとんどそこにいます-最初に、オリジナルには2つの引数があることを覚えているかもしれませんf-したがって、おそらく別の引数を追加する必要があります:

let fA i xs = ...

その後、元の変更iが進むにつれて、あなたもそうすべきです（ループに追加してください）：

let fA i xs = 
    let rec loop i acc = function

それからあなたはほとんどそこにいます-loop正しい引数で呼び出す必要があり、おそらく順序の問題があります...試し続けてください:D

ああ、そうです-@Sehnsuchtが言ったように-どこかに を入れる必要がi+1あります...よく覚えておいiてくださいloop...

次のヒント

accほとんど何も変更されていないことがわかります。

let fA i xs = 
    let rec loop i acc = function
        | ???
        | x::xs -> loop (???) (???::acc) xs
    ???

明らかに、場所に（異なる）ものを挿入する必要があります???:D

それでも問題が解決しない場合は、次のようなコンパイル バージョンを入手できます。

let fA i xs = 
    let rec loop i acc = function
        | [] -> acc
        | x::xs -> loop i (x::acc) xs
    loop i [] xs

もちろん、これは正しく機能しませんが、何かが始まります

継続

あなたはおそらくそれを推測しました-アキュムレータベースから継続ベースへの方法はそれほど違いはありません(実際、これはより簡単かもしれません-あなたが後方思考にどれだけ慣れているかによって異なります):

次からやり直します。

let fC i xs =
    let rec loop i cont = function

問題が発生した場合は、コンパイラに少し手伝ってもらう必要があるかもしれません。そのためには、次のcontように型を追加します。

let fC i xs =
    let rec loop i (cont : int list -> int list) = function

ここで、新しい継続を作成する必要があることを思い出してください。新しい継続(fun res -> ...something... |> cont)として渡すようなものです。リストの残りの部分（あなたの）で私resのことをした結果と考えれば、それは簡単なはずです。xs

最初の継続では、おそらく何もしたくないでしょう...しかし、これはほとんどの場合同じなので、すぐにわかるでしょう。

あなたの先生がつけたいくつかの卑劣なポイント

  • これ[] -> [i]は厄介な場合があります...そして、はい、あなたは今それを見逃していました;) - 何かをコンパイルすると(最初の関心事になるはずです)、すぐにそれを理解できると思います
  • i+xそしてi+1...混ぜないで忘れないでください;）

PS：宿題をあまり台無しにしたくありません-後でこれを完全な回答にします-しかし、1つのコメントIMOでは多すぎて読めませんでした

于 2015-05-28T13:14:16.720 に答える
1

この質問に出くわしたばかりで、私にとってもいい練習になると思いました. 誰かに役立つことを願って解決策を共有します。最善の解決策としてではなく、謙虚な提案として受け取ってください。私はコンピュータ サイエンスの教育を受けていない F# ファンです。

私が使用していることに注意してください

let f list =
  match list with
  | ...

元のより簡潔な代わりに

let f =
  function
  | ...

前者の構文では、の引数がf可視になるためです。

実用的なソリューションは次のとおりです。

// Original version
let rec f i list = 
  match list with
  | [] -> [i]
  | x::xs -> i+x :: f (i+1) xs

// Tail recursive version with accumulator
let fA i list =
  let rec loop i acc list =
    match list with
    | x::xs ->
      let newI = i + 1
      let newAcc = x + i :: acc
      let newList = xs
      loop newI newAcc newList
    | [] -> List.rev (i::acc)
  loop i [] list

// Continuation based version
let fC i list =
  let rec loop i (cont:int list -> int list) list =
    match list with 
    | x::xs ->
      let newI = i + 1
      let newCont = fun res -> cont (x + i :: res)
      let newList = xs
      loop newI newCont newList
    | [] -> cont (i::list) 
  loop i id list

// All these expressions evaluate to [10; 12; 14; 16; 14]
let res1 = f 10 [0..3]
let res2 = fA 10 [0..3]
let res3 = fC 10 [0..3]

これらのソリューションのいずれかを改善できる場合は、コメントをいただければ幸いです。

于 2015-05-29T14:19:56.527 に答える