Haskell - помогите понять функцию

Question

У меня есть таинственная функция, которую я не могу понять:

mystery :: [a] -> [[a]]
mystery [] = [[]]
mystery (x:xs) = sets ++ (map (x:) sets)
                 where sets = mystery xs

Вот некоторые входные данные с результатами:

mystery [1,2] returns [[],[2],[1],[1,2]]
mystery [1,2,3] returns [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

Глядя на результаты, я вижу, что он вычисляет все возможные комбинации чисел в списке, но не все возможные перестановки ... Я думаю.

Проблема, с которой я столкнулся, на самом деле проходит через рекурсию и понимание того, как функция получает эти результаты.

Я думаю, что я получил начало -> отображение (1 :) на [2], получая [1,2], но в этот момент я запутался, как работает рекурсия, и могу ли я я все еще отображаю (1 :) или сейчас (2 :), и на что именно.

Если кто-нибудь может помочь мне, объяснив шаг за шагом (используя один из приведенных примеров), как работает эта функция (с картой и устанавливает рекурсию), это было бы очень признательно!

Спасибо!

Answer 1

Haskell выполнит так называемую ленивую оценку, что означает, что он будет работать только так, как он нужен слева направо (обычно). Итак, взяв ваш пример mystery [1, 2], Haskell сделает следующее:

sets ++ (map (x:) sets)

Что оценивается в:

mystery (2:[]) ++ (map (1:) sets)

На данный момент мы звоним mystery (2:[])

mystery ([]) ++ (map (2:) sets) ++ (map (1:) sets)

mystery ([]) вернет пустой список списков

[[]] ++ (map (2:) sets) ++ (map (1:) sets)
[[]] ++ (map (2:) mystery []) ++ (map (1:) sets)

Так что теперь Haskell попытается применить функцию (2:) к списку, содержащему пустой список

[[]] ++ (2:[[]]) ++ (map (1:) sets)
[[]] ++ [[2]] ++ (map (1:) sets)
[[], [2]] ++ (map (1:) sets)

Здесь все становится немного более запутанным.

[[], [2]] ++ (map (1:) mystery (2:[]))

Это последнее sets будет оценивать mystery (2:[])

[[], [2]] ++ (map (1:) (sets ++ (map (2:) sets)))
[[], [2]] ++ (map (1:) (mystery [] ++ (map (2:) sets))
[[], [2]] ++ (map (1:) ([[]] ++ (map (2:) mystery []))
[[], [2]] ++ (map (1:) ([[]] ++ (2:[[]]))
[[], [2]] ++ (map (1:) ([[]] ++ [[2]])

Теперь (1:) будет применен к списку, который содержит пустой список, и список, содержащий 2:

[[], [2]] ++ (map (1:) ++ [[], [2]])
[[], [2]] ++ [[1], [1, 2]]
[[], [2], [1], [1, 2]]

Настоящая суть операции - в этих двух последних разделах. Haskell создает список наподобие [[], [2]], а затем добавляет его в начало каждого списка, чтобы сформировать [[1], [1, 2]].

Answer 2

Ваша загадочная функция вычисляет мощность его входа.