F#有循环退出语句吗？

Question

我知道递归函数在F#中是一种强大的技术。我的问题是：是否有退出语句可以像命令式语言一样跳出递归函数？例如，将一个节点插入到二叉树中。

type Tree<'a> when 'a :> IComparable<'a> =
           | Nil
           | Leaf of 'a
           | Node of Tree<'a> * 'a * Tree<'a>

let tt2 = Node(
              Node(Leaf "D", "B",Node(Leaf "G", "E", Leaf "H" )),
              "A",
              Node(Nil, "C", Node(Nil, "F", Leaf "I")))

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> if x.CompareTo(y) = 0 then true else false
    | Node(l, y, r) -> 
         match l, y, r with
             | l, y, Nil -> if x.CompareTo(y) = 0 then true else contains x  l
             | Nil,y, r -> if x.CompareTo(y) = 0 then true else contains x r 
             | _ -> if x.CompareTo(y) = 0 then true
                    else contains x r |>ignore
                         contains x l

let xx = contains "C"  tt2  //It is wrong answer.

- dagelee

Answer 1

是否有一个退出语句，可以像命令式语言一样跳出递归函数。

没有。原因是你可以通过递归函数和模式匹配来编码命令式的break/return语句。如果你想要中断，只需返回一个值，否则调用另一个递归调用。

这个问题更适合问高阶函数。当你需要在高阶函数中进行早期退出时，编写自定义的递归函数是正确的方法。如果你对F#中的命令式构造感兴趣，请看看@Tomas的优秀系列。

当条件确定时，您的函数将在某个分支处退出。唯一的问题是您不应该在倒数第二行舍弃contain x r。

为了清晰起见，您可以删除多余的if/else语句。

let rec contains (x : #IComparable<'a>) = function
    | Nil -> false
    | Leaf y -> x.CompareTo(y) = 0
    | Node(l, y, r) -> 
         match l, y, r with
         | l, y, Nil -> x.CompareTo(y) = 0 || contains x l
         | Nil,y, r -> x.CompareTo(y) = 0 || contains x r 
         | _ -> x.CompareTo(y) = 0 || contains x l || contains x r

- pad

---

感谢提到该系列 :-) 不过需要注意的是这样做会影响性能- 因此仅在您关心表现力的 DSL 类代码中使用更为有用，而不是低级函数实现。 - Tomas Petricek

没错，当性能至关重要时，应该选择自定义递归函数。 - pad