# Products with unordered n-tuples

Recently, Dani Rybe wrote this really cool blog
post
(in turn based on this old post by Samuel
Gélineau)
about encoding truly *unordered* n-tuples in Haskell. This is
something I thought about a long time ago in my work on
combinatorial species, but I never came up with a way to represent
them. Samuel and Dani’s solution is wonderful and clever and totally
impractical, and I love it.

I won’t go into more detail than that; I’ll let you go read it if you’re interested. This blog post exists solely to respond to Dani’s statement towards the end of her post:

I’m not sure how to, for example, write a function that multiplies the inputs.

Challenge accepted!

```
primes :: [Int]
= 2 : sieve primes [3 ..]
primes where
: ps) xs =
sieve (p let (h, t) = span (< p * p) xs
in h ++ sieve ps (filter ((/= 0) . (`mod` p)) t)
mul :: [Int] -> Int
= unfuck mulU
mul where
mulU :: U n Int -> Int
= ufold 1 id (< 0) \(US neg nonNeg) ->
mulU * mulPos primes (abs <$> neg) * (-1) ^ ulen neg
mulNonNeg nonNeg
mulNonNeg :: U n Int -> Int
= ufold 1 id (== 0) \(US zero pos) ->
mulNonNeg if ulen zero > 0 then 0 else mulPos primes pos
mulPos :: [Int] -> U n Int -> Int
= ufold 1 id (== 1) \(US _ pos) -> mulGTOne ps pos
mulPos ps
mulGTOne :: [Int] -> U n Int -> Int
: ps) = ufold 1 id ((== 0) . (`mod` p)) \(US divP nondivP) ->
mulGTOne (p : ps) ((`div` p) <$> divP) * (p ^ ulen divP) * mulGTOne ps nondivP mulPos (p
```

Since every integer has a unique prime factorization, at each step we split the remaining numbers into those divisible by \(p\) and those not divisible by \(p\). For the ones that are, we divide out \(p\) from all of them, multiply by the appropriate power of \(p\), and recurse on what’s left; for those that are not, we move on to trying the next prime.

Dani also speculates about `ubind :: U n (U m a) -> U (n :*: m) a`

. I
believe in my heart this should be possible to implement, but after
playing with it a bit, I concluded it would require an astounding feat
of type-fu.

PS I’m working on getting comments set up here on my new blog… hopefully coming soon!