Это не базовый случай, а специальный случай, и это не рекурсия, а corecursion , (*) который никогда не останавливается.
Возможно, будет легче следовать следующей переформулировке:
allCombs :: [t] -> [[t]]
-- [1,2] -> [[]] ++ [1:[],2:[]] ++ [1:[1],2:[1],1:[2],2:[2]] ++ ...
allCombs vals = concat . iterate (cons vals) $ [[]]
where
cons :: [t] -> [[t]] -> [[t]]
cons vals combs = concat [ [v : comb | v <- vals]
| comb <- combs ]
-- iterate :: (a -> a ) -> a -> [a]
-- cons vals :: [[t]] -> [[t]]
-- iterate (cons vals) :: [[t]] -> [[[t]]]
-- concat :: [[ a ]] -> [ a ]
-- concat . iterate (cons vals) :: [[t]]
Выглядит иначе, делает то же самое. Не только дает те же результаты, но фактически делает то же самое для их получения. (*) concat - это то же самое concat, вам просто нужно наклонить Пройдите немного, чтобы увидеть это.
Это также показывает, почему здесь нужен concat. Каждый step = cons vals создает новую серию комбинаций, длина которых увеличивается на 1 в каждом step приложении, и concat склеивает их все вместе в один список результатов.
Длина каждой партии - это длина предыдущей партии, умноженная на n, где n - это длина vals. Это также показывает необходимость особого случая vals == [], т.е. случая n == 0: 0*x == 0, поэтому длина каждой новой партии равна 0, поэтому попытка получить еще одно значение из результатов никогда не приведет к результат, то есть войти в бесконечный цикл. Говорят, что в этот момент функция становится непроизводительной .
Кстати, cons почти такой же, как
== concat [ [v : comb | comb <- combs]
| v <- vals ]
== liftA2 (:) vals combs
liftA2 :: Applicative f => (a -> b -> r) -> f a -> f b -> f r
Так что, если вам не важен внутренний порядок результатов каждого шага (но обратите внимание на важное предупреждение в нижней части поста), это можно просто кодировать как
allCombsA :: [t] -> [[t]]
-- [1,2] -> [[]] ++ [1:[],2:[]] ++ [1:[1],1:[2],2:[1],2:[2]] ++ ...
allCombsA [] = [[]]
allCombsA vals = concat . iterate (liftA2 (:) vals) $ [[]]
(*) на самом деле, это относится к немного измененной версии,
allCombsRes vals = res
where res = [] : concatMap (\w -> map (: w) vals)
res
-- or:
allCombsRes vals = fix $ ([] :) . concatMap (\w -> map (: w) vals)
-- where
-- fix g = x where x = g x -- in Data.Function
Или в псевдокоде:
Produce a sequence of values `res` by
FIRST producing `[]`, AND THEN
from each produced value `w` in `res`,
produce a batch of new values `[v : w | v <- vals]`
and splice them into the output sequence
(by using `concat`)
Таким образом, список res создается ядром, начиная с его начальной точки, [], производя следующие его элементы на основе предыдущих (-ых) - либо пакетами, как в версии на основе iterate, или один за другим, как здесь, принимая вход с помощью обратного указателя в результаты, ранее произведенные (принимая его вывод в качестве входных данных, как говорится - что, конечно, немного обманчиво, так как мы принимаем его с более медленной скоростью, чем производим, иначе процесс перестанет быть производительным , как уже упоминалось выше.
Но. Иногда может быть выгодно производить ввод через рекурсивные вызовы, создавая во время выполнения последовательность функций, каждая из которых передает свой вывод по цепочке вызывающей стороне. Тем не менее, поток данных идет вверх, в отличие от обычной рекурсии, которая сначала идет вниз к базовому случаю.
Только что упомянутое преимущество связано с сохранением памяти. Corecursive allCombsRes как бы хранит обратный указатель в последовательности, которую он сам производит, и поэтому последовательность не может быть собрана мусором на лету.
Но цепочка производителей потоков, неявно созданная вашей исходной версией во время выполнения, означает, что каждый из них может собираться мусором на лету, так как n = length vals новые элементы создаются из каждого последующего элемента таким образом, общий процесс становится эквивалентным просто k = ceiling $ logBase n i вложенных циклов каждый с O (1) пробелом для получения i -го элемента последовательности .
Это намного лучше, чем O (n) требования к памяти для corecursive / value-recursive allCombsRes, который фактически сохраняет обратный указатель на свой выходной сигнал при i/n позиция. И на практике логарифмическое пространство, скорее всего, будет рассматриваться как более или менее O (1) пространство.
Это преимущество имеет место только с порядком генерации, как в вашей версии, т.е. как в cons vals, а не liftA2 (:) vals, который должен возвращаться к началу своей входной последовательности combs (для каждого нового v в vals), что, таким образом, должно быть сохранено, поэтому мы можем с уверенностью сказать, что формулировка в вашем вопросе довольно изобретательна.
И если мы после бессмысленной переформулировки - как бессмысленно может время от времени быть светящейся - это
allCombsY values = _Y $ ([] :) . concatMap (\w -> map (: w) values)
where
_Y g = g (_Y g) -- no-sharing fixpoint combinator
Таким образом, код гораздо проще понять в fix -использующей формулировке, и тогда мы просто переключаем fix с семантически эквивалентным _Y для эффективности, получая (эквивалент) исходного кода из вопроса.
Приведенные выше утверждения о поведении требований к пространству легко проверяются .Я еще этого не сделал.
См. Также: