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:
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?