Listes de différences dans la programmation fonctionnelle

La question Quoi de neuf dans les structures de données purement fonctionnelles depuis Okasaki? , et la réponse épique de jbapple, mentionnant l'utilisation de listes de différences dans la programmation fonctionnelle (par opposition à la programmation logique), ce qui m'a récemment intéressé. Cela m'a amené à trouver l' implémentation de la liste de différences pour Haskell. J'ai deux questions (pardonnez-moi / corrigez-moi si je devais leur poser deux questions différentes sur le StackExchange).

La question simple est: est-ce que quelqu'un est au courant de la considération académique des listes de différences dans la programmation fonctionnelle et / ou les implémentations en plus de celle de la bibliothèque Haskell? La réponse de jbapple n'a pas donné de citation pour les listes de différences (les listes de différences dans la programmation logique existent dans l'histoire et dans quelques sources que j'ai Around Here Somewhere (TM)). Avant de trouver l'implémentation Haskell, je ne savais pas que l'idée était passée de la logique à la programmation fonctionnelle. Certes, les listes de différences Haskell sont une sorte d'utilisation naturelle des fonctions d'ordre supérieur et fonctionnent assez différemment de celles de la programmation logique, mais l'interface est certainement similaire.

La chose la plus intéressante (et la plus floue) que je voulais poser est de savoir si la limite supérieure asymptotique revendiquée pour la bibliothèque de listes de différences Haskell susmentionnée semble correcte / plausible. Ma confusion peut être due au fait que je manque quelque chose d'évident sur le raisonnement de la complexité avec la paresse, mais les limites revendiquées n'ont de sens pour moi que si la substitution sur une grande structure de données (ou formation de fermeture, ou recherche de variable, ou quelque chose ) prend toujours un temps constant. Ou le "catch" est-il simplement qu'il n'y a pas de limite sur le temps d'exécution pour "head" et "tail" précisément parce que ces opérations peuvent avoir à labourer une pile arbitraire de calculs / substitutions différés?

Ou est-ce que le "catch" est simplement qu'il n'y a pas de limite sur le temps d'exécution pour "head" et "tail" précisément parce que ces opérations peuvent avoir à labourer une pile arbitraire de calculs / substitutions différés?

$\Theta(m)$$m$

$O(1)$ fromList

{-# LANGUAGE NoMonomorphismRestriction #-}

data DL a = Id
          | Cons a
          | Compose (DL a) (DL a)

fromList [] = Id
fromList (x:xs) = Compose (Cons x) (fromList xs)

toList x = help x []
    where help Id r = r
          help (Cons a) r = a:r
          help (Compose f g) r = help f $ help g r

empty = Id

singleton = Cons

cons x = append (singleton x)

append = Compose

snoc xs x = append xs (singleton x)

$\Theta(n)$headtail[a] -> [a]toList

Oui, les limites dépendent de l'hypothèse selon laquelle la composition des fonctions prend un temps constant. Fondamentalement, si vous avez une liste de jointures:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

Il est évident que la concaténation est un temps constant, et qu'il est $O(n)$pour en faire une contre-liste. Si vous pensez à la représentation habituelle des fermetures, vous pouvez voir que c'est fondamentalement la même représentation de pointeur que la représentation habituelle des types de données. (Alternativement, vous pouvez afficher ce type comme une liste de différences fonctionnalisée.)