SMLNJ powerset function

Question

I am trying to print the size of a list created from below power set function

fun add x ys = x :: ys;
   fun powerset ([])  = [[]]
   | powerset (x::xr) = powerset xr @ map (add x) (powerset xr) ;

val it = [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] : int list list;

I have the list size function

fun size xs = (foldr op+ 0 o map (fn x => 1)) xs;

I couldnt able to merge these two functions and get the result like

I need something like this:

[(0,[]),(1,[3]),(1,[2]),(2,[2,3]),(1,[1]),(2,[1,3]),(2,[1,2]),(3,[1,2,3])]

Could anyone please help me with this?

Answer 1

You can get the length of a list using the built-in List.length.

You seem to forget to mention that you have the constraint that you can only use higher-order functions. (I am guessing you have this constraint because others these days are asking how to write powerset functions with this constraint, and using foldr to count, like you do, seems a little constructed.)

Your example indicates that you are trying to count each list in a list of lists, and not just the length of one list. For that you'd want to map the counting function across your list of lists. But that'd just give you a list of lengths, and your desired output seems to be a list of tuples containing both the length and the actual list.

Here are some hints:

1. You might as well use foldl rather than foldr since addition is associative.

2. You don't need to first map (fn x => 1) - this adds an unnecessary iteration of the list. You're probably doing this because folding seems complicated and you only just managed to write foldr op+ 0. This is symptomatic of not having understood the first argument of fold.

   Try, instead of op+, to write the fold expression using an anonymous function:

   fun size L = foldl (fn (x, acc) => ...) 0 L
   

   Compare this to op+ which, if written like an anonymous function, would look like:

   fn (x, y) => x + y
   

   Folding with op+ carries some very implicit uses of the + operator: You want to discard one operand (since not its value but its presence counts) and use the other one as an accumulating variable (which is better understood by calling it acc rather than y).

   If you're unsure what I mean about accumulating variable, consider this recursive version of size:

   fun size L =
       let fun sizeHelper ([], acc) = acc
             | sizeHelper (x::xs, acc) = sizeHelper (xs, 1+acc)
       in sizeHelper (L, 0) end
   

   Its helper function has an extra argument for carrying a result through recursive calls. This makes the function tail-recursive, and folding is one generalisation of this technique; the second argument to fold's helper function (given as an argument) is the accumulating variable. (The first argument to fold's helper function is a single argument rather than a list, unlike the explicitly recursive version of size above.)

3. Given your size function (aka List.length), you're only a third of the way, since

   size [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
   

   gives you 8 and not [(0,[]),(1,[3]),(1,[2]),(2,[2,3]),...)]

   So you need to write another function that (a) applies size to each element, which would give you [0,1,1,2,...], and (b) somehow combine that with the input list [[],[3],[2],[2,3],...]. You could do that either in two steps using zip/map, or in one step using only foldr.

   Try and write a foldr expression that does nothing to an input list L:

   foldr (fn (x, acc) => ...) [] L
   

   (Like with op+, doing op:: instead of writing an anonymous function would be cheating.)

   Then think of each x as a list.