Search code examples
recursionsmlfoldmlpowerset

Implementing powerset function in ML using only map and folds

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

Solution

  • 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...