Как мне сделать powerset без использования карты или лямбды в Haskell?

Question

Я пытаюсь сделать powerset в Haskell (я очень новичок в этом), и я не могу точно понять, что мне нужно сделать, чтобы сделать его без карты. С картой и лямбдой я нашел это решение:

powerset :: Set a -> Set (Set a)
powerset [] = [[]]
powerset (head:tail) = powerset tail >>= \set ->[set, head:set]
powerset (x:xs) = map (x:) (powerset xs) ++ powerset xs

Это НЕ то, что я хочу. Я просмотрел все остальные вопросы и не смог найти ответ, который искал. Помощь будет принята с благодарностью!!

Редактировать: это то, что я придумал до сих пор.. Это, очевидно, не работает, но я пытаюсь!!

powerset :: Set a -> Set (Set a)
powerset [] = [[]]
powerset (x:xs) = [x + (powerset xs)] + powerset xs

Answer 1

Вы почти на месте - если вы хотите использовать списки, которые эквивалентны map в этом случае вам нужен только маленький шаг:

powerset (x:xs) = [x:ps | ps <- powerset xs] ++ powerset xs

_{Что мне любопытно - почему вы хотите избежать} map _{это один из самых важных шаблонов функционального программирования, который вы найдете! Но я думаю, что это не часть моего ответа - просто примечание.}

Answer 2

Из комментариев:

a 'with [a]' a '- это переменная жесткого типа, связанная сигнатурой типа для powerset:: Set a -> Set (Set a) at assignment2.hs:71:1 В первом аргументе (++)' а именно: x 'в выражении: x ++ (powerset xs) в первом аргументе (++)', а именно: [[x ++ (powerset xs)]'

Это потому что powerset возвращает Set (Set a) где Set это просто псевдоним для списков. Обратите внимание, что (++) объединяет два списка одного типа. поскольку x это Set a, он не может быть соединен с Set (Set a), Вместо этого вы должны использовать оператор cons (:) который добавляет элемент в начало списка.

x : powerset xs