Implementing powerset function in ML using only map and folds

Question

I need to implement a powerset function in ML that takes a list of ints with the following contraints:

1) Never call built in library functions except map, foldr, and foldl.
2) Never be recursive. All recursion occur within map and fold
3) Never contain let or local expressions

I've already implemented the function without these constraints using normal recursion of the form:

Powerset(x::xs) = powerset(xs) @ x.powerset(xs)

I'm having trouble thinking of a way to translate this type of implementation into one that uses only maps and folds.

I'm not necessarily asking for someone to implement it for me, but I would appreciate a nudge in the right direction or any help for that matter.

Thakns

Answer 1

Here's how I go about solving problems with folds.

Think about the final value you want to obtain. In your case, this would be the powerset of the input list. The crucial question is now this: can the powerset of a list be recomputed after inserting a new element? That is, given P(S), the powerset of some set of items S, it is possible to compute P(S ∪ {x}) in terms of only P(S) and x?

I believe you've already answered this question definitively above. Not explicitly, perhaps, but if you rework your Powerset function, you'll find that the right idea is hidden in it. You'll want to package up this code into a little helper function:

fun extendPowerset (PS : 'a list list, x : 'a) : 'a list list =
  (* PS is the powerset of some set S. This function
   * should return the powerset of S ∪ {x}. *)
  ...

Great, now how do you plug that into a fold? Well, at each step of the fold, you are given two things:

1. the next element of the list, and
2. some value computed from all previous elements (think of this as a "summary" of the previous elements)

In return, you must compute a slightly larger summary: it should summarize the next element in addition to all previous. Doesn't this feel vaguely similar? The extendPowerset function is basically doing exactly what you need, where the "summary" of the previous elements is the powerset of those elements. I'll leave the rest to you.

---

Aside: note that you can also append two lists with a fold. As a hint, try working out what value is computed by foldl op:: [1,2] [3,4]. It's not quite like appending [1,2] and [3,4], but it's close...

Answer 2

Like you have already done, I would also first write a powerset function using explicit recursion. I would then try and discover the higher-order functional patterns and substitute those afterwards, one pattern at a time.

• You might for example turn a helper function

  fun consMany (x, []) = []
    | consMany (x, L::Ls) = (x::L) :: consMany (x, Ls)
  

  into the expression

  map (fn L => x::L) Ls
  

• You might eliminate a let-expression (useful for re-using a once-computed value twice)

  fun foo (x::xs) =
      let val rest = foo xs
      in ... x ... rest ... rest ...
      end
  

  using a function:

  fun foo (x::xs) =
      bar (x, foo xs)
  
  and bar (x, rest) = ... x ... rest ... rest ...
  

  although, this might as well be an anonymous function:

  fun foo (x::xs) =
      (fn rest => ... x ... rest ... rest ...) (foo xs)
  

• And you might turn a list-recursive function

  fun derp [] = ...
    | derp (x::xs) = g (x, derp xs)
  

  into the fold:

  fun derp xs = foldr g (...) xs
  

  but if the order of your results don't matter, foldl is tail-recursive.