Traversing a nested record in deep

[suimong]

This should be a straightforward-enough problem but I just can't wrap my head around it, so here I am asking help from the community: How to turn a record like this:

conf0 = {
  system | doc "group" = {
    "0" | doc "section" = {
      hostname = "openwrt01",
      timezone = "UTC",
      log_size = "132",
    }
  },
  timeserver | doc "group" = {
    ntp | doc "section" = {
      enabled = 1,
      enable_server = 0,
      server = [
        "0.openwrt.pool.ntp.org",
        "1.openwrt.pool.ntp.org",
      ],
    },
    ntp2 | doc "section" = {
      enabled = 0,
      enable_server = 0,
    },
  },
},

into something like this:

[
["system", "0", "hostname", "openwrt01"],
["system", "0", "timezone", "UTC"],
["system", "0", "log_size", "132"],
["timeserver", "ntp", "enabled", "1"],
["timeserver", "ntp", "enable_server", "0"],
["timeserver", "ntp", "server", ["0.openwrt.pool.ntp.org", "1.openwrt.pool.ntp.org"]],
["timeserver", "ntp2", "enabled", "0"],
["timeserver", "ntp2", "enable_server", "0"],
]

This is not the entire input of course, but the characteristics of the input record is that the nesting depth for every top-level key is the same (in this example, the depth is 3, i.e. you need a path of exactly length 3 to get to the "value").

The use case is essentially converting a declarative configuration to a script consisting of imperative "uci set" commands.

[yannham]

Hi!

Here is a possibility: I just wrote a recursive function which traverses records and gather all leafs as an array:

let leafs
  | doc m%"
      Returns all the leafs of a record as an array of paths.

      Each element of the returned outermost array, a path, is composed of the
      consective fields that need to be traversed to reach the leaf concatened
      with the value of the leaf.

      # Examples

      ```nickel
      {
        foo = {
          bar = 1,
          baz = 2,
        },
        foobis.barbis.borg = ["hello"],
      }
      |> leafs
      ```

      gives

      ```nickel
      [
        [ "foo", "bar", 1 ],
        [ "foo", "baz", 2 ],
        [ "foobis", "barbis", "borg", [ "hello" ] ]
      ]
      ```
    "%
  | { .. } -> Array (Array Dyn)
  =
    let rec leafs_aux 
      | doc m%"
        Auxiliary variant of `leafs`.

        `leafs_aux` takes a current field path, indicating the position of the
        field being processed in the original record (represented as an array of
        strings) and the value of the field (which might or might not be a
        record). Returns the set of leafs of this field, represented as an array
        of paths.
      "%
      | Array String -> Dyn -> Array (Array Dyn) = fun path value =>
        if !(std.is_record value) then
          # If we reached a leaf, we just append the value to the current path,
          # and return an array with a single element
          [std.array.append value path]
        else
          # If the value is itself a record, we simply recurse into each field,
          # generate an array of leafs for each such field.
          value
          |> std.record.to_array
          |> std.array.map
            (
              fun { field, value } =>
                let new_path = std.array.append field path in
                leafs_aux new_path value
            )
          # Now we have an array of array of fields (each subfield might have
          # several leafs itself), so we finally flatten it
          |> std.array.flatten
      in

    leafs_aux []
  in

{
  system | doc "group" = {
      "0" | doc "section" = {
          hostname = "openwrt01",
          timezone = "UTC",
          log_size = "132",
        }
    },
  timeserver | doc "group" = {
      ntp | doc "section" = {
          enabled = 1,
          enable_server = 0,
          server = [
            "0.openwrt.pool.ntp.org",
            "1.openwrt.pool.ntp.org",
          ],
        },
      ntp2 | doc "section" = {
          enabled = 0,
          enable_server = 0,
        },
    },
}
|> leafs

I think it's slightly different from yours, because you stop at a specific depth, but it shouldn't be too difficult to tune: you can just add an additional parameter to leaf and leaf_aux which is a max depth, and decrement it at each recursive call:

@@ -29,9 +29,9 @@ let leafs
       ]
       ```
     "%
-  | { .. } -> Array (Array Dyn)
+  | std.number.Nat -> {..} -> Array (Array Dyn)
   =
-    let rec leafs_aux 
+    let rec leafs_aux
       | doc m%"
         Auxiliary variant of `leafs`.
 
@@ -41,8 +41,9 @@ let leafs
         record). Returns the set of leafs of this field, represented as an array
         of paths.
       "%
-      | Array String -> Dyn -> Array (Array Dyn) = fun path value =>
-        if !(std.is_record value) then
+      | Array String -> std.number.Nat -> Dyn -> Array (Array Dyn)
+      = fun path depth value =>
+        if !(std.is_record value) || depth == 0 then
           # If we reached a leaf, we just append the value to the current path,
           # and return an array with a single element
           [std.array.append value path]
@@ -55,7 +56,7 @@ let leafs
             (
               fun { field, value } =>
                 let new_path = std.array.append field path in
-                leafs_aux new_path value
+                leafs_aux new_path (depth - 1) value
             )
           # Now we have an array of array of fields (each subfield might have
           # several leafs itself), so we finally flatten it
@@ -88,4 +89,4 @@ let leafs
         },
     },
 }
-|> leafs
+|> leafs 2

The second version stops at max depth depth, even if the field is yet a record.

[suimong]

As always @yannham you are amazing! I just came across an almost identical solution, but your implementation is just..textbook! It's not just the implementation, but your concise and idiomatic nickel style that made me love this project even more. Thanks!

[yannham]

Happy to help, and thank you for the kind words @suimong 🙂