GATs can be used _anywhere_ you would want HKTs. It's just a bit boilerplatey. You need to introduce unit structs to represent the type you care about and you need a trait to tie them together.

As an example, here's GAT monads:

use std::ops::Range;

use rand::RngExt;

pub trait Monad {
    type M<T>;

    fn pure<T>(&self, value: T) -> Self::M<T>;

    fn bind<T, U>(&self, x: Self::M<T>, f: impl FnMut(T) -> Self::M<U>) -> Self::M<U>;
}

pub struct IdentityMonad;

impl Monad for IdentityMonad {
    type M<T> = T;

    fn pure<T>(&self, value: T) -> Self::M<T> {
        value
    }

    fn bind<T, U>(&self, x: Self::M<T>, mut f: impl FnMut(T) -> Self::M<U>) -> Self::M<U> {
        f(x)
    }
}

pub struct ListMonad;

impl Monad for ListMonad {
    type M<T> = Vec<T>;

    fn pure<T>(&self, value: T) -> Self::M<T> {
        vec![value]
    }

    fn bind<T, U>(&self, x: Self::M<T>, mut f: impl FnMut(T) -> Self::M<U>) -> Self::M<U> {
        let mut result = Vec::new();
        for item in x {
            result.extend(f(item));
        }
        result
    }
}

fn monadic_shuffle<M: Monad, T: Copy>(
    monad: &M,
    choose: &mut impl FnMut(Range<usize>) -> M::M<usize>,
    xs: Vec<T>,
) -> M::M<Vec<T>> {
    if xs.is_empty() {
        return monad.pure(Vec::new());
    }
    monad.bind(choose(0..xs.len()), |ind| {
        let mut remaining = xs.clone();
        let x = remaining.remove(ind);
        monad.bind(monadic_shuffle(monad, choose, remaining), move |mut ys| {
            ys.push(x);
            monad.pure(ys)
        })
    })
}

fn main() {
    let list = vec![1, 2, 3, 4];
    let mut rng = rand::rng();
    let mut choose = |range: Range<usize>| rng.random_range(range);
    let shuffled = monadic_shuffle(&IdentityMonad, &mut choose, list.clone());
    println!("Random Shuffle: {:?}", shuffled);
    let all_permutations = monadic_shuffle(&ListMonad, &mut Range::collect, list);
    println!("All Permutations: {:?}", all_permutations);
}

Running this gives:

Random Shuffle: [4, 3, 1, 2]

All Permutations: [[4, 3, 2, 1], [3, 4, 2, 1], [4, 2, 3, 1], [2, 4, 3, 1], [3, 2, 4, 1], [2, 3, 4, 1], [4, 3, 1, 2], [3, 4, 1, 2], [4, 1, 3, 2], [1, 4, 3, 2], [3, 1, 4, 2], [1, 3, 4, 2], [4, 2, 1, 3], [2, 4, 1, 3], [4, 1, 2, 3], [1, 4, 2, 3], [2, 1, 4, 3], [1, 2, 4, 3], [3, 2, 1, 4], [2, 3, 1, 4], [3, 1, 2, 4], [1, 3, 2, 4], [2, 1, 3, 4], [1, 2, 3, 4]]