Подмножество Haskell Recursion

Question

Я новичок в переполнении стека и Haskell, поэтому, пожалуйста, дайте мне знать, если есть другой способ сделать это!

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

Вот вопрос:

Я не понимаю, как работает рекурсия в следующем коде:

subsets :: [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

Вывод этого кода:

*Main> subsets [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Я понимаю, как подмножества вызываются рекурсивно и как вы можете добраться до подмножества [] = [[]], но я не совсем понимаю, как это возвращает список списков и как он возвращает некоторый список, такой как [1], [1,3]и [2,3].

Опять же, я новичок в переполнении стека, поэтому, пожалуйста, дайте мне знать, если есть лучший способ сделать это, кроме повторения вопроса.

Answer 1

Давайте сначала уточнить subsets [3].Помните, что ys <- [ [] ] означает, что ys принимает каждый из элементов в списке, [ [] ], который включает в себя только один элемент, [].

   subsets (3:[])
=> [zs | ys <- subsets [] ...
=> [zs | ys <- [ [] ] ...
=> [zs | ys <- [ [] ], zs <- [[], (3:[])]]
= [[], [3]] -- zs takes on each element of [[], (3:[])]

Теперь давайте проигнорируем то, что "на самом деле"происходит и выражает логику в словах.

subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

означает:

Aggregate all zs
  where ys takes on in turn each of the subsets of the list without x,
  and for each ys,
    zs takes on the subset ys, and the subset ys and x together

Например:

   subsets [2,3]
=> ys takes on in turn each of the subsets of the list without 2
=> [[], [3]]

=> for each ys,
     zs takes on the subset ys, and the subset ys and 2 together
=> [[], [2], [3], [2,3]]