My question is then: What's the best thing to use for "x", Void or ()? […] An alernative I've been considering is actually to create a Foo' type which actually does eliminate the i parameter
This is only a partial answer, but why not role your own i? And why not define Foo' in terms of Foo and whatever you end up using? data ThereIsNoIOnlyZuul -- intentionally left blank type Foo' e n = Foo ThereIsNoIOnlyZuul e n -- extra types included for clarity The reason I suggest this is that a) your own types are also documentation and b) you can change the behavior of your new type at will. Speaking of new types…
(Aside: AFAICT there's no reasonable way to implement anything like Foldable or Traversable to avoid the explicit "toList" function, right? […]) I suspect the canonical answer would be to use copious amounts of newtype. Downside: lots of wrapping and unwrapping. Upside: it's like an early Christmas!
Cheers, MarLinn