prefixes ls = zipWith take [1 .. length ls] (repeat ls)
Yat-il un moyen de faire mieux que cela? Intuitivement, il me semble que l'on ne peut pas obtenir un algorithme en dessous de O (n²) dans un langage purement fonctionnel car soit inverser soit ajouter doit être appliqué n fois. Je ne sais pas comment le prouver, cependant.Quel est l'algorithme purement fonctionnel le plus efficace pour générer tous les préfixes d'une liste?
Je pense que vous avez raison. Il ne peut y avoir aucun partage de la colonne vertébrale de la liste car toutes les queues sont différentes. Par conséquent, la liste des préfixes, si elle est entièrement évaluée, prendrait l'espace Θ (n) complet, qui doit prendre Ω (n) temps à générer.
Notez que (une version lazier de) la fonction que vous avez écrit est disponible en Data.List en tant que inits.
Il y a une optimisation précise que vous pouvez faire. Cette équation est vérifiée:
map (foldl f z) . inits = scanl f z
Et scanl fonctionne en temps linéaire. Donc, si vous pouvez exprimer la chose que vous voulez faire à chaque préfixe comme un pli gauche, alors vous pouvez éviter la complexité quadratique de la construction de la liste des préfixes.
N'est-ce pas dépendant de la représentation? Si vous représentez des listes en tant que stockage contigu plus index de début et de fin (similaire à bytestrings), vous pouvez partager le stockage et simplement devoir parcourir une fois pour créer la liste d'index. L'algorithme ne changerait pas, juste la représentation. Pour ce cas d'utilisation particulier, l'utilisation de listes snoc (listes binaires, mais imbriquées à la fin, pas au début, de la liste) permettrait également le partage de sous-listes, n'est-ce pas?
Je pense que c'est relativement clair, que sa question cible une liste de haskell ordinaire '[]'. -1 – fuz
Cela dépend si vous regardez la syntaxe de l'exemple ou à la question comme indiqué. Compte tenu de la réponse acceptée, la limitation aux listes binaires peut avoir été prévue. Mais ce n'est pas une propriété des algorithmes purement fonctionnels, pas même de tels algorithmes dans Haskell, juste de cette représentation de liste particulière. – claus
Oui, la limitation aux listes binaires était prévue. J'aurais pu le préciser. –
+1 bonne idée avec scanl –