Qu'est-ce que la fusion de flux d'Haskell ?

Question

Qu'est-ce que la fusion de flux d'Haskell et comment l'utiliser ?

Answer 1

Le document que Logan indique est excellent, mais il est un peu difficile. (Il suffit de demander à mes étudiants.) Il traite également en grande partie de " la façon dont la fusion des flux fonctionne " et seulement en partie de " ce qu'est la fusion des flux et comment vous pouvez l'utiliser ".

Le problème que la fusion de flux résout est que les codes fonctionnels tels qu'ils sont écrits allouent souvent des listes intermédiaires, par exemple, pour créer une liste infinie de numéros de nœuds, vous pourriez écrire

nodenames = map ("n"++) $ map show [1..]

Un code naïf allouerait une liste infinie d'entiers [1, 2, 3, ...] une liste infinie de chaînes de caractères ["1", "2", "3", ...] et finalement une liste infinie de noms ["n1", "n2", "n3", ...] . C'est trop d'allocation.

Ce que la fusion de flux fait est de traduire une définition comme nodenames en quelque chose qui utilise une fonction récursive qui alloue seulement ce qui est nécessaire pour le résultat. En général, l'élimination de l'allocation de listes intermédiaires est appelée déforestation .

Pour utiliser la fusion de flux, vous devez écrire fonctions de liste non récursives qui utilisent les fonctions de la bibliothèque de fusion de flux décrites dans le document Ticket GHC 915 ( map , foldr et ainsi de suite) au lieu d'une récursion explicite. Cette bibliothèque contient de nouvelles versions de toutes les fonctions Prelude qui ont été réécrites pour exploiter la fusion de flux. Apparemment, ces fonctions sont prévues pour la prochaine version de GHC (6.12) mais ne sont pas présentes dans la version stable actuelle (6.10). Si vous voulez utiliser la bibliothèque, Porges a une explication simple et agréable dans sa réponse.

Si vous voulez vraiment une explication sur le fonctionnement de la fusion des courants, posez une autre question - mais c'est beaucoup plus difficile.

Answer 2

Pour autant que je sache, et contrairement à ce que Norman a dit, la fusion de flux est no actuellement implémentées dans la base de GHC (c'est-à-dire que vous ne pouvez pas simplement utiliser les fonctions Prelude). Pour plus d'informations, voir Ticket GHC 915 .

Pour utiliser la fusion de flux, vous devez installer la bibliothèque stream-fusion, importer Data.List.Stream (vous pouvez également importer Control.Monad.Stream) et utiliser uniquement les fonctions de ce module plutôt que les fonctions Prelude. Cela signifie que vous devez importer le module Prelude qui cache toutes les fonctions de liste par défaut, et ne pas utiliser les constructions [x..y] ou la compréhension de liste.

Answer 3

Don Stewart a écrit un très bon article aquí qui démontre comment la bibliothèque uvector peut être utilisée pour faire de la fusion de flux.

Answer 4

N'est-il pas correct que lorsque GHC en 6.12 utilisera ces nouvelles fonctions par défaut, elles implémenteront également [x..y] et les compréhensions de listes de cette manière non récursive ? Parce que la seule raison pour laquelle ils ne sont pas dans la rangée droite, est qu'ils sont interne et pas vraiment écrites en Haskell, mais plutôt comme des mots-clés, pour des raisons de rapidité et/ou parce que vous ne pourriez pas redéfinir cette syntaxe.