尾递归的 F# map 函数

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# 相当新手，意识到我可能没有正确地调用该函数，但我想不出为什么。这主要是我的学习经验，所以解释比仅仅修复代码更重要。语法明显有误，但我能否通过执行类似于

car = car*2 然后在列表的 cdr 上调用内部函数来将 *2 映射到一个列表中。

- Sam

---

为了消除第二个错误，您需要从innerfunct定义中删除ax参数。function语句隐式地接受参数。否则，您可以阅读整个match ax with语句并保留ax参数不变。 - Bartek Kobyłecki

Answer 1

有一些问题我很难在没有展示中间代码的情况下解释清楚，因此我将尝试通过注释重构来解决：

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

1. As F# lists are immutable and so are primitive ints, we need a way to mutate that thing inside the list:

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

2. Getting rid of the superfluous ax and arranging the cases a bit, we can make use of these reference cells:

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

3. We see, that multiply only calls its inner function, so we end up with the first solution:

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

   ^{This is really only for it's own purpose. If you want mutability, use arrays and traditional for-loops.}

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

1. As we learnt in the mutable world, the first error is due to car not being mutable. It is just a primitive int out of an immutable list. Living in an immutable world means we can only create something new out of our input. What we want is to construct a new list, having car*2 as head and then the result of the recursive call to innerfunct. As usual, all branches of a function need to return some thing of the same type:

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

2. Knowing m is immutable, we can get rid of the printfn. If needed, we can put it outside of the function, anywhere we have access to the list. It will always print the same.

3. We finish by also making the reference to the list immutable and obtain a second (intermediate) solution:

   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. It might be nice to also multiply by different values (the function is called multiply after all and not double). Also, now that innerfunct is so small, we can make the names match the small scope (the smaller the scope, the shorter the names):

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

   Note that I put the factor first and the list last. This is similar to other List functions and allows to create pre-customized functions by using partial application:

   let double = multiply 2
   let doubled = double a
   

5. All that's left now is to make multiply tail-recursive:

   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)

。

- CaringDev

Answer 2

F#是一种“单次”编译器，因此您可以期望任何编译错误都会在错误下方产生级联影响。当您有编译错误时，请专注于该单个错误。虽然您的代码可能存在更多错误（确实有），但后续错误也可能只是第一个错误的结果。

就像编译器所说，car不可变，因此不能给它赋值。

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

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

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

通常可以通过引入一个使用累加器作为结果的“内部”实现函数来重构为尾递归实现。以下是一种方法：

// ('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

无论如何，做所有这些的唯一原因是为了练习，因为此函数已经内置。

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

> 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]

你可以以相同的方式使用上述所有地图函数。

- Mark Seemann

Answer 3

在匹配语句中创建的符号是不可变的，因此当您使用(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

- Bartek Kobyłecki