Почему списки различий более эффективны, чем обычная конкатенация?
В настоящее время я прохожу свой путь черезУзнай тебя на Хаскеле бронируйте онлайн и пришли к главе, в которой автор объясняет, что некоторые объединения списков могут быть неэффективными: например,
((((a ++ b) ++ c) ++ d) ++ e) ++ f
предположительно неэффективен. Решение, которое предлагает автор, заключается в использовании «списков различий», определенных как
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))
Я пытаюсь понять, почему DiffList в некоторых случаях эффективнее в вычислительном отношении, чем простая конкатенация. Может ли кто-нибудь объяснить мне в простых терминах, почему приведенный выше пример настолько неэффективен и каким образом DiffList решает эту проблему?