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

在没有显示中间代码的情况下,我无法轻易解释许多问题,因此我将尝试通过注释重构:

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

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

   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)