如何实现F#中Ecma类型的路径提取函数pathList？

定义的Ecma类型 #

我定义了以下Ecma类型：

type Name = string
type Path = Name list
type Ecma =
    | Number of float
    | String of string
    | Boolean of bool
    | Null
    | Array of Ecma list
    | Object of (Name * Ecma) list

需求说明 #

需要编写一个函数pathList : Ecma -> Path list，用于提取Ecma结构中的所有名称路径。

测试实例与期望输出 #

给定测试实例：

let v1 =
    Object [
        "abc", Boolean false
        "xs", Array [
            Object ["a", String "a"]
            Number 1.0
            Boolean true
            Object ["b", String "b"]
            Boolean false
        ]
        "xyz", Object [
            "a", Number 1.0
            "b", Object ["b", String "b"]
        ]
        "ws", Array [Boolean false]
    ]

期望输出为：

[
  [];
 ["abc"];
["xs"];
["xs"; "a"];
["xs"; "b"];
 ["xyz"];
 ["xyz"; "a"];
 ["xyz"; "b"];
 ["xyz"; "b"; "b"];
 ["ws"]
  ]

尝试的实现及问题 #

我尝试了如下递归函数实现：

let checkArray e =
    match e with
    | Array _ -> true
    | _ -> false 

let checkObj e =
    match e with
    | Object _ -> true
    | _ -> false 

let rec listPaths e : Path list=
    match e with
    | Object ((name, ecma) :: t) -> [[name]] @ ( (if (checkArray ecma  || checkObj ecma ) then (name :: (List.concat (listPaths ecma)) ) else [])) :: (listPaths (Object t))
    | Array (h ::t) -> listPaths h @ (listPaths (Array t))
    | _ -> []

但实际输出不符合预期：

[abc]
[]
[xs]
[xs, a, b]
[xyz]
[xyz, a, b, b, b]
[ws]
[ws]

我尝试过过滤但效果不佳，考虑使用fold或范畴论中的catamorphisms优化，但不知如何实现。同时我也在怀疑是否应该像以下示例一样，用and关键字递归定义类型：

type FileSystemItem =
    | File of FileInfo
    | Directory of DirectoryInfo
and FileInfo = {name:string; fileSize:int}
and DirectoryInfo = {name:string; dirSize:int; subitems:FileSystemItem list}

解决方案 #

核心思路 #

要正确提取所有路径，需要跟踪当前路径前缀，递归遍历每个节点时，将当前名称添加到前缀中，收集所有生成的路径（包括当前节点自身的路径）。原实现的问题在于没有正确处理路径前缀的传递，导致路径拼接错误。

另外，你的原始Ecma类型定义无需修改，不需要用and关键字，因为类型之间没有相互依赖的递归关系。

正确实现代码 #

let rec pathList (root: Ecma) : Path list =
    // 辅助函数：带当前路径前缀的遍历
    let rec traverse prefix e =
        match e with
        | Object props ->
            // 先收集当前对象自身的路径（前缀）
            let selfPath = [prefix]
            // 遍历每个属性，生成属性路径 + 子路径
            let propPaths = 
                props
                |> List.collect (fun (name, value) ->
                    let propPrefix = prefix @ [name]
                    // 属性自身的路径 + 子节点的所有路径
                    [propPrefix] @ traverse propPrefix value)
            selfPath @ propPaths
        | Array items ->
            // 遍历数组中的每个元素，收集所有子路径
            items |> List.collect (traverse prefix)
        // 基础类型没有子路径，仅返回空列表
        | Number _ | String _ | Boolean _ | Null -> []
    
    // 根节点的路径是空列表，从空前缀开始遍历
    traverse [] root

测试验证 #

将上述函数应用到v1，会得到预期的输出：

[
    [];
    ["abc"];
    ["xs"];
    ["xs"; "a"];
    ["xs"; "b"];
    ["xyz"];
    ["xyz"; "a"];
    ["xyz"; "b"];
    ["xyz"; "b"; "b"];
    ["ws"]
]

实现说明 #

1. 辅助函数traverse：接收当前路径前缀和当前节点，返回所有从该节点出发的子路径。
2. Object处理：
   • 首先添加当前对象的路径（即传入的前缀）。
   • 对每个属性，生成新的前缀（原前缀 + 属性名），添加该属性的路径，再递归遍历属性值收集子路径。
3. Array处理：遍历数组中的每个元素，直接传递当前前缀，收集所有子路径（数组元素本身没有名称，所以不会添加新的路径节点）。
4. 基础类型处理：基础类型没有子节点，返回空列表。

优化思路（使用Fold） #

如果想用fold重构，可以将遍历过程中的路径收集用fold实现，核心逻辑不变：

let rec pathList (root: Ecma) : Path list =
    let rec traverse prefix e =
        match e with
        | Object props ->
            let self = [prefix]
            let propsPaths =
                props
                |> List.fold (fun acc (name, value) ->
                    let newPrefix = prefix @ [name]
                    acc @ [newPrefix] @ traverse newPrefix value) []
            self @ propsPaths
        | Array items ->
            items |> List.fold (fun acc item -> acc @ traverse prefix item) []
        | _ -> []
    traverse [] root

Catamorphisms（范畴论优化） #

如果想用范畴论中的catamorphisms（即折叠递归类型），可以先定义Ecma类型的代数结构，然后编写折叠函数：

// 定义Ecma的F代数
type EcmaF<'a> =
    | NumberF of float
    | StringF of string
    | BooleanF of bool
    | NullF
    | ArrayF of 'a list
    | ObjectF of (Name * 'a) list

// 定义从Ecma到EcmaF的映射
let rec project (e: Ecma) : EcmaF<Ecma> =
    match e with
    | Number f -> NumberF f
    | String s -> StringF s
    | Boolean b -> BooleanF b
    | Null -> NullF
    | Array es -> ArrayF es
    | Object props -> ObjectF props

// 定义catamorphism函数
let cata (f: EcmaF<'a> -> 'a) (e: Ecma) : 'a =
    let rec loop e = f (project e |> function
        | ObjectF props -> ObjectF (props |> List.map (fun (n, e) -> (n, loop e)))
        | ArrayF es -> ArrayF (es |> List.map loop)
        | other -> other)
    loop e

// 使用catamorphism实现pathList
let pathListCata (root: Ecma) : Path list =
    let folder (prefix: Path) (ef: EcmaF<Path list>) : Path list =
        match ef with
        | ObjectF props ->
            let self = [prefix]
            let propPaths =
                props
                |> List.collect (fun (name, paths) ->
                    let newPrefix = prefix @ [name]
                    [newPrefix] @ paths)
            self @ propPaths
        | ArrayF pathLists ->
            pathLists |> List.collect id
        | _ -> []
    
    // 部分应用前缀，然后传入cata
    let cataFolder = folder []
    cata cataFolder root

这种方式更符合函数式编程的抽象风格，但对于简单场景，基础递归实现已经足够清晰。

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