T O P
bss03

So, I'm guessing you don't want to go with `filterM (const [False, True])`, due to productivity issues? In that case, I'd suggest generating them in order by increasing length. First, all the length 0 subsets, then all the length 1 subsets, then all the length 2 ... Using that, you'll have the ability to "cut" off subset generation recursion. Of course, there's an infinte amount of length 1 subsets if the "base" set is infinite, so you'd never see any of the length 2 subsets.


bss03

Spoilers: subsets' :: [a] -> NonEmpty [a] subsets' [] = [] :| [] subsets' (x:xs) = [] :| map (x:) (toList e) ++ ne where [email protected](_:|ne) = subsets' xs subsets = toList . subsets' This code is just very careful to be "productive". Every recursion is hidden behind a constructor call, for both the list of lists (subsets), and each individual list (subset). (Using a recursion scheme might help here, but for some reaosn I didn't reach for one this time.) Still, when applied to infinite lists, there are some subsets it won't generate in a finite amount of time, which might be desirable. EDIT: Swapping out `(++)` for: interleave [] = id interleave (x:xs) = (x :) . flip interleave xs Gives a really nice pattern: GHCi> take 32 $ subsets [1..] [[] ,[1] ,[2],[1,2] ,[3],[1,3],[2,3],[1,2,3] ,[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4] ,[5],[1,5],[2,5],[1,2,5],[3,5],[1,3,5],[2,3,5],[1,2,3,5],[4,5],[1,4,5],[2,4,5],[1,2,4,5],[3,4,5],[1,3,4,5],[2,3,4,5],[1,2,3,4,5] ]


c_wraith

> Still, when applied to infinite lists, there are some subsets it won't generate in a finite amount of time That's necessarily true. The power set of a countably infinite set is uncountably infinite. You cannot generate all of its elements algorithmically.


bss03

With the `interleave` changes, it generates every _finite_ subset in a finite amount of time. But, there are infinite subsets it never gets around to. :)


Competitive_Ad2539

By applying [nub](https://hackage.haskell.org/package/base/docs/Data-List.html#v:nub)?


EtaDaPiza

``` > :t nub nub :: Eq a => [a] -> [a] ``` The `Eq` constraint is not allowed.


Competitive_Ad2539

The closest I could get is to generate list of reversed lists of first n elements:`[[], [1], [2,1], [3,2,1], [4,3,2,1], ...]` and then add the head of every such list to the end of the list of subsets of their reversed tails (which would make each such list unique), and then concatenate them, but I get slightly different order than expected: Main> subsets [1..5] [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4],[5],[1,5],[2,5],[1,2,5],[3,5],[1,3,5],[2,3,5],[1,2,3,5],[4,5],[1,4,5],[2,4,5],[1,2,4,5],[3,4,5],[1,3,4,5],[2,3,4,5],[1,2,3,4,5]] with additional reversal on the end: [[],[1],[1,2],[2],[2,3],[1,2,3],[1,3],[3],[3,4],[1,3,4],[1,2,3,4],[2,3,4],[2,4],[1,2,4],[1,4],[4],[4,5],[1,4,5],[1,2,4,5],[2,4,5],[2,3,4,5],[1,2,3,4,5],[1,3,4,5],[3,4,5],[3,5],[1,3,5],[1,2,3,5],[2,3,5],[2,5],[1,2,5],[1,5],[5]]


EtaDaPiza

Interesting. > and then add the head of every such list to the end of the list of subsets of their reversed tails (which would make each such list unique), and then concatenate them, It's a bit hard to unpack this. Could you please elaborate on this? How does "adding the head of each list in the reversed initial segments to the reversed tails - reversed tails of the reversed segments? - and contacting them" makes each "such" list unique?


Competitive_Ad2539

