4 ms·
Linked Trees in a functional language
I'm reading the first paragraph of https://johnazariah.github.io//blog/2017/12-23-fun-with-trees/index.html
But I believe that parent linked trees are really needed in real world e.g. to get the path of a node. I think this use case is missing. There must be a simple sort of link to the parent tags.
I'd suggest
type Tags<'a> = {
Tag : 'a
ParentTag : Tags<'a> option
}
type Tree<'a> = {
Tags : Tags<'a>
Children : Tree<'a> list
}
With the path helper
let rec getPath (node:Tags<'a>) : 'a list =
match node.ParentTag with
| None -> [node.Tag]
| Some parent ->
List.append (getPath parent) [node.Tag]
What's your opinion? Thanks
- dozzie 9y ago> But I believe that parent linked trees are really needed in real world e.g. to get the path of a node. Yeah, it would be about that: belief. You can remember the path to the root when descending, so the parent node is not really necessary.
- giuliohome 9y agoFor example I develop software for trading applications. Let's say I have a trade with its portfolio (an attribute). I want to get the full path of such portfolio (see it like a floder/filename tree structure). I'm not descending anything, I just need backward propagation... And also I don't want to "remember" the parent path (let's say a long string) by duplicating it in memory for each of its children...
- giuliohome 9y agoNotice that you can add all the content, with whatever non-unique attribute inside the Tags type; plus the link to access the parent's parent content and so on... by reproducing the whole tree structure backwards Finally consider that getPath is not doing a lookup by id but it is really directly accessing the parent node content and up to the root, immediately. What you can't do this way is that you can't go through the other children of the parent (and all the rest of the tree structure that is not straight up in the hierarchy), but that's another story: it would need another use case to be introduced and discussed - in the first place