Écrire des structures de données nécessitant des pointeurs/références dans Clojure?

Question

J'ai travaillé sur une base de données de jouets dans Clojure et je voulais mettre en place un arbre B +. Quand j'ai commencé à y penser, j'ai réalisé qu'il n'y avait peut-être pas moyen d'avoir quelque chose comme un pointeur/une référence aux autres nœuds de Clojure. Cela n'a pas d'importance pour quelque chose comme un BST ou beaucoup d'autres structures arborescentes puisque tout ce dont vous avez besoin est de stocker l'enfant d'un nœud. Mais qu'est-ce que je fais dans quelque chose comme un arbre B + où je dois pouvoir me référer au frère d'un nœud? Lorsque je cherchais des solutions, je suis tombé sur un article dans Google Groupes sur la façon dont vous n'implémentez pas une liste Doublement liée dans Clojure car il existe d'autres façons de faire les choses dans Clojure.

Que dois-je faire pour un arbre B +?

Answer 1

Ce n'est pas qu'il est difficile d'avoir des références aux objets dans clojure; mais généralement, ces références sont immuables. C'est l'immuabilité qui rend la liste doublement chaînée impossible, car contrairement à une liste unidirectionnelle, vous ne pouvez en changer aucune partie sans créer de mutation quelque part.

Pour voir cela, supposons que j'ai une liste chaînée,

a -> b -> c 

et suppose que je veux changer la tête de celui-ci. Je peux le faire en changeant l'intégralité de la liste. Je crée une nouvelle liste en créant une nouvelle valeur pour la valeur de la tête et de réutiliser la queue:

a'-> b -> c 

Mais listes doublement chaînées sont impossibles. Donc, dans clojure, et d'autres langages fonctionnels, nous utilisons parfois un zipper dans de telles situations. Maintenant, supposons que vous ayez vraiment besoin de références mutables dans Clojure - comment le faire? Eh bien, en fonction de la sémantique dont vous avez besoin concurrency, Clojure a vars, refs, atoms, etc.

En outre, avec deftype, vous pouvez créer des objets qui ont des champs mutables, et ces champs mutables peut contenir des références à d'autres choses. Vous pouvez également utiliser des tableaux java raw dans clojure dans le même but.

Votre base de données va-t-elle être une base de données en mémoire ou une base de données sauvegardée sur disque? Si sur le disque, je pense que le problème de pointer swizzling est plus compliqué que d'avoir des références mutables. Pour en revenir à la question des structures de données fonctionnelles, je crois qu'il est possible de créer des arbres B qui ont une sémantique purement fonctionnelle. Le premier indice ici est que c'est un arbre, et les arbres sont le beurre de pain et la viande de structures de données fonctionnelles. Deuxièmement, notez qu'il existe des bases de données qui fonctionnent uniquement en mode append - par exemple, couchDB. Cela a l'avantage que la base de données est son propre journal, dans un sens. Pour avoir une meilleure idée des coûts et avantages de cette approche, vous pouvez vouloir watch Slava Akhmechet's presentation. Son entreprise, RethinkDB, a finalement adopté une approche hybride, l'IIRC.

Answer 2

Vous pouvez regarder Chouser's finger trees dans Clojure pour voir comment la fonctionnalité d'une liste doublement liée peut être implémentée en utilisant un style fonctionnel. Alternativement, vous pouvez simplement prendre du recul et vous demander pourquoi vous croyez que B + est un bon choix de structure de données pour un langage fonctionnel.

Si vous n'êtes pas familier avec les alternatives, vous pouvez consulter le livre de Chris Okazaki "Purely Functional Data Structures."