Haskell Powerset в лексикографическом порядке

Я хочу написать функцию powerset в Haskell с объявлением функции:

powerset :: Ord a => [a] -> [[a]]

Однако я пытаюсь сделать лексикографический порядок так, чтобы:

powerset [1,2,3] = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

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

powerSet = filterM (const [True, False])

но ничего, что обеспечивает powerset в лексографическом порядке. Есть ли способ написать функцию набора мощности, чтобы обеспечить это или отсортировать несортированный набор мощности в этом порядке?


haskell powerset
person R. Monks    schedule 05.02.2016    source источник
comment
Вы не можете составить sortBy ? Вероятно, не самый эффективный способ, но он должен помочь.   -  person Mephy    schedule 06.02.2016

Ответы (1)


arrow_upward
3
arrow_downward

Вы можете сделать правильный фолд:

powerset :: Foldable t => t a -> [[a]]
powerset xs = []: foldr go [] xs
    where go x acc = [x]: fmap (x:) acc ++ acc

тогда:

\> powerset [1, 2]
[[],[1],[1,2],[2]]
\> powerset [1, 2, 3]
[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

(ответ отредактирован, чтобы удалить вызов функции tail)

person behzad.nouri    schedule 05.02.2016
comment
Насколько хорошо это справляется с большими результатами? Если вы попросите head . last . powerset $ [1..25], сколько времени это займет? - person dfeuer; 06.02.2016
comment
@dfeuer Кажется, что на этот вопрос вы можете ответить без какой-либо дополнительной работы со стороны автора ответа. - person Daniel Wagner; 06.02.2016
comment
@DanielWagner, обычно это было бы правдой, но я отлучусь от своего ноутбука самое раннее до вечера понедельника, и я ужасно нетерпелив. - person dfeuer; 06.02.2016
comment
@dfeuer Это быстрее, чем версия filterM. - person Daniel Wagner; 06.02.2016
comment
Спасибо, @DanielWagner! - person dfeuer; 06.02.2016
comment
@dfeuer на самом деле это довольно быстро. учитывая, что [1..25] имеет 2^25 подмножеств, это работает очень хорошо по сравнению, скажем, с maximum [1..2^25]. - person behzad.nouri; 07.02.2016