Обычный тип дерева выглядит примерно так
type Tree<'LeafData,'INodeData> =
| LeafNode of 'LeafData
| InternalNode of 'INodeData * Tree<'LeafData,'INodeData> seq
Можно ли использовать древовидный тип, который можно было бы использовать чисто функционально, но при этом предоставляющий доступ к родительскому элементу каждого узла?
Вы можете определить лес вершин, которые знают своих родителей, следующим образом: type Vertex<'a> = { Parent : Vertex<'a> option; Data : 'a }
. Вероятно, это не то, что вы имеете в виду, но если вам нужны деревья с двусторонней связью, это будет более громоздко. В ФП это не нормально. Вероятно, есть лучшее решение, но трудно сказать... Какую проблему вы пытаетесь решить?
@MarkSeemann спасибо за ваше предложение. Вопрос возник при попытке решить загадку седьмого дня появления кода в 2022 году. Речь идет о навигации и управлении виртуальной файловой системой. Команда «cd ..» должна изменить текущий узел на родительский, и я искал эффективный способ сделать это, сохраняя при этом неизменным код.
Обычно вы можете «пропустить» переменную «состояние» (здесь неизменный стек каталогов) через алгоритм. См., например. моя статья Recurse для ознакомления с концепцией.
@MarkSeemann спасибо за ссылку. С этой информацией я мог бы придумать что-то, что позволило бы мне узнать родительский узел текущего узла, но как это поможет обновить родительский узел — скажем, для «cd ..» и добавить новый файл? Мне все равно пришлось бы искать родительский узел из корня дерева, но вместо того, чтобы пытаться найти узел, у которого текущий узел является дочерним, я мог бы искать узел (родительский) напрямую. Не большая разница?
В этом году я занимался Advent of Code в Python, поэтому использовал изменяемый стек, представляющий «текущий» каталог, и цикл for, но, как я уже писал, эквивалентная функция заключается в передаче неизменяемого стека в качестве аргумента, который вы может манипулировать. Когда вы cd
попадаете в каталог, помещайте его в стек. Когда вы cd ..
, вытащите стопку.
Использование метода стека вместо построения дерева кажется отличной идеей. Спасибо за указатель.
Да и нет.
В чисто функциональном плане лучше всего поискать "Tree Zipper" (застежки-молнии бывают всякие).
Эти чисто функциональные структуры данных позволяют вам перемещаться по структуре данных (здесь — дереву) без необходимости встраивать явную ссылку на «родителя» в саму структуру данных.
Дерево не знает своего родителя, но молния знает «путь» к определенному узлу и, следовательно, знает родителя.
обзор 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-Tree-Zipper.html
но мой haskell слишком ржавый, чтобы легко перевести это
Есть застежка-молния бинарного дерева в FSharpx.Коллекции.Экспериментальная
Это отличная статья. Спасибо за ссылку. Не могли бы вы прокомментировать, как будет выглядеть застежка-молния для небинарного дерева?
Я добавил еще несколько ссылок ... но, не ломая голову в течение часа и не вспоминая, как вывести эти вещи (это довольно механически), я не могу найти ничего прямого. Если вы знаете ocaml/haskell, вы, вероятно, можете найти пример где-нибудь в Google "застежка-молния розового дерева"
F# поддерживает рекурсивную инициализацию значений с помощью
let rec
, но я нахожу это странной функцией, и вместо этого я бы использовал обычные классы с активными шаблонами.