Member Avatar for lotrsimp12345

so far I can't figure out a way to write powerset in SML :(.
I see a pattern for example

powerset([1,2,3]) is

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

Here's what I have come up with:

fun add(a,L)= [a]@L

fun ps(L)=
ps(tl L)@add(hd L, ps(tl L));

Any help appreciated.

  • 2 Contributors
  • 2 Replies
  • 90 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by lotrsimp12345

Dani AI

Generated

A couple of practical notes that follow from 's base-case hint and 's attempt: prefer pattern matching to hd/tl (it avoids empty-list exceptions and is clearer), and build the set of subsets for xs first, then derive those that include the head. An idiomatic, readable Standard ML implementation is:

fun powerset [] = [[]]
  | powerset (x::xs) =
      let
        val rest = powerset xs
        val withx = List.map (fn subset => x :: subset) rest
      in
        rest @ withx
      end

This returns a value of type 'a list -> 'a list list. The algorithm generates every subset of xs (the rest) and then prepends x to each of those to form the subsets that include x, finally concatenating the two lists. Time and memory grow exponentially (roughly O(2^n * n) time and O(2^n) space), so this is fine for small inputs but unsuitable for large lists. For different ordering or for performance tuning, the same idea can be expressed with List.foldr or a lazy/streamed generator to avoid holding all subsets in memory. Avoid using hd and tl in recursive code; pattern matching makes the base case and recursive step explicit and safe.

Recommended Answers

All 2 Replies

Member Avatar for Rashakil Fol

What's the powerset of the empty set?

Given x and given the powerset of xs, what's the powerset of (x :: xs)?

Bam, use recursion.

Member Avatar for lotrsimp12345

thanks i figured it out.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.