First, the definition of your array monad transformer is wrong.
<!-- language: haskell -->
ArrayT m a = m (Array (m a))
The above type definition does not correctly interleave the underlying monad.
Following is an example value of the above data type.
<!-- language: lang-js -->
of([of(1), of(2), of(3)])
There are several problems with this data type.
1. There is no effect for the end of the array. 2. The effects are not ordered. Hence, they can be executed in any order. 3. The underlying monad wraps the individual elements as well as the entire array. This is just wrong.
Following is an example value of the correct array monad transformer type.
<!-- language: lang-js -->
of([1, of([2, of([3, of([])])])])
Note that.
1. There is an effect for the end of the array. 2. The effects are ordered. This is because the data type is defined recursively. 3. The underlying monad wraps the individual steps of the array. It doesn't wrap the entire array again.
Now, I understand why you want to define `ArrayT m a = m (Array (m a))`. If `m = Identity` then you get back an actual `Array a`, which supports random access of elements.
<!-- language: lang-js -->
of([of(1), of(2), of(3)]) === [1, 2, 3]
On the other hand, the recursive array monad transformer type returns a linked list when `m = Identity`.
<!-- language: lang-js -->
of([1, of([2, of([3, of([])])])]) === [1, [2, [3, []]]]
However, there's no way to create a lawful array monad transformer type which also returns an actual array when the underlying monad is `Identity`. This is because monad transformers are inherently algebraic data structures, and arrays are not algebraic.
The closest you can get is by defining `ArrayT m a = Array (m a)`. However, this would only satisfy the monad laws when the underlying monad is commutative.
Just remember, when defining a monad transformer data type.
1. The underlying monad must wrap at most one value at a time. 2. The underlying monad must be nested, to correctly order and interleave effects.
---
Coming back, the `Trampoline` monad is just the `Free` monad. We can define it as follows.
<!-- language: lang-js -->
// pure : a -> Free a const pure = value => ({ constructor: pure, value });
// bind : Free a -> (a -> Free b) -> Free b const bind = monad => arrow => ({ constructor: bind, monad, arrow });
// thunk : (() -> Free a) -> Free a const thunk = eval => ({ constructor: thunk, eval });
// MonadFree : Monad Free const MonadFree = { pure, bind };
// evaluate : Free a -> a const evaluate = expression => { let expr = expression; let stack = null;
while (true) { switch (expr.constructor) { case pure: if (stack === null) return expr.value; expr = stack.arrow(expr.value); stack = stack.stack; break; case bind: stack = { arrow: expr.arrow, stack }; expr = expr.monad; break; case thunk: expr = expr.eval(); } } };
I'll also copy my implementation of the array monad transformer from my [previous answer](https://stackoverflow.com/a/64480784/783743).
<!-- language: lang-js -->
// Step m a = null | { head : a, tail : ListT m a } // ListT m a = m (Step m a)
// nil : Monad m -> ListT m a const nil = M => M.pure(null);
// cons : Monad m -> a -> ListT m a -> ListT m a const cons = M => head => tail => M.pure({ head, tail });
// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b const foldr = M => f => a => m => M.bind(m)(step => step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);
Thus, when the underlying monad is `Free` then the operations are stack safe.
<!-- language: lang-js -->
// replicate :: Number -> a -> ListT Free a const replicate = n => x => n ? cons(MonadFree)(x)(thunk(() => replicate(n - 1)(x))) : nil(MonadFree);
// map : (a -> b) -> Free a -> Free b const map = f => m => bind(m)(x => pure(f(x)));
// add : Number -> Free Number -> Free Number const add = x => map(y => x + y);
// result : Free Number const result = foldr(MonadFree)(add)(pure(0))(replicate(1000000)(1));
console.log(evaluate(result)); // 1000000
Putting it all together.
<!-- begin snippet: js hide: true console: true -->
<!-- language: lang-js -->
// pure : a -> Free a const pure = value => ({ constructor: pure, value });
// bind : Free a -> (a -> Free b) -> Free b const bind = monad => arrow => ({ constructor: bind, monad, arrow });
// thunk : (() -> Free a) -> Free a const thunk = eval => ({ constructor: thunk, eval });
// MonadFree : Monad Free const MonadFree = { pure, bind };
// evaluate : Free a -> a const evaluate = expression => { let expr = expression; let stack = null;
while (true) { switch (expr.constructor) { case pure: if (stack === null) return expr.value; expr = stack.arrow(expr.value); stack = stack.stack; break; case bind: stack = { arrow: expr.arrow, stack }; expr = expr.monad; break; case thunk: expr = expr.eval(); } } };
// Step m a = null | { head : a, tail : ListT m a } // ListT m a = m (Step m a)
// nil : Monad m -> ListT m a const nil = M => M.pure(null);
// cons : Monad m -> a -> ListT m a -> ListT m a const cons = M => head => tail => M.pure({ head, tail });
// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b const foldr = M => f => a => m => M.bind(m)(step => step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);
// replicate :: Number -> a -> ListT Free a const replicate = n => x => n ? cons(MonadFree)(x)(thunk(() => replicate(n - 1)(x))) : nil(MonadFree);
// map : (a -> b) -> Free a -> Free b const map = f => m => bind(m)(x => pure(f(x)));
// add : Number -> Free Number -> Free Number const add = x => map(y => x + y);
// result : Free Number const result = foldr(MonadFree)(add)(pure(0))(replicate(1000000)(1));
console.log(evaluate(result)); // 1000000
<!-- end snippet -->
Hope that helps.

