Les appels 'length' sont-ils réécrits en tant qu'informations constantes par GHC?

Juste une réflexion aléatoire regardant mes nombreux appels length, il me semble que le compilateur peut certainement dire la longueur de toute liste grâce à l'immuabilité et la transparence référentielle (même lorsque les nouvelles listes sont concat-à partir de listes connues existantes/chemins de code). Ensuite, il va probablement remplacer tous les length l "appels" avec le réel constante à un certain stade lors de la génération de code de bas niveau, non? Je me demande si c'est vraiment le cas, ou si quelque chose me manque dans mon intuition de débutant sur les langages fonctionnels purs/compilateur.Les appels 'length' sont-ils réécrits en tant qu'informations constantes par GHC?

Source

2016-12-04 metaleap

Montrer/Dites-nous en plus sur votre code. Les listes sont-elles constantes? – ThreeFx

Juste réalisant le mien était une question si stupide (temps de pause je suppose), bien sûr beaucoup de mes listes sont des chaînes chargées de IO et entièrement dynamique-longueur. Je dois supposer qu'un projet de compilateur de ~ 25 ans alignera des longueurs connues de listes constantes. – metaleap

Cela n'a rien à voir avec un compilateur de 25 ans - cela dépend de l'implémentation de la structure de données que vous utilisez. Les listes ne sauvegardent pas les informations de longueur et vous n'avez donc pas de durée constante avec les listes. – ThreeFx

Je crois que la question est de savoir si GHC tourne, par exemple, length [1,2,3] en 3 au moment de la compilation. GHC 8.0.1 est la première version de GHC à faire cette optimisation (au moins parmi les versions que j'ai installées). Passons maintenant à la deuxième partie de votre question. Maintenant, passons à la deuxième partie de votre question. Prenons la date de la première version bêta de GHC de Wikipedia comme date de début de GHC: 1er avril 1991. GHC 8.0.1 a été publié en mai 2016. Donc, il semble que votre théorie selon laquelle c'est une optimisation qui caractérise Les projets de compilation de plus de 25 ans sont validés dans ce cas.

Source

2016-12-04 14:46:15

WIll le fera aussi pour les chaînes/listes lues à partir de fichiers, qui ne sont pas connus au moment de la compilation? – ThreeFx

@Reid Barton bien le bon timing pour moi alors avec 8.0.1! Le cas ici avec "listes" était vraiment beaucoup de traitement de chaîne avec de nombreuses constantes de chaîne dispersées (formats prédéfinis pour générer etc) --- pas assez haut niveau pour utiliser des paquets de traitement de texte avancé, mais assez alambiqué que j'ai remarqué Je fais autant de longueurs sur des constantes ou des concat de constantes, et dans des récursions profondes, et pour des nombres inconnus de fichiers in/out etc cela m'a fait réfléchir sur la constance de mes constantes à ce stade. .. – metaleap

@ThreeFx improbable maintenant n'est ce pas? De tels pouvoirs prédictifs devraient être l'étoffe de la chose suivante après l'informatique quantique. – metaleap

Tout dépend de la structure de données utilisée. listes régulières sont simples listes chaînée:

data List a = Nil | Cons a (List a)

Vous pouvez imaginer length être définis comme ceci:

length []  = 0 
length (x:xs) = 1 + length xs

Cela nécessite du temps O (n) à courir, car il n'y a pas moyen plus rapide pour déterminer la longueur de cette structure. Comme les chaînes résident dans un fichier texte, elles ne sont pas constantes au moment de la compilation et les appels length doivent être évalués normalement.

Utilisation du package Data.Vector vous obtenez O (1) Les appels de longueur, mais perdre certaines propriétés de la liste.

Source

2016-12-04 14:32:35 ThreeFx

Je pense que la question n'était pas quelle est la structure de données de List et comment implémenter la longueur, mais s'il y a des optimisations de compilateur dans les cas où la longueur peut être connue au moment de la compilation. – jpath

Les appels 'length' sont-ils réécrits en tant qu'informations constantes par GHC?

Répondre

Questions connexes