初尝 F# 函数式编程之 "用递归实现循环"

Author: 102419@gmail.com
Created at: 2020-12-01

原教程在这里 https://fsharpforfunandprofit.com/posts/designing-for-correctness/

但下面的内容是我在原教程的基础上自己添加的,原教程里没有下面的内容。

原教程里定义了一个类型 Cart, 但下面我们不用关心 Cart 的具体定义,只需要知道它表示一个购物车,下面我用一个列表 ["aaa"; "bbb"; "ccc"] 表示货物。

然后我想做的是,像普通编程方法的 while 或 for 循环那样,循环添加货物进购物车里。

在函数式编程中,通常用递归来实现循环,如下所示:


    let rec addItems (cart: Cart) items =
        match items with
        | [] -> cart
        | head :: tail ->
            let cartFilled = cart.Add head
            addItems cartFilled tail

    let cart = Cart.New
    let items = ["aaa"; "bbb"; "ccc"]
    let cartFilled = addItems cart items
    

初看有点复杂,但它非常直白地表达了这样一个算法:

  1. 向函数 addItems 输入两个参数:cart 和 items
  2. 如果 items 是空的,就直接原封不动返回 cart
  3. 如果 items 里面有东西,就取第一个,放进 cart 里
  4. items 除去第一个之后剩下的东西按上述 1~3 的步骤重复操作

另外,上面代码的最后两行,可以用 F# 的特性改写成这样:


    let cartFilled = ["aaa"; "bbb"; "ccc"] |> addItems cart
    

同样的功能,也可以用另一种方法来实现:


    let addItems (cart: Cart) items =
        let action (cartFilled: Cart) item = cartFilled.Add item
        match items with
        | [] -> cart
        | head :: tail -> List.fold action (cart.Add head) tail
    

上面的代码使用了 List.fold, 其实 fold 很强大,上面的代码还可以进一步简化如下:


    let action (cartFilled: Cart) item = cartFilled.Add item
    let cartFilled = List.fold action cart items
    

另外,根据具体情况,可以采用 List.filter, List.map, List.scan, List.iter, List.reduce 等,都是很常用也很好用的工具。

本文介绍了在 F# 里实现循环的几种方法,虽然没有体现 F# 或函数式编程的优势,但初学函数式通常都会有这样的疑问:不用 while 不用 for 怎样写循环?本文初步回答了这个问题。


更新,补充

在上面的代码中,到处都有 (cart: Cart) 这样显式的类型声明,经过后续的学习我发现这个有办法更优雅一些,所以回头来补充。

方法很简单,就是加一个函数 let add (cart:Cart) item = cart.Add item, 添加后代码可以简化如下:


    let add (cart:Cart) item = cart.Add item

    // 利用递归
    let rec addItems cart items =
        match items with
        | [] -> cart
        | head :: tail -> addItems (add cart head) tail

    // 或者利用 List.fold
    let cartFilled = List.fold add cart items
    

仔细看上面的代码可以发现,类型声明被集中到 add 函数里了,其他函数就可以自动推导。而且利用 List.fold 时,连 action 函数都省了,因为碰巧与 add 一样。(另外,根据 ScottW 的说法,更推荐用 List.fold 而不是递归)

使用这个小小的技巧,结果明显优雅了很多。

←← →→