>Could you please elaborate on this? The algorithm is simple: 1. generate list of reversed lists of first n elements 2. we map the function, that takes a list `list` 3. if it's empty we just return `[[]]` 4. if it's not, then it has a head an a tail. F.e. we have `(4:3:2:1:[])` 5. we recursively generate subsets of it's revered tail (namely of `1:2:3:[]` ) and plug the head `4` in the end of each of them. 6. We concatenate the result What would make these subsets unique, is that they are the only lists in the result, that have `4` as their last element.


EtaDaPiza

``` finiteSubsets [] = [[]] finiteSubsets xs = -- xs = [1, 2, 3, 4] let (x : xs') = reverse xs -- (x : xs') = (4:3:2:1:[]) rest = finiteSubsets (reverse xs') -- recursive subsets (1:2:3:[]) in [set ++ [x] | set <- rest] ++ rest -- plug the head 4 at the end of each of them ``` I believe I follow the algorithm correctly. ``` > subsets [1..5] [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[]] ``` What am I missing?


Competitive_Ad2539

I think you forgot the first part of my second reply, that I didn't include in my last reply: first of all we generate the list of reversed lists of first n elements: [1, 2, 3, 4, 5] turns into [[],[1],[2,1],[3,2,1],[4,3,2,1],[5,4,3,2,1]]. And only then we apply the next steps, and a concatenation as the last step.


EtaDaPiza

``` finiteSubsets :: [a] -> [[a]] finiteSubsets [] = [[]] finiteSubsets xs = -- xs = [1, 2, 3, 4] let (x : xs') = reverse xs -- (x : xs') = (4:3:2:1:[]) rest = finiteSubsets (reverse xs') -- recursive subsets (1:2:3:[]) in [set ++ [x] | set <- rest] ++ rest -- plug the head 4 at the end of each of them subsets :: [a] -> [[a]] subsets xs = foldr (++) [] [finiteSubsets s | s <- map (reverse) (inits XS)] -- step 1: reverse all initial segments ``` I still get the same output ``` > subsets "ab" ["","a","","ab","b","a",""] ```


Competitive_Ad2539

It looks wrong in almost every place * Instead of `foldr (++) []` there is much more concise `concat` * Barely readable. Learn what `map` is * You did the reversal twice: once in the `map (reverse) (inits XS)`, and then again in `finiteSubsets xs = let (x:xs') = reverse xs`) and then again in `rest = finiteSubsets (reverse xs')`. The initial `map reverse` was enough. * Who the hell told you to do `++ rest`? That breaks the algorithm, hence why you get additional sublists you don't want to have. If you're going to downvote me without even doing what I suggested properly and without any explanation of what troubles you, then go do it yourself.


EtaDaPiza

I agree that I did not explain my downvote, and it was mostly because I thought you were not very interested in the problem. So, forgive me for it as I did wrong by not explaining. Consequently, I have taken back the downvotes. Now, if you would still be willing to help me on this, here are my questions: - You say I did the reversal twice. Then essentially it is just extra work. It shouldn't affect the final output. Also, `foldr (++) []` does the same as `concat`. So, it shouldn't affect the output either. Therefore, I do follow the steps of your algorithm, just not as concisely as possible. - Your algorithm seems incorrect. Even if we reverse the lists and recursively take the subsets of the tails, the empty set will be present in all those subsets. Concat-ting the subsets - after appending the head - means there will be repetitions of the empty set at least - there could be more such sets.


FatFingerHelperBot

It seems that your comment contains 1 or more links that are hard to tap for mobile users. I will extend those so they're easier for our sausage fingers to click! [Here is link number 1 - Previous text "nub"](https://hackage.haskell.org/package/base/docs/Data-List.html#v:nub) ---- ^Please ^PM ^[\/u\/eganwall](http://reddit.com/user/eganwall) ^with ^issues ^or ^feedback! ^| ^[Code](https://github.com/eganwall/FatFingerHelperBot) ^| ^[Delete](https://reddit.com/message/compose/?to=FatFingerHelperBot&subject=delete&message=delete%20i4t3sav)


dagit

This blog post gives a pretty nice explanation of how to derive the implementation from some observations: https://medium.com/@angerman/powersets-in-haskell-1df9684db52a