For whatever it's worth, here's how you would actually implement the reflexive-transitive closure of a relation in Prolog:

    subtype(gerbil, rodent).
    subtype(rodent, mammal).
    subtype(mammal, animal).

    transitive_subtype(S, T) :-
        subtype(S, T).
    transitive_subtype(S, T) :-
        subtype(S, U),
        transitive_subtype(U, T).

    reflexive_transitive_subtype(T, T).  % FIXME: should check if T is a type
    reflexive_transitive_subtype(S, T) :-
        transitive_subtype(S, T).

This terminates as expected:

    ?- transitive_subtype(gerbil, X).
    X = rodent ;
    X = mammal ;
    X = animal ;
    false.  % meaning "I have proved that there are no further solutions"

    ?- reflexive_transitive_subtype(gerbil, X).
    X = gerbil ;
    X = rodent ;
    X = mammal ;
    X = animal ;
    false.

or even:

    ?- reflexive_transitive_subtype(S, T).
    S = T ;
    S = gerbil,
    T = rodent ;
    S = rodent,
    T = mammal ;
    S = mammal,
    T = animal ;
    S = gerbil,
    T = mammal ;
    S = gerbil,
    T = animal ;
    S = rodent,
    T = animal ;
    false.

Left recursion can indeed be a problem in Prolog, but this is not a problematic case.

While the solution is composed neatly from functional primitives, the large amount of boxes of boxes are not ideal.

For example, Interleave stores a Vec<Box<Iterator>>, which it absolutely should for the general case. But Flatten only ever uses it with two iterators, so the Vec is an extra allocation that could've been avoided in Flatten's case.

For the specific case of flattening an infinite iterator of infinite iterators, once could simplify to:

    struct FlattenInfinite<I> where I: IntoIterator, <I as IntoIterator>::Item: IntoIterator {
        iters: <I as IntoIterator>::IntoIter,
        realized_iters: Vec<<I::Item as IntoIterator>::IntoIter>,
        cursor: usize,
    }

where the number of trailing ones in self.cursor specifies which iterator to yield the next element from.

Full example at https://play.rust-lang.org/?version=stable&mode=release&edit...

The `.expect()`s require that the solution is specific to an infinite iterator of infinite iterators.

(Edit: Better implementation that uses usize::trailing_zeros() instead of hand-counting trailing ones.)