Das dlist-Paket enthält die DList -Daten Typ, der viele Instanzen hat, aber nicht Foldable oder Traversable . In meinen Augen sind dies zwei der "listenähnlichen" Klassen. Gibt es einen Leistungsgrund, dass DList keine Instanz dieser Klassen ist?
Außerdem implementiert das Paket foldr und unfoldr , aber keine der anderen Faltungsfunktionen.
DList a ist ein Wrapper vom Typ newtype für [a] -> [a] , der in einer kontravarianten Position eine a aufweist. Daher kann Foldable oder Traversable oder sogar Functor nicht direkt implementiert werden. Die einzige Möglichkeit, sie zu implementieren, ist die Konvertierung in und aus regulären Listen (siehe foldr Implementierung), was den Leistungsvorteil von Differenzlisten zunichte macht.
Eine Alternative, die Sie anstelle von DList in Betracht ziehen sollten, ist die Verwendung von Church-encoded-Listen. Die Idee ist, dass Sie eine Liste als einen undurchsichtigen Wert darstellen, der weiß, wie man eine foldr über eine Liste ausführt. Dies erfordert die Verwendung der Erweiterung RankNTypes :
Der Nachteil ist, dass es keine effiziente tail -Operation für eine ChurchList -Faltung gibt ChurchList ist billig, aber wiederholte Schwänze zu nehmen ist teuer ...
Tags und Links haskell church-encoding difference-lists