F#中如何传递树类型？解决contains函数列表参数匹配问题

类型定义 #

type Name = string
type Flow = int
type River = R of Name * Flow * River list
type Tributaries = River list

需求与问题 #

需要实现一个contains函数，接收参数n（河流名称）和r（河流实例），当n存在于当前河流或其任意支流中时返回true。

用户尝试的代码如下，但因支流列表Tr无法直接传入接收单个River的contains函数而报错：

let rec contains (n:Name)(r:River) =
    match r with
        |R(Name,_,_) when Name = n -> true 
        |R(_,_,Tr) -> contains n Tr
        |_ -> false

简洁解决方案 #

可以利用F#标准库的List.exists函数，遍历支流列表并对每个支流递归调用contains，只要有一个支流匹配就返回true，无需额外辅助函数：

let rec contains (n: Name) (r: River) =
    match r with
    | R(name, _, _) when name = n -> true
    | R(_, _, tributaries) -> List.exists (contains n) tributaries

代码解释 #

• 第一个匹配分支：直接判断当前河流的名称是否等于目标n，是则返回true。
• 第二个匹配分支：对支流列表使用List.exists，该函数会遍历列表中的每个River元素，对每个元素调用contains n，只要有一个调用返回true，List.exists就会整体返回true，否则返回false。
• 无需额外辅助函数，通过递归结合标准库函数实现简洁的遍历逻辑。

内容的提问来源于stack exchange，提问作者ibo a