Warum sind Differenzlisten effizienter als die reguläre Verkettung?
Ich arbeite mich gerade durch dieLerne dir einen Haskell Buchen Sie online und besuchen Sie ein Kapitel, in dem der Autor erklärt, dass einige Listenverknüpfungen ineffizient sein können: Zum Beispiel
((((a ++ b) ++ c) ++ d) ++ e) ++ f
ist angeblich ineffizient. Die Lösung, die der Autor vorschlägt, besteht darin, "Differenzlisten" zu verwenden, die als definiert sind
newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }
instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
Ich habe Probleme zu verstehen, warum DiffList in einigen Fällen recheneffizienter ist als eine einfache Verkettung. Könnte mir jemand in einfachen Worten erklären, warum das obige Beispiel so ineffizient ist und auf welche Weise die DiffList dieses Problem löst?