Thanks to everyone for the nice solutions to this puzzle, here and on reddit: http://www.reddit.com/r/haskell/comments/fu6el/a_practical_haskell_puzzle/ There were two basic approaches. One was to use GADTs and higher-rank types to reduce the amount of type trickery needed. One nice example is apfelmus' solution here in this thread, and several people on reddit suggested using use thrists package: http://hackage.haskell.org/package/thrist The other approach is to use some kind of generics. In any case, there does not appear to be any reasonable way to handle this simple and common situation in Haskell without extensions. I challenge the Haskell community to add these extensions to the Haskell standard in Haskell 2012! Lennart proposed using type-level numbers and reification, but I'm not sure about the full details of that solution. Does it use Haskell extensions, and if so, which ones? Thanks, Yitz