Использовать ли Data.Sequence или DList зависит от того, как вы собираетесь использовать результирующий список.DList замечательно, когда вы строите последовательность, скажем, в вычислении Writer, чтобы преобразовать ее в конец списка и использовать ее.Однако, если вам нужно использовать промежуточные результаты, например, скажем:
f (foo ++ bar)
+ f (foo ++ bar ++ baz)
+ f (foo ++ bar ++ baz ++ quux)
, тогда DList довольно плохо, потому что каждый раз нужно пересчитывать позвоночник.Data.Sequence - лучший выбор в этой ситуации.Data.Sequence также лучше, если вам нужно удалить элементы из последовательности.
Но, возможно, вам даже не нужно принимать это решение.Реверсивные списки в конце вычислений распространены в строгих функциональных языках, таких как ML и Scheme, но не в Haskell.Возьмем, к примеру, эти два способа записи map:
map_i f xs = reverse $ go [] xs
where
go accum [] = accum
go accum (x:xs) = go (f x : accum) xs
map_ii f [] = []
map_ii f (x:xs) = f x : map_ii f xs
На строгом языке map_ii было бы ужасно, потому что он использует пространство линейного стека, тогда как map_i хвостовая рекурсивность.Но поскольку Haskell ленив, map_i неэффективен.map_ii может потреблять один элемент ввода и выдавать один элемент вывода, тогда как map_i потребляет весь ввод перед тем, как получить какой-либо вывод.
Хвостовая рекурсия не является святым Граалем эффективного внедрения в Haskell.При создании структуры данных, такой как список, вы действительно хотите быть co -recursive;то есть, сделайте рекурсивный вызов под приложением конструктора (например, f x : map_ii f xs выше).
Так что, если вы обнаружите, что вы переворачиваете после хвостовой рекурсивной функции, посмотрите, можете ли вы интегрировать весь лот вcorecursive функция.