Please improve these comprehensions (was meaning of [ ])

[Rustom Mody]

Since these discussions are uselessly abstract and meta
Here is some code I (tried) to write in class the other day

The basic problem is of generating combinations
Using the pascal-identity nCr + nC(r-1) = (n+1)Cr

This can be written (Haskell)
c :: Int -> Int -> Int
c n 0         = 1
c 0 (r+1)     = 0
c (n+1) (r+1) = c n r + c n (r+1)

But I dont want NUMBER of combinations I want to generate combinations from 
a given set

So change the spec to
c :: [a] -> Int -> [[a]]
ie n stops being a number but is now a set (here list) length n

c n 0 = [[]]
c [] (r+1)  = []
c (x:xs) (r+1) = [x:l | l <- c xs r] ++  c xs (r+1)


Runs
? c [1,2,3,4] 2
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] :: [[Int]]

All binomials
? [c [1,2,3,4] r | r <- [0..4]]
[
 [[]], 
 [[1], [2], [3], [4]], 
 [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 
 [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]], 
 [[1, 2, 3, 4]]
] :: [[[Int]]]

Now thats neat as far as it goes but combinations are fundamentally sets
not lists

So I thought python would do a better job
I tried translating it to python and sets but it turned out more annoying than
helpful
Can someone improve it??

The straightforward translation of the above
Which is ok so far


def c(n,r):
    if r == 0:
        return [[]]
    elif len(n) == 0:
        return []
    else:
        return [[n[0]] + l for l in c(n[1:],r-1)] + c(n[1:],r)


Now to go from returning list of lists to set of sets:

st = frozenset
nullset = st([])
def singleton(x): return st([x])
def splitset(s):
    i = iter(s)
    e = next(i)
    new = st(i)
    return e,new

def cs(n,r):
    """ Set version of c"""
    if r == 0 :
        return singleton(nullset)
    elif len(n) == 0 :
        return nullset
    else:
        x,xs = splitset(n)
        return st([(singleton(x) | l) for l in cs(xs,r-1)]) | cs(xs,r)

def ss0n(fs):
    """ Shows a simple-set (ie set-0, contains no subsets) nicely"""
    r = "{"
    for x in fs:
        r += repr(x) + ", "
    return r + "}"

def ss1n(fs0):
    """ Shows a set-of-sets (ie set-1, contents are sets) nicely"""
    r = "{"
    for x in fs0:
        r += ss0n(x) + ", "
    return r + "}"    

>>> cs({1,2,3,4}, 2)
frozenset([frozenset([2, 4]), frozenset([3, 4]), frozenset([2, 3]), frozenset([1, 3]), frozenset([1, 2]), frozenset([1, 4])])
>>> ss1n(cs({1,2,3,4}, 2))
'{{2, 4, }, {3, 4, }, {2, 3, }, {1, 3, }, {1, 2, }, {1, 4, }, }'

>>> ss1n(cs({1,2,3,4}, 2))
'{{2, 4, }, {3, 4, }, {2, 3, }, {1, 3, }, {1, 2, }, {1, 4, }, }'


So how could this be done better?

Here for reference is an abstract math ideal I would like to approximate

c : {t} → Int → {{t}}   ## t is an arbitrary unspecified type
c n          0     = {{}}
c {}         (r+1) = {}
c ({x} ∪ xs) (r+1) = {{x} ∪ l | l ∈ c xs r} ∪ c xs (r+1)

exactly parallel to the pascal identity

c n 0         = 1
c 0 (r+1)     = 0
c (n+1) (r+1) = c n r + c n (r+1)