Skip to main content
refreshing this question to focus on any kind of map from Bag to List.
Source Link
Ben Sprott
  • 1.3k
  • 14
  • 23

Transformation from the Bag monad to the LIstList monad

The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the set along with an equivalence between any two strings that are equal due to the commutativity of the elements. So, we can write the Bag data structure in terms of a monad $Bag = (B, \mu_B, \eta_B)$. This is also true of lists. Lists are very much like bags, except there is no commutativity equivalence. They are litterally strings, so the theory of Lists (ie the category of algebraic structures which has an adjunction into Set that generates the LIst monad) is just free monoids. So, we can write the List data structure as a monad, $List = (L, \mu_L, \eta_L)$. I am looking for a map between Monads that will take the Bag monad to the listList monad. What Does this map exist? Are there several ways to do it?

Edit: I would like is for the liststhink I get why my desire to be exactly all the strings written in exactly theturn Bag elements to every permutation is a bad idea. This question conflates two desires of the bagmine. For instanceFirst, take an element in a freee commutative monoid $x = abc = cba \ldots$I just want to see the transformation from Bag to List, whatever that may be. The map $M: Bag \rightarrow List$ would take $x$ Second, I have been trying to everyfind a Monad-like permutation of the elementsgadget. I think I found that in terms of an operad $b$over here. Does this map exist? I just forgot, so apologies.

Transformation from the Bag monad to the LIst monad

The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the set along with an equivalence between any two strings that are equal due to the commutativity of the elements. So, we can write the Bag data structure in terms of a monad $Bag = (B, \mu_B, \eta_B)$. This is also true of lists. Lists are very much like bags, except there is no commutativity equivalence. They are litterally strings, so the theory of Lists (ie the category of algebraic structures which has an adjunction into Set that generates the LIst monad) is just free monoids. So, we can write the List data structure as a monad, $List = (L, \mu_L, \eta_L)$. I am looking for a map between Monads that will take the Bag monad to the list monad. What I would like is for the lists to be exactly all the strings written in exactly the elements of the bag. For instance, take an element in a freee commutative monoid $x = abc = cba \ldots$. The map $M: Bag \rightarrow List$ would take $x$ to every permutation of the elements of $b$. Does this map exist?

Transformation from the Bag monad to the List monad

The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the set along with an equivalence between any two strings that are equal due to the commutativity of the elements. So, we can write the Bag data structure in terms of a monad $Bag = (B, \mu_B, \eta_B)$. This is also true of lists. Lists are very much like bags, except there is no commutativity equivalence. They are litterally strings, so the theory of Lists (ie the category of algebraic structures which has an adjunction into Set that generates the LIst monad) is just free monoids. So, we can write the List data structure as a monad, $List = (L, \mu_L, \eta_L)$. I am looking for a map between Monads that will take the Bag monad to the List monad. Does this map exist? Are there several ways to do it?

Edit: I think I get why my desire to turn Bag elements to every permutation is a bad idea. This question conflates two desires of mine. First, I just want to see the transformation from Bag to List, whatever that may be. Second, I have been trying to find a Monad-like permutation gadget. I think I found that in terms of an operad over here. I just forgot, so apologies.

Source Link
Ben Sprott
  • 1.3k
  • 14
  • 23

Transformation from the Bag monad to the LIst monad

The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the set along with an equivalence between any two strings that are equal due to the commutativity of the elements. So, we can write the Bag data structure in terms of a monad $Bag = (B, \mu_B, \eta_B)$. This is also true of lists. Lists are very much like bags, except there is no commutativity equivalence. They are litterally strings, so the theory of Lists (ie the category of algebraic structures which has an adjunction into Set that generates the LIst monad) is just free monoids. So, we can write the List data structure as a monad, $List = (L, \mu_L, \eta_L)$. I am looking for a map between Monads that will take the Bag monad to the list monad. What I would like is for the lists to be exactly all the strings written in exactly the elements of the bag. For instance, take an element in a freee commutative monoid $x = abc = cba \ldots$. The map $M: Bag \rightarrow List$ would take $x$ to every permutation of the elements of $b$. Does this map exist?