重新创建一个 "tree cointains element" 与折返。我不明白为什么它会起作用

Question

我试图用 Foldback 重新创建一个给定树和元素 x 的函数，如果元素在树内，它将输出 true，否则输出 false。这是我的树：

type 'a binTree =
  | Null                                     // empty tree
  | Node of 'a  * 'a binTree * 'a binTree

这是我没有折返的代码

let rec containsTreeBis bTree y =
match bTree with 
    | Null -> false
    | Node(x,left,right) -> 
        match x=y with 
            | true -> true 
            | _ -> containsTreeBis left y || containsTreeBis right y

这是我的 foldTree 函数，它将折叠应用于树：

let rec foldTree f e tree = 
match tree with
  | Null -> e
  | Node (x, left, right) ->
    f x ( foldTree f e left )  ( foldTree f e right )

他们都工作得很好。

现在进入正题。

我尝试使用 foldTree 来做同样的事情。我真的确信这是正确的代码

 let containsTreeF bTree pred = 
    foldTree ( fun y vl vr -> pred y || vl || vr ) true bTree

但是用 FsCheck 做了一些检查，结果是 Falsiable。

我随机把代码改成这样：

 let containsTreeF bTree pred = 
    foldTree ( fun y vl vr -> pred y || vl || vr ) false bTree

把最后的true改成了false。

做了FsCheck。有用。

怎么样？我没听懂。

Answer 1

您的 fold 函数已正确实现，因此问题是关于如何使用 fold 函数来检查树（或具有 fold 操作的任何对象）是否包含指定元素。

要做到这一点，你需要使用false作为初始值和逻辑or作为操作，即：

let contains x tree = 
  foldTree (fun y vl vr -> x = y || vl || vr) false tree

这将 return false 用于空树。如果任一分支包含该元素，则 true || false 将是 true，但如果分支中的 none 包含该元素，则 false || false 将导致 false.

当您将 true 作为初始值时，为什么您的 FsCheck 测试没有捕捉到这个？使用该初始值，您的函数将始终 return true，因此您可以通过查找不包含在树中的元素的测试来捕获它。

一个单元测试是：

let t = Node(1, Node(2, Null, Null), Null)
contains 7 t

使用 FsCheck，您可以使用一些随机生成的集合中的值生成树，然后检查它是否包含不在此集合中的项目。

重新创建一个 "tree cointains element" 与折返。我不明白为什么它会起作用

Re-create a "tree cointains element" with foldback. I don't understand why it's working

tree

f#

fold