Operations on Sets

GolfScript, 73 characters

.' '?:^>~`"~{:^1$?0<{[^]+}*}/
{\\`{[\\]}+/}+%
{?0<!}+,
{?0<}+,"n/^2/2-=~`

Uses non of the GolfScript set operators and should work on all valid GolfScript objects. Input must be given on STDIN, for format see also the online examples.

> union [1 2 3] [2 3 4]
[1 2 3 4]

> intersect [1 2 3] [2 3 4]
[2 3]

> complement [1 2 3] [2 3 4]
[1]

> product [1 2 3] [2 3 4]
[[1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 2] [3 3] [3 4]]

The code does not use GolfScript's set operators but implements them using loops.

.' '?        # find the first space character in the input
:^>          # save the position to variable ^ and remove from start of string
~            # evaluate the string (i.e. get two sets as arguments)
`            # transform the second set into a string
"..."n/      # generates an array of 4 strings which represent the set operations
             # (see below)
^2/2-        # take position of the first space (i.e. length of the operator)
             # divide by two, subtract two (i.e. union->0, intersect->2, 
             # complement->3, product->1)
=~           # take the corresponding command string and evaluate on the arguments
`            # transform the result back into a string representation

### union
~{           # evaluate the second argument (i.e. revert the ` operation)
             # and loop over all items
  :^         #   save item to variable ^
  1$?        #   is it contained in the first set?
  0<{        #   if no then
    [^]+     #     add to set
  }*         #   end if
}/           # end loop

### intersection
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if yes, keep
}+,          # end filter block

### complement
{            # prepend second argument to code block {...}+ and filter the first set
  ?0<!       #   is the current item contained in the second set? if no, keep
}+,          # end filter block

### product
{            # prepend second argument to code block {...}+ and map on first set
  \`{        #   take current item and prepend to code block `{...}+ and iterate
    [\]      #     swap both items (item of second set + item of first set) and
             #     build a tuple of them
  }+/        #   end loop
}+%          # end map

Ruby, 97 characters

$_,a=$*;A,B=eval a
p (~/c/?B.map{|i|~/d/?A.map{|j|[i,j]}:!A.index(i)^~/m/?p: i}:A+B).uniq.compact

Usage examples:

$ ruby set.rb union [[1,2,3],[8]]
[1, 2, 3, 8]
$ ruby set.rb complement [[1,2,3,6,7],[7,2,1,5]]
[5]
$ ruby set.rb intersect [[1,2,3,6,7],[7,2,1,5]]
[7, 2, 1]
$ ruby set.rb product [[1,2],[7,5,2]]
[[[7, 1], [7, 2]], [[5, 1], [5, 2]], [[2, 1], [2, 2]]]

GolfScript, 77 characters

(\~@99-:x{6x={&}{13x={'"#{['@','*+'].product ['+\','*+']}"'+~}{|}if}if}{-}if`

Sample inputs and outputs:

$ echo "union [1 2 3] [2 3 4]" | golfscript setops.gs
[1 2 3 4]
$ echo "intersect [1 2 3] [2 3 4]" | golfscript setops.gs
[2 3]
$ echo "complement [1 2 3] [2 3 4]" | golfscript setops.gs
[1]
$ echo "product [1 2 3] [2 3 4]" | golfscript setops.gs
"[[1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 2], [3, 3], [3, 4]]"

---

Okay, now time to explain this gobbledygook. First, here's an explanation of how it chooses which one of the four blocks (union, intersect, complement, product) to execute.

I noticed something convenient about these commands. They each begin with a unique letter (u, i, c, p). Therefore, we only care about this first letter.

Now, to make the code even shorter, these can be converted into ASCII codes (117, 105, 99, 112). Here's an explanation of the main logic of the program:

(     # grab the ASCII code of the first letter of the input string
\~    # evaluate the rest of the string. GS will ignore "nion", "tersect", etc.
@     # stack is now [A B CMD]
99-:x # subtract 99 for shorter code. Now 'uicp' maps to [18 6 0 13]

After this comes a huge chain of ifs. With the set operation logic removed, it looks like this:

{6x={INTERSECT_CODE}{13x={PRODUCT_CODE}{UNION_CODE}if}if}{COMPLEMENT_CODE}if`

Converted to a more readable C-like format, it looks like this:

if (x) {
  if (x == 6) {
    INTERSECT_CODE
  } else {
    if (x == 13) {
      PRODUCT_CODE
    } else {
      // x must be 18
      UNION_CODE
    }
  }
} else {
  // x is 0
  COMPLEMENT_CODE
}

Now, it's just a matter of looking at the code for the set operations. Most of them are fairly straightforwards: & for intersect, | for union, and - for complement. However, GolfScript doesn't have a built-in product operator, so I had to build some Ruby code for that. Here's an explanation of that mess:

'"#{['         # stack: [1 2 3] [2 3 4] '"#{['
@','*+         # stack: [2 3 4] '"#{[1,2,3'
'].product ['+ # stack: [2 3 4] '"#{[1,2,3].product ['
\','*+         # stack: '"#{[1,2,3].product [2,3,4'
']}"'+         # stack: '"#{[1,2,3].product [2,3,4]}"'
~              # evaluate

Simply tack on a ` to show array output correctly, and it's done!