Trying to write a function for Ecma/JASON representation type

Question

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

I have this type definition for Ecma. I'm trying to write a function " pathList : Ecma -> Path list" that will get all the names in the ecma such that if we are given

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]
    ]

then the output is

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

I have many many versions of a recursive function that's basically the same, the best one is

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))
    | _ -> []`

Yet the output is

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

I tried filtering, which wasn't any better, I feel like I should use fold or even better catamorphisms, yet I am not sure how and I am just stuck here going in circles basically. I am also starting to doubt my definition of the type, maybe I should have defined the array or the object recursively, using the "and" keyword

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

like this? Thanks in advance!

Answer 1

There are definitely multiple ways of doing this, but I think a lot of the complexity in your code comes from trying to handle the Object and Array case by decomposing the list of fields / array of elements at the same time as you pattern match on the type of node.

It gets easier if you handle this in two steps - first pattern match and then do some kind of iteration over the elements. You can do this quite nicely by using a list comprehension (because then you just need to iterate over the elements and yield, rather than worrying about how to collect the generated paths):

Another trick is to keep the prefix path - i.e. the path visited so far - in a parameter of the recursive function:

let rec listPaths prefix e = 
  [ match e with
    | Object(fields) ->             
        for n, v in fields do 
          yield prefix @ [n]
          yield! listPaths (prefix @ [n]) v
    | Array(elements) -> 
        for e in elements do 
          yield! listPaths prefix e
    | _ -> () ]

listPaths [] v1