排列单子（Permutation monad）的定义可行性及构造方法问询

Great question! Let's unpack how to define a permutation-related monad, addressing the nuances of your description (since "permutation" can mean two common things here: full permutations of a set, or arbitrary-length non-repeating lists).

First, let's start with your example: for a set ( S = {a,b} ), ( P(S) ) is the set of full permutations ( {[a,b], [b,a]} ).

The Functor ( P ) #

For this to work as an endofunctor (like the List monad on ( \text{Set} )), we immediately hit a constraint: ( P(X) ) only makes sense as "full permutations" when ( X ) is finite, and even then, we can't define ( P(f) ) for arbitrary functions ( f: X \to Y ). If ( |X| \neq |Y| ), ( P(X) ) (length ( |X| ) lists) can't map to ( P(Y) ) (length ( |Y| ) lists).

To fix this, we restrict to the category ( \text{FinSet}_{\cong} ) (finite sets and bijections). Here:

• ( P(X) ) is the set of all full permutations of ( X ) (equivalent to the set of bijections ( X \to X ), represented as ordered lists).
• For a bijection ( f: X \to Y ), ( P(f): P(X) \to P(Y) ) takes a permutation ( [x_1, x_2, ..., x_n] ) to ( [f(x_1), f(x_2), ..., f(x_n)] ) (which is a full permutation of ( Y ), since ( f ) is bijective).

The Unit ( \eta ) #

The unit natural transformation ( \eta: \text{Id} \to P ) needs to map each element ( x \in X ) to a permutation of ( X ). For ( \text{FinSet}_{\cong} ), a natural choice that satisfies monad laws is mapping each element to the permutation where it's the "starting point" (or more formally, for ( X = {x_1, x_2, ..., x_n} ), ( \eta_X(x_i) ) is the permutation starting with ( x_i ) followed by the rest of the elements in a fixed order). This satisfies naturality: for any bijection ( f: X \to Y ), ( P(f)(\eta_X(x)) = \eta_Y(f(x)) ).

The Multiplication ( \mu ) #

Your partial description mentions ( \mu: P \circ P \to P ) forms a permutation from "the first element of each permutation in the permutation of permutations". For small sets (like ( |X|=2 )), this works: take ( P(P(X)) = {[[a,b],[b,a]], [[b,a],[a,b]]} ), then ( \mu ) maps ( [[a,b],[b,a]] ) to ( [a,b] ) (taking the first element of each sub-permutation) and ( [[b,a],[a,b]] ) to ( [b,a] ).

For larger sets, this rule doesn't produce a full permutation (since ( |P(X)| = n! \neq n ) for ( n>2 )). Instead, we can redefine ( \mu ) to compose permutations: if we treat ( P(X) ) as the symmetric group ( S_X ) (set of bijections ( X \to X )), ( \mu ) takes a permutation of permutations ( [\sigma_1, \sigma_2, ..., \sigma_{n!}] ) and returns the composition ( \sigma_{n!} \circ ... \circ \sigma_2 \circ \sigma_1 ) (represented as an ordered list). This aligns with monad associativity and unit laws.

If we relax the definition to let ( P(X) ) be the set of all non-repeating finite lists of elements from ( X ) (i.e., all k-permutations for ( k \geq 1 ), plus the empty list if desired), this becomes a well-behaved monad similar to the List monad, but with no duplicate elements.

The Functor ( P ) #

• For a set ( X ), ( P(X) = \bigcup_{k=1}^{|X|} { [x_1, x_2, ..., x_k] \mid x_i \in X, x_i \neq x_j \text{ for } i \neq j } ) (add ( [] ) to match the List monad's empty list).
• For a function ( f: X \to Y ), ( P(f): P(X) \to P(Y) ) maps a non-repeating list ( [x_1, ..., x_k] ) to ( [f(x_1), ..., f(x_k)] ). Note: if ( f ) isn't injective, the result may have duplicates—so this functor is often restricted to injective functions to keep outputs in ( P(Y) ).

The Unit ( \eta ) #

Just like the List monad, ( \eta_X: X \to P(X) ) maps each element ( x \in X ) to the singleton non-repeating list ( [x] ). This satisfies naturality: ( P(f)(\eta_X(x)) = [f(x)] = \eta_Y(f(x)) ).

The Multiplication ( \mu ) #

Flattening works similarly to the List monad, but we only retain lists with no duplicates. For example:

• ( \mu([[a,b], [c]]) = [a,b,c] ) (disjoint sub-lists, so no duplicates)
• For overlapping sub-lists like ( [[a,b], [b,c]] ), we can either restrict ( P(P(X)) ) to disjoint sub-lists, or define ( \mu ) to remove duplicates (though the latter breaks strict monad laws).

• If you mean full permutations (lists containing every element exactly once), you can't define a general endofunctor monad on ( \text{Set} ), but you can define a restricted monad on the category of finite sets and bijections, with multiplication based on permutation composition.
• If you mean arbitrary non-repeating lists, you can define a monad similar to List, though it's often constrained to injective functions to avoid duplicate elements.

内容的提问来源于stack exchange，提问作者Ben Sprott