Quelles sont les questions en suspens dans les structures de données purement fonctionnelles?

51

Cette question s'inspire d' une autre question sur les nouveautés du PFDS depuis la publication du livre d'Okasaki en 1998 .

Je vais commencer par deux questions que j'ai:

  • Existe-t-il une structure de données d'ensemble purement fonctionnelle qui approche la vitesse des tables de hachage? Les essais ne sont pas encore là.
  • Existe-t-il des doigts purement fonctionnels avec O (1) append? Le meilleur à ce jour est O (lg lg n), conçu par Kaplan et Tarjan.

Quels autres problèmes de structure de données purement fonctionnels sont ouverts?

big-list ds.data-structures functional-programming jbapple
la source
Je suppose que vous entendez des tentatives comme dans les arbres de hachage plutôt que les dictionnaires plus généraux avec des clés qui sont des séquences? FWIW, je pense qu’il est impossible d’approcher la bonne vieille table de hachage ici.
Jon Harrop

Réponses:

19

Je vais interpréter la question un peu libéralement. Pour les structures de données de style Okasaki, la mémorisation est une forme de mutation implicite qui a un effet secondaire sur le temps d'exécution. Je poserai donc la question concernant les structures de données persistantes au sens strict plutôt que les structures de données avec une implémentation purement fonctionnelle, qui sont un sous-ensemble de la précédente. Par strict, je veux dire que vous devriez pouvoir accéder aux anciennes versions d’une structure de données sans pénalité, l’arbre des versions peut se ramifier de façon arbitraire, etc.

Dans ce contexte, je considère que la persistance d'UNION-FIND est un problème ouvert important. Il y a le papier Conchon-Filliâtre qui a été mentionné dans l'autre fil. Un intervenant a déjà évoqué un problème avec son tableau dit persistant: il n’est vraiment que semi-persistant. Mais supposons que vous le remplaciez par une table de hachage ou un autre tableau véritablement persistant qui se comporte mieux dans le pire des cas (et sans doute moyen,), mais pire dans le meilleur des cas. Cela laisse encore un problème important en suspens:

Le papier donne une preuve formelle de la correction en Coq. Mais ils ne parviennent pas à traiter la complexité amortie de manière formelle ou informelle. Il est très bien pas clair pour moi que le complexe derrière les coulisses mutation entraîne la complexité amortie attendue dans tous les cas. La dernière fois que j'ai réfléchi à la question, je me sentais un peu confiant de pouvoir construire un contre-exemple si je mettais des efforts à faire. Même si je me trompe à propos de cette dernière partie, l’absence d’une analyse appropriée est une lacune majeure; Il est clair que l'analyse classique de l'amortissement de UNION-FIND par Trajan n'est pas transférée directement.

Par Vognsen
la source
5
Un candidat pour les matrices entièrement persistantes (mais non persistantes de manière confluente) est présenté dans Essais de manière persistante pour un contrôle de version efficace . Les auteurs affirment que le ralentissement O (lg lg n) est supérieur au ralentissement O (lg lg m) de Dietz et al. Où m est le nombre d'opérations effectuées sur le réseau.
jbapple
1
J'ajouterai également que, bien que les structures amorties paresseuses d'Okasaki soient souvent beaucoup plus simples que les solutions de rechange, je ne connais aucune structure de données pouvant être mise en œuvre de cette manière et ne pouvant pas l'être également (avec les mêmes délais, mais pire des cas) de manière véritablement fonctionnelle.
jbapple
12

Quels autres problèmes de structure de données purement fonctionnels sont ouverts?

En voici un:

Quel est l'équivalent purement fonctionnel d'une table de hachage faible?

Jon Harrop
la source
15
euh ... le PO a demandé des questions sans réponse, donc cela pourrait être considéré comme une réponse possible à la question du PO.
Jason S
6
Ok, je vais mordre. Qu'est-ce qu'une table de hachage faible?
Jeffε
4
C'est une table de hachage qui permet à ses éléments d'être collectés si seulement elle (et d'autres cartes faibles) en font référence.
Havvy
3
@JonHarrop: il est facile de prouver qu'une version pure d'une référence faible est impossible, car des références faibles rendent la sémantique du langage non déterministe et les langages purement fonctionnels sont déterministes. Si vous marquez également le non-déterminisme dans le type, l'implémentation habituelle fonctionne. Vous avez besoin de types dépendants (pour prouver qu'une implémentation donne les mêmes réponses quel que soit le contenu de la référence) si vous souhaitez masquer l'effet en toute sécurité.
Neel Krishnaswami
5
@ NeelKrishnaswami, je ne pense pas que ce soit le cas. Vous pouvez créer des structures de données faibles qui ne créent pas de non-déterminisme, telles qu'une table faible qui ne prend pas en charge l'énumération (ou le comptage). Voir wiki.ecmascript.org/doku.php?id=harmony:weak_maps pour un exemple.
Sam Tobin-Hochstadt le