Zippers for non-inductive types | Hacker News Reader

Zippers for non-inductive types

danghica.blogspot.com

39 pointsmatt_d6 comments

> Set(A) = ∑n A^n/n! = e^A since there are n! permutations to quotient by.

But this is wrong. The number of sets over A={0,1,2} is 2^3 = 8 /= e^3

The actual series should be

    Set(A) = ∑n (A*(A-1)*(A-2)..(A-n+1))/n! = 2^A

This is also consistent with the fact that Set(A) ~ A -> Bool

How do you interpret the derivative of that? It's now log(2)*2^A.

What does "log(2)" mean as a type here? Do you expand it back out as a taylor series like in the circular list example?

Right, that is the formula for multisets, or bags as they are also called.

No, I believe the formula for multisets would be

    M(x) = ∑n (A*(A+1)*(A+2)..(A+n-1))/n!

since there are (n+k+1)c(k+1) possible unordered n-tuples over a set with cardinality k.

∑Aⁿ/n! actually represents the multisets (aka bags) of elements from A. A multiset is a list, but we quotient out by permutations (hence n!)

The division here can be seen as an action of the permutation group (which has n! element).