Ответ 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 _|_ = _|_ : _|_, но на самом деле она подчиняется гораздо более сильному правилу, которое трудно описать легко.