Можно ли создать дерево на F#, где каждый узел также знает своего родителя?

Обычный тип дерева выглядит примерно так

type Tree<'LeafData,'INodeData> =
   | LeafNode of 'LeafData
   | InternalNode of 'INodeData * Tree<'LeafData,'INodeData> seq

Можно ли использовать древовидный тип, который можно было бы использовать чисто функционально, но при этом предоставляющий доступ к родительскому элементу каждого узла?

F# поддерживает рекурсивную инициализацию значений с помощью let rec, но я нахожу это странной функцией, и вместо этого я бы использовал обычные классы с активными шаблонами.

JL0PD 19.12.2022 04:22

Вы можете определить лес вершин, которые знают своих родителей, следующим образом: type Vertex<'a> = { Parent : Vertex<'a> option; Data : 'a }. Вероятно, это не то, что вы имеете в виду, но если вам нужны деревья с двусторонней связью, это будет более громоздко. В ФП это не нормально. Вероятно, есть лучшее решение, но трудно сказать... Какую проблему вы пытаетесь решить?

Mark Seemann 19.12.2022 07:18

@MarkSeemann спасибо за ваше предложение. Вопрос возник при попытке решить загадку седьмого дня появления кода в 2022 году. Речь идет о навигации и управлении виртуальной файловой системой. Команда «cd ..» должна изменить текущий узел на родительский, и я искал эффективный способ сделать это, сохраняя при этом неизменным код.

Hans Wurst 19.12.2022 08:25

Обычно вы можете «пропустить» переменную «состояние» (здесь неизменный стек каталогов) через алгоритм. См., например. моя статья Recurse для ознакомления с концепцией.

Mark Seemann 19.12.2022 09:51

@MarkSeemann спасибо за ссылку. С этой информацией я мог бы придумать что-то, что позволило бы мне узнать родительский узел текущего узла, но как это поможет обновить родительский узел — скажем, для «cd ..» и добавить новый файл? Мне все равно пришлось бы искать родительский узел из корня дерева, но вместо того, чтобы пытаться найти узел, у которого текущий узел является дочерним, я мог бы искать узел (родительский) напрямую. Не большая разница?

Hans Wurst 19.12.2022 10:52

В этом году я занимался Advent of Code в Python, поэтому использовал изменяемый стек, представляющий «текущий» каталог, и цикл for, но, как я уже писал, эквивалентная функция заключается в передаче неизменяемого стека в качестве аргумента, который вы может манипулировать. Когда вы cd попадаете в каталог, помещайте его в стек. Когда вы cd .., вытащите стопку.

Mark Seemann 19.12.2022 13:24

Использование метода стека вместо построения дерева кажется отличной идеей. Спасибо за указатель.

Hans Wurst 19.12.2022 15:00
Введение в одну из самых важных концепций в React - функциональное программирование
Введение в одну из самых важных концепций в React - функциональное программирование
React разработан с использованием концепции функционального программирования, поэтому понимание функционального программирования важно для изучения...
Фото ️🔁 Radek Jedynak 🔃 on ️🔁 Unsplash 🔃
Фото ️🔁 Radek Jedynak 🔃 on ️🔁 Unsplash 🔃
Что такое Java 8 Streams API? Java 8 Stream API
1
7
77
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Да и нет.

В чисто функциональном плане лучше всего поискать "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.Коллекции.Экспериментальная

Это отличная статья. Спасибо за ссылку. Не могли бы вы прокомментировать, как будет выглядеть застежка-молния для небинарного дерева?

Hans Wurst 19.12.2022 08:20

Я добавил еще несколько ссылок ... но, не ломая голову в течение часа и не вспоминая, как вывести эти вещи (это довольно механически), я не могу найти ничего прямого. Если вы знаете ocaml/haskell, вы, вероятно, можете найти пример где-нибудь в Google "застежка-молния розового дерева"

MrD at KookerellaLtd 19.12.2022 14:32

Другие вопросы по теме