Powerset без дубликатов

Мне нужно создать функцию powerset в haskell, которая берет набор и выводит набор мощности без повторяющихся записей, независимо от того, что помещено в список ввода. Например: [1,1] должен вернуть [[], [1]]

    powerset [] = [[]]
    powerset (x:xs) = union((powerset xs)) (map (x:) (powerset xs))

Если union - это ранее определенная функция, она соединяет два набора без дубликатов. Проблема с приведенным выше кодом заключается в том, что он считает дубликаты исходными записями, поэтому input [1,1] возвращает [[], [1], [1], [1,1]].

Любые идеи? Я подумал об использовании объединения со списком ввода и пустым списком для удаления дубликатов перед запуском powerset, но я не уверен, как это будет выглядеть.


functional-programming haskell powerset
person lepdeffard    schedule 27.03.2015    source источник
comment
Не совсем эффективно: filterM (const [True, False]) $ nub xs   -  person Sibi    schedule 27.03.2015

Ответы (1)


arrow_upward
5
arrow_downward

  1. Удалите все дубликаты из данного списка (вы можете использовать функцию nub).

  2. Запустите алгоритм, который вы используете сейчас.

person kraskevich    schedule 27.03.2015
comment
Как мне сделать все это в одной функции? Я хочу запустить powerset как функцию, которая сначала удаляет дубли, а затем возвращает powerset. - person lepdeffard; 27.03.2015
comment
@lepdeffard Это жесткое требование использовать одну функцию? Если это не так, вы можете переименовать свою текущую функцию в powerset' и определить powerset как композицию powerset' и nub. - person kraskevich; 27.03.2015