Adventures in Recursion

#1

I’m trying to write code in Dhall that takes a tree of objects and turns them into a flat list where every object just references the other objects by unique names. For this example, assume I want to go from this tree:

tree

To a list:

[
  { gid = "root_leaf", references = [] },
  { gid = "root_middle_leaf", references = [] }, 
  { gid = "root_middle", references = ["root_middle_leaf"] }, 
  { gid = "root", references = [ "root_leaf", "root_middle" }
]

The high-level goal is that the list is flat and that names are unique.

To do represent the initial tree, I’m using the recursive construction suggested in the FAQ:

let GenericObject = Ξ»(ref : Type) β†’ { gid : Text, references : List ref }

let Object
    : Type
    = βˆ€(Object : Type) β†’ βˆ€(MakeObject : GenericObject Object β†’ Object) β†’ Object

-- An example tree of objects
let example
    : Object
    =   Ξ»(Object : Type)
      β†’ Ξ»(MakeObject : GenericObject Object β†’ Object)
      β†’ MakeObject
          { gid = "root"
          , references =
            [ MakeObject { gid = "leaf", references = [] : List Object }
            , MakeObject
                { gid = "middle"
                , references =
                      [ MakeObject
                          { gid = "leaf"
                          , references = [] : List Object
                          }
                      ]
                    : List Object
                }
            ]
          }

So far so good. To flatten the tree, I’m using the following code:

let concat = http://prelude.dhall-lang.org/List/concat

let map = http://prelude.dhall-lang.org/List/map

-- Remember which children are transitive children and which child is
-- directly under the current node.
let FlattenType
    : Type
    = { indirect : List (GenericObject Text), direct : GenericObject Text }

let squash = Ξ»(f : FlattenType) β†’ f.indirect # [ f.direct ]

let allDirectRef = map FlattenType Text (Ξ»(f : FlattenType) β†’ f.direct.gid)

let allChildren =
        Ξ»(fl : List FlattenType)
      β†’ concat
          (GenericObject Text)
          (map FlattenType (List (GenericObject Text)) squash fl)

let flatten
    : Object β†’ FlattenType
    =   Ξ»(x : Object)
      β†’ x
          FlattenType
          (   Ξ»(p : { references : List FlattenType, gid : Text })
            β†’ { direct =
                  { gid = p.gid
                  , references = allDirectRef p.references : List Text
                  }
              , indirect = allChildren p.references : List (GenericObject Text)
              }
          )

in  {
    flattened = squash (flatten example)
}

This works as expected:

{ flattened =
  [ { gid = "leaf", references = [] : List Text }
  , { gid = "leaf", references = [] : List Text }
  , { gid = "middle", references = [ "leaf" ] }
  , { gid = "root", references = [ "leaf", "middle" ] }
  ]
}

Now the remaining problem is to prefix all child nodes with their parent’s name, but for the life of me I can’t get this written down.

Can anyone help? :slight_smile:

#2

@blitz: Is this what you mean?

{ flattened =
  [ { gid = "leaf", references = [] : List Text }
  , { gid = "leaf", references = [] : List Text }
  , { gid = "middle", references = [ "middle-leaf" ] }
  , { gid = "root", references = [ "root-leaf", "root-middle" ] }
  ]
}

… because that can be done like this:

let GenericObject = Ξ»(ref : Type) β†’ { gid : Text, references : List ref }

let Object
    : Type
    = βˆ€(Object : Type) β†’ βˆ€(MakeObject : GenericObject Object β†’ Object) β†’ Object

let example
    : Object
    =   Ξ»(Object : Type)
      β†’ Ξ»(MakeObject : GenericObject Object β†’ Object)
      β†’ MakeObject
          { gid = "root"
          , references =
            [ MakeObject { gid = "leaf", references = [] : List Object }
            , MakeObject
                { gid = "middle"
                , references =
                  [ MakeObject { gid = "leaf", references = [] : List Object } ]
                }
            ]
          }

let concat = http://prelude.dhall-lang.org/List/concat

let map = http://prelude.dhall-lang.org/List/map

let FlattenType
    : Type
    = { indirect : List (GenericObject Text), direct : GenericObject Text }

let squash = Ξ»(f : FlattenType) β†’ f.indirect # [ f.direct ]

let allDirectRef = map FlattenType Text (Ξ»(f : FlattenType) β†’ f.direct.gid)

let allChildren =
        Ξ»(fl : List FlattenType)
      β†’ concat
          (GenericObject Text)
          (map FlattenType (List (GenericObject Text)) squash fl)

let flatten
    : Object β†’ FlattenType
    =   Ξ»(x : Object)
      β†’ x
          FlattenType
          (   Ξ»(p : { references : List FlattenType, gid : Text })
            β†’ { direct =
                  { gid = p.gid
                  , references =
                      map
                        Text
                        Text
                        (Ξ»(child : Text) β†’ "${p.gid}-${child}")
                        (allDirectRef p.references)
                  }
              , indirect = allChildren p.references
              }
          )

in  { flattened = squash (flatten example) }

The relevant change I made was:

@@ -47,6 +47,10 @@
             β†’ { direct =
                   { gid = p.gid
                   , references =
+                      map
+                        Text
+                        Text
+                        (Ξ»(child : Text) β†’ "${p.gid}-${child}")
                         (allDirectRef p.references)
                   }
               , indirect = allChildren p.references
#3

In order to get the output you mention at the start, what we need is a way to get the path through the tree so far in order to construct the full gid of each node. To do that, we do what we’d do in Haskell: pass the path so far as an extra argument to our β€œrecursive” function. In Haskell, we might do:

flatten :: Object -> [Text] -> FlattenType
flatten = ...

We can do the same in Dhall, the trick being that FlattenType is now a function that takes a path and returns what we want.
Here is what I came up with:

let concatMap =
      http://prelude.dhall-lang.org/List/concatMap sha256:3b2167061d11fda1e4f6de0522cbe83e0d5ac4ef5ddf6bb0b2064470c5d3fb64

let concatSep =
      http://prelude.dhall-lang.org/Text/concatSep sha256:e4401d69918c61b92a4c0288f7d60a6560ca99726138ed8ebc58dca2cd205e58

let map =
      http://prelude.dhall-lang.org/List/map sha256:dd845ffb4568d40327f2a817eb42d1c6138b929ca758d50bc33112ef3c885680

let Path = List Text

let appendPath
    : Text β†’ Path β†’ Path
    = Ξ»(x : Text) β†’ Ξ»(path : Path) β†’ path # [ x ]

let FlattenTypeOutputElem = { path : Path, references : List Path }

let FlattenTypeOutput =
      { indirect : List FlattenTypeOutputElem, direct : FlattenTypeOutputElem }

let FlattenType = βˆ€(path : Path) β†’ FlattenTypeOutput

let squash
    : FlattenTypeOutput β†’ List FlattenTypeOutputElem
    = Ξ»(f : FlattenTypeOutput) β†’ [ f.direct ] # f.indirect

let flattenAux
    : Object β†’ FlattenType
    =   Ξ»(x : Object)
      β†’ x
          FlattenType
          (   Ξ»(p : { gid : Text, references : List FlattenType })
            β†’ Ξ»(path : Path)
            β†’ let refs
                  : List FlattenTypeOutput
                  = map
                      FlattenType
                      FlattenTypeOutput
                      (Ξ»(child : FlattenType) β†’ child (appendPath p.gid path))
                      p.references
              
              in  { direct =
                      { path =
                          appendPath p.gid path
                      , references =
                          map
                            FlattenTypeOutput
                            Path
                            (Ξ»(x : FlattenTypeOutput) β†’ x.direct.path)
                            refs
                      }
                  , indirect =
                      concatMap
                        FlattenTypeOutput
                        FlattenTypeOutputElem
                        squash
                        refs
                  }
          )

let pathToText = concatSep "-"

let flatten
    : Object β†’ List { gid : Text, references : List Text }
    =   Ξ»(x : Object)
      β†’ map
          FlattenTypeOutputElem
          { gid : Text, references : List Text }
          (   Ξ»(x : FlattenTypeOutputElem)
            β†’ { gid =
                  pathToText x.path
              , references =
                  map Path Text pathToText x.references
              }
          )
          (squash (flattenAux x ([] : Path)))

in  flatten example

Output:

[ { gid = "root", references = [ "root-leaf", "root-middle" ] }
, { gid = "root-leaf", references = [] : List Text }
, { gid = "root-middle", references = [ "root-middle-leaf" ] }
, { gid = "root-middle-leaf", references = [] : List Text }
]
1 Like
#4

Using a function to pass the paths along the recursion seems to do the trick. Given that mixing both concerns (flattening and name prefixing) into one function makes the code look pretty intimidating, I wrote a function that only prefixes the names:

let PrefixType = βˆ€(prefix : Text) β†’ Object

let prefixNames
    : Object β†’ PrefixType
    =   Ξ»(x : Object)
      β†’ x
          PrefixType
          (   Ξ»(p : { references : List PrefixType, gid : Text })
            β†’ Ξ»(prefix : Text)
            β†’ Ξ»(IObject : Type)
            β†’ Ξ»(MakeObject : GenericObject IObject β†’ IObject)
            β†’ let newPrefix = prefix ++ p.gid

              in  MakeObject
                    { gid = newPrefix
                    , references =
                        map
                          PrefixType
                          IObject
                          (   Ξ»(child : PrefixType)
                            β†’ child (newPrefix ++ "_") IObject MakeObject
                          )
                          p.references
                    }
          )

With my original flatten function I now get:

squash (flatten (prefixNames example ""))

which results in exactly what I want. Nice!

Thanks @Nadrieril and @Gabriel439 !

2 Likes