Graded monoids: What does it mean to say a monoid is graded by another monoid? The question https://cs.stackexchange.com/questions/129236/creating-a-large-tuple-from-smaller-tuples-via-a-monad-or-applicative/129482#129482
regards the existence of a procedure which uses a monad for assembling tuples in the lambda calculus whose components are of possibly different type.
According to the only answer given, a tuple could be constructed using the graded monoid of finite sequences, if the tuple contained expressions of the same type. My first question is the following:

*

*What is the graded monoid of finite sequences?

For the case in which a tuple contains expressions of different type it is claimed that:

In theory we could have used any monoid graded by any other monoid, (for example the monoid of heterogeneous lists, graded by the monoid of lists of types -- if we wanted to be able to talk about heterogeneous tuples)the monoid of heterogeneous lists, graded by the monoid of lists of types.


*

*What does it mean to say a monoid is graded by another monoid? I can find discussions of graded monoids in the literature but not a clear explanation of what it means to say a monoid is graded by another monoid


*What exactly is the monoid of heterogeneous lists graded by the monoid of lists of types?
 A: There's a general description of graded objects, but for the purposes of just defining graded monoids it's possible to simplify:

A grading of a monoid $M$ by another monoid $N$ is just a homomorphism $\varphi : M \to N$. The preimages $\varphi^{-1}(n)$ are the graded components $M_n$ of $M$; the elements of $M_n$ are said to be of degree or grade $n$.

As a simple example, the monoid $\mathbb{N}^k$ is graded by $\mathbb{N}$ with the grading given by taking the sum of the components. Taking the monoid ring of this example produces the familiar grading of multivariate polynomials by total degree, although we need a somewhat different definition of what a grading of a ring is.

I don't quite know what "heterogeneous lists" means, but I can make a guess. Suppose you have a collection of types $T_i, i \in I$ indexed by a set $I$. Then you can construct the monoid of lists of elements where each element can be in any of the types $T_i$; equivalently, the monoid of lists of elements of the sum type $\coprod_i T_i$. This monoid admits a grading, which remember is just a homomorphism, by the monoid of lists of elements of $I$; this homomorphism is determined by sending each element to its type.
For example, suppose we have two types, strings and ints. A heterogenous list of strings and ints looks like

{"dog", 3, "mouse", "cat", 7, ...}

and the corresponding list of types is

{string, int, string, string, int, ...}

