Right, the trick is to not use concrete types when unnecessary. As the OP makes clear, it doesn't make sense to stuff all these use cases into a single concrete type.

> Note also that the clone issue and the borrow issue are not applicable to Haskell

No, but Rust switching to a typeclass-based iterator syntax should help with this too.

> the performance characteristics of Range may be hard to replicate while implementing Foldable or Traversable.

I don't see why - rustc generally does (and must do) a great job of specializing parametric code.