Эффективная версия "inits"

То есть inits "abc" == ["","a","ab","abc"]

Существует стандартная версия inits в Data.List, но ниже я сам написал версию:

myInits = f id
 where
  f start (l:ls) = (start []):(f (start . (l:)) ls)
  f start [] = [(start [])]

Хотя моя версия довольно проста, чем стандартная версия, я подозреваю, что это не так хорошо по соображениям эффективности. Я подозреваю, что когда myInits l полностью оценивается, оно занимает пробел O(n^2). Возьмем, к примеру, myTails, реализацию tails:

myTails [email protected](_:ls) = a:(myTails ls)
myTails [] = [[]]

Это почти то же самое, что и стандартная версия, и я подозреваю, что он достигает пространства O(n), повторно используя хвосты списков.

Может ли кто-нибудь объяснить:

Почему моя версия inits плохая.
Почему другой подход лучше (либо стандартный в Data.List, либо ваш собственный).

Ответ 1

Ваш myInits использует метод, называемый список различий, чтобы создавать функции, которые строят списки в линейном времени. Я считаю, но не проверял, что время выполнения для полной оценки myInits составляет O(n^2), требующее пробела O(n^2). Для полной оценки inits также требуется O(n^2) время и пробел. Любая версия inits потребует пробела O(n^2); списки, построенные с помощью : и [], могут делиться только своими хвостами, а между результатами inits нет хвостов. В версии inits в Data.List используется время ожидания O(1), как и более простая очередь описанная во второй половине соответствующего ответа. Snoc, на который ссылается исходный код в Data.List, является воспроизведением слов на Cons (другое имя для :) назад - возможность добавления элемента в конец списка.

Вкратце экспериментируя с этими функциями, предположим, что myInits удовлетворительно удовлетворяет при использовании редко в большом списке. На моем компьютере, в ghci, myInits [1..] !! 8000000 дает результаты в течение нескольких секунд. К сожалению, у меня есть ужасающая неэффективная реализация, поставляемая с ghc 7.8.3, поэтому я не могу сравнить myInits с inits.

Строгость

Существует одна большая разница между myInits и inits и между myTails и tails. Они имеют разные значения при применении к undefined или _|_ (произносится как "bottom", другой символ используется для undefined).

inits имеет свойство строгости inits (xs ++ _|_) = inits xs ++ _|_, которое, когда xs является пустым списком [], говорит, что inits по-прежнему будет давать хотя бы один результат при применении к undefined

inits (xs ++ _|_) = inits xs ++ _|_
inits ([] ++ _|_) = inits [] ++ _|_
inits        _|_  = [[]]     ++ _|_
inits        _|_  =  []      :  _|_

Мы можем видеть это экспериментально

> head . inits $ undefined
[]

myInits не имеет этого свойства ни для пустого списка, ни для более длинных списков.

> head $ myInits undefined
*** Exception: Prelude.undefined

> take 3 $ myInits ([1,2] ++ undefined)
[[],[1]*** Exception: Prelude.undefined

Мы можем исправить это, если поймем, что f в myInits даст start [] в любой ветки. Поэтому мы можем отложить соответствие шаблонов, пока не потребуется решить, что делать дальше.

myInits' = f id
 where
  f start list = (start []):
                 case list of
                     (l:ls) -> f (start . (l:)) ls
                     []     -> []

Это увеличение лени делает myInits' работать так же, как inits.

> head $ myInits' undefined
[]

> take 3 $ myInits' ([1,2] ++ undefined)
[[],[1],[1,2]]

Аналогично, разница между myTails и tails в Data.List заключается в том, что tails выводит весь список как первый результат, прежде чем решить, останется ли остаток списка. В документации говорится, что она подчиняется tails _|_ = _|_ : _|_, но на самом деле она подчиняется гораздо более сильному правилу, которое трудно описать легко.

Ответ 2

Конструкция префикс-функций может быть отделена от их овеществления как фактические списки:

diffInits = map ($ []) . scanl (\a x -> a . (x:)) id

Это заметно быстрее (протестировано внутри GHCi) и более ленивее, чем ваша версия (см. ответ Cirdec для обсуждения):

diffInits        _|_  == []           :  _|_
diffInits (xs ++ _|_) == diffInits xs ++ _|_