将递归函数从 3 个子句简化为 2 个子句

Question

我正在用 F# 做一些练习，我有这个计算交替总和的函数：

let rec altsum = function
    | []         -> 0
    | [x]        -> x
    | x0::x1::xs -> x0 - x1 + altsum xs;; 

val altsum : int list -> int

练习内容是只用两个子句声明相同的函数...但是如何做到这一点？

Answer 1

要减少案例数，您需要将算法移回到更接近原始问题的位置。问题是要否定交替值，所以这就是您的解决方案应该做的。

let altsum lst =
  let rec altsumRec lst negateNext =
    match lst with
    | [] -> 0
    | head::tail -> (if negateNext then -head else head) + altsumRec tail (not negateNext)
  altsumRec lst false

Answer 2

mydogisbox 的答案是正确的，有效！

但经过一些尝试，我找到了一个最小且可读的问题解决方案。

let rec altsum2 = function
| [] -> 0
| x0::xs -> x0 - altsum2 xs

例子

altsum2 [1;2;3] essentially do this:
1 - (2 - (3 - 0)

这有点棘手，但行得通！

题外话：

使用 F# List 库解决问题的另一种优雅方法是：

let altsum3 list = List.foldBack (fun x acc -> x - acc) list 0;;

在phoog的评论之后我开始尝试用尾递归函数解决问题：

let tail_altsum4 list = 
    let pl l = List.length l % 2 = 0
    let rec rt = function    
        | ([],acc) -> if pl list then -acc else acc
        | (x0::xs,acc) -> rt (xs, x0 - acc)
    rt (list,0)

这也有点棘手...减法不是可交换的，并且不可能考虑用 List.rev 一个长列表来反转...但我找到了解决方法！ :)

将递归函数从 3 个子句简化为 2 个子句

Simplify a recursive function from 3 to 2 clauses

recursion

f#