f# - 尾递归映射 f#

Question

我想在 F# 中编写一个尾递归函数来将列表中的所有值乘以 2。我知道有很多方法可以做到这一点，但我想知道这是否是一种可行的方法。这纯粹是出于教育目的。我意识到有一个内置函数可以为我执行此操作。

 let multiply m =
    let rec innerfunct ax = function
    | [] -> printfn "%A" m
    | (car::cdr) -> (car <- car*2 innerfunct cdr);
  innerfunct m;;



let mutable a = 1::3::4::[]
multiply a

我有两个错误，尽管我怀疑它们是唯一的问题。

这个值在我的第二个匹配条件下是不可变的

和

这个表达式是一个函数值，即缺少参数。它的类型是'a list -> unit。当我调用 length a 时。

我对 F# 还很陌生，我意识到我可能没有正确调用该函数，但我不知道为什么。这对我来说主要是一次学习经历，所以解释比修复代码更重要。语法显然不正确，但是我可以通过执行相当于

的操作将 *2 映射到列表

car = car*2 然后在列表的 cdr 上调用内部函数。

Answer 1

如果不显示中间代码，我将无法轻松解释许多问题，因此我将尝试通过注释重构:

首先，我们将走可变路径:

1. 由于 F# 列表是不可变的，原始 int 也是如此，我们需要一种方法来改变列表中的内容:

   let mutable a = [ref 1; ref 3; ref 4]
   

2. 去掉多余的ax，稍微整理一下，就可以利用这些引用单元了:

   let multiply m =
       let rec innerfunct = function
       | [] -> printfn "%A" m
       | car :: cdr ->
           car := !car*2
           innerfunct cdr
       innerfunct m
   

3. 我们看到，乘法只调用了它的内部函数，所以我们最终得到了第一个解决方案:

   let rec multiply m =
       match m with
       | [] -> printfn "%A" m
       | car :: cdr ->
           car := !car*2
           multiply cdr
   

   ^{这真的只是为了它自己的目的。如果您想要可变性，请使用数组和传统的 for 循环。}

然后，我们走上不变的道路:

1. 正如我们在可变世界中了解到的，第一个错误是由于 car 不可变。它只是一个不可变列表中的原始 int。生活在一个不可变的世界意味着我们只能从我们的输入中创造出新的东西。我们想要的是构造一个新列表，以 car*2 作为头部，然后是递归调用 innerfunct 的结果。像往常一样，函数的所有分支都需要返回相同类型的东西:

   let multiply m =
       let rec innerfunct = function
       | [] ->
           printfn "%A" m
           []
       | car :: cdr -> 
           car*2 :: innerfunct cdr
       innerfunct m
   

2. 知道m是不可变的，我们就可以摆脱printfn。如果需要，我们可以将它放在函数之外，任何我们可以访问列表的地方。它总是会打印相同的。

3. 最后，我们还将对列表的引用设为不可变，并获得第二个(中间)解决方案:

   let multiply m =
       let rec innerfunct = function
       | [] -> []
       | car :: cdr -> car*2 :: innerfunct cdr
       innerfunct m
   
   let a = [1; 3; 4]
   printfn "%A" a
   let multiplied = multiply a
   printfn "%A" multiplied
   

4. 也可以乘以不同的值(该函数毕竟称为 multiply 而不是 double)。另外，既然 innerfunct 这么小，我们可以让名称匹配小范围(范围越小，名称越短):

   let multiply m xs =
       let rec inner = function
       | [] -> []
       | x :: tail -> x*m :: inner tail
       inner xs
   

   请注意，我将因素放在首位，列表放在最后。这类似于其他 List 函数，并允许使用部分应用程序创建预先自定义的函数:

   let double = multiply 2
   let doubled = double a
   

5. 现在剩下的就是使 multiply 尾递归:

   let multiply m xs =
       let rec inner acc = function
       | [] -> acc
       | x :: tail -> inner (x*m :: acc) tail
       inner [] xs |> List.rev
   

所以我们最终得到了(出于教育目的)let multiply' m = List.map ((*) m)

的硬编码版本