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

累加器

好吧，你快到了 - 首先你可能记得原来f有 2 个参数 - 所以你可能应该添加另一个：

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：我不想过多地破坏您的作业-稍后我会将其变成完整的答案-但是对于单个评论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 回答