通常的树类型看起来像
type Tree<'LeafData,'INodeData> =
| LeafNode of 'LeafData
| InternalNode of 'INodeData * Tree<'LeafData,'INodeData> seq
是否有可能使用可以以纯功能方式使用但仍然可以访问每个节点的父节点的树类型?
是,也不是。
在纯函数设置中,最好查找"Tree Zipper"(这里有各种各样的拉链)。
这些纯功能数据结构允许你在数据结构(这里是树)中导航,而不必在数据结构本身中嵌入对'parent'的显式引用。
树不知道它的父节点,但是拉链知道特定节点的"路径",所以它知道父节点。
查看f#概览https://tomasp.net/blog/tree-zipper-query.aspx/
(在回答你的问题时,我包含了更多的链接和参考资料,但响应的大小意味着我不能确切地给你你想要的货架)
在Haskell中有一个关于拉链的描述,但不要太惊慌,它很容易理解http://learnyouahaskell.com/zippers
有一篇论文是关于使用微分来推导数据结构的——尽管它有点繁重。(下面有一节https://en.wikibooks.org/wiki/Haskell/Zippers解释了这个机制)
的
https://hackage.haskell.org/package/rosezipper - 0.2 -/- docs/data树- zipper.html
但是我的haskell太生锈了,不能很容易地翻译这个
有一个二叉树拉链FSharpx.Collections.Experimental