The array monad transformer is the same as the list monad transformer.
<!-- begin snippet: js console: true -->
<!-- language: lang-js -->
// Step m a = null | { head : a, tail : ListT m a } // ListT m a = m (Step m a)
// nil : Monad m -> ListT m a const nil = M => M.pure(null);
// cons : Monad m -> a -> ListT m a -> ListT m a const cons = M => head => tail => M.pure({ head, tail });
// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b const foldr = M => f => a => m => M.bind(m)(step => step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);
// append : Monad m -> ListT m a -> ListT m a -> ListT m a const append = M => m1 => m2 => foldr(M)(cons(M))(m2)(m1);
// pure : Monad m -> a -> ListT m a const pure = M => x => cons(M)(x)(nil(M));
// bind : Monad m -> ListT m a -> (a -> ListT m b) -> ListT m b const bind = M => m => f => foldr(M)(x => append(M)(f(x)))(nil(M))(m);
// MonadListT : Monad m -> Monad (ListT m) const MonadListT = M => ({ pure: pure(M), bind: bind(M) });
// MonadArray : Monad Array const MonadArray = { pure: x => [x], bind: a => f => a.flatMap(f) };
// MonadListArray : Monad (ListT Array) const MonadListArray = MonadListT(MonadArray);
// fromArray : Monad m -> Array a -> ListT m a const fromArray = M => a => a.reduceRight((xs, x) => cons(M)(x)(xs), nil(M));
// lift : Monad m -> m a -> ListT m a const lift = M => m => M.bind(m)(pure(M));
// foo : Nat -> ListT Array Nat const foo = x => x === 0 ? fromArray(MonadArray)([0, 1]) : lift(MonadArray)([0, 1]);
// associativityLHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c const associativityLHS = M => m => k => h => M.bind(M.bind(m)(k))(h);
// associativityRHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c const associativityRHS = M => m => k => h => M.bind(m)(x => M.bind(k(x))(h));
// lhs :: ListT Array Nat const lhs = associativityLHS(MonadListArray)(foo(0))(foo)(foo);
// rhs :: ListT Array Nat const rhs = associativityRHS(MonadListArray)(foo(0))(foo)(foo);
console.log(JSON.stringify(lhs) === JSON.stringify(rhs)); console.log(JSON.stringify(lhs));
<!-- end snippet -->
Note that each step of the list is wrapped in the argument monad. This allows other monadic actions to be interleaved and it's necessary to preserve the monad laws if the argument monad is not commutative.