尾递归映射 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

我遇到了两个错误，但我怀疑它们是唯一的问题。

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

和

这个表达式是一个函数值，即缺少参数。它的类型是“一个列表 -> 单元”。因为当我打电话给 length a。

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

将 *2 映射到列表吗

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

Answer 1

您在匹配语句中创建的符号是不可变的，因此当您与 (car::cdr) 匹配时，您不能更改它们的值。

标准的功能方式是生成一个包含计算值的新列表。为此你可以这样写：

let multiplyBy2 = List.map (fun x -> x * 2)
multiplyBy2 [1;2;3;4;5]

这本身不是尾递归（但 List.map 是）。如果您真的想更改列表的值，可以改用数组。那么你的函数将不会产生任何新的对象，只是遍历数组：

let multiplyArrayBy2 arr =
    arr
    |> Array.iteri (fun index value -> arr.[index] <- value * 2)

let someArray = [| 1; 2; 3; 4; 5 |]
multiplyArrayBy2 someArray

Answer 2

F# 是一个 'single-pass' 编译器，因此您可以预期任何编译错误都会在错误下产生级联效应。当你有一个编译错误时，关注那个单一的错误。虽然您的代码中可能有更多错误（确实如此），但后续错误也可能只是第一个错误的结果。

正如编译器所说，car 不可变，因此您可以为其赋值。

在函数式编程中，映射可以很容易地实现为递归函数：

// ('a -> 'b) -> 'a list -> 'b list
let rec map f = function
    | [] -> []
    | h::t -> f h :: map f t

然而，这个版本不是尾递归的，因为它在之前递归调用map它把头放到尾部。

您通常可以通过引入使用累加器作为结果的 'inner' 实现函数来重构为尾递归实现。这是一种方法：

// ('a -> 'b) -> 'a list -> 'b list let map' f xs = let rec mapImp f acc = function | [] -> acc | h::t -> mapImp f (acc @ [f h]) t mapImp f [] xs

这里，mapImp是在h::t情况下调用的最后一个操作。

这个实现有点低效，因为它在每次迭代中连接两个列表 (acc @ [f h])。根据要映射的列表的大小，cons 累加器然后在最后做一个反向可能更有效：

// ('a -> 'b) -> 'a list -> 'b list let map'' f xs = let rec mapImp f acc = function | [] -> acc | h::t -> mapImp f (f h :: acc) t mapImp f [] xs |> List.rev

然而无论如何，做这一切的唯一原因是为了练习，因为this function is already built-in.

在所有情况下，您都可以使用映射函数将列表中的所有元素乘以二：

> let mdouble = List.map ((*) 2);; val mdouble : (int list -> int list) > mdouble [1..10];; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

不过，通常情况下，我什至不关心显式定义这样的函数。相反，您可以内联使用它：

> List.map ((*) 2) [1..10];; val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

上面所有的地图功能都可以用同样的方法使用。

Answer 3

如果不显示中间代码，我无法轻易解释许多问题，因此我将尝试完成注释重构：

首先，我们将沿着可变路径前进:

由于 F# 列表是不可变的，原始 ints 也是如此，我们需要一种方法来改变列表中的内容：
```
let mutable a = [ref 1; ref 3; ref 4]
```

去掉多余的ax，稍微整理一下案例，我们可以利用这些参考单元格：

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

我们看到，乘法只调用了它的内部函数，所以我们得到第一个解决方案：
```
let rec multiply m =
    match m with
    | [] -> printfn "%A" m
    | car :: cdr ->
        car := !car*2
        multiply cdr
```
^{这真的只是为了它自己的目的。如果您想要可变性，请使用数组和传统的 for 循环。}

然后，我们沿着不变的路径往上走：

正如我们在可变世界中了解到的那样，第一个错误是由于 car 不是可变的。它只是一个不可变列表中的原始 int。生活在一个不变的世界中意味着我们只能从我们的输入中创造出新的东西。我们想要的是构造一个新列表，以 car*2 作为头部，然后递归调用 innerfunct 的结果。像往常一样，一个函数的所有分支都需要 return 一些相同类型的东西：
```
let multiply m =
    let rec innerfunct = function
    | [] ->
        printfn "%A" m
        []
    | car :: cdr -> 
        car*2 :: innerfunct cdr
    innerfunct m
```
知道m是不可变的，我们可以去掉printfn。如果需要，我们可以将它放在函数之外，我们可以访问列表的任何地方。它将始终打印相同的内容。

我们还通过使对列表的引用不可变来完成并获得第二个（中间）解决方案：

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

乘以不同的值可能会更好（毕竟该函数称为 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
```

现在剩下的就是使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)

的硬编码版本

尾递归映射 f#

Tail Recursive map f#

f#

tail-recursion

map-function