Is there a data type that's spine lazy like a list, but can be seeked (sought?) efficiently? IntMap and Sequence are spine strict so if you take the head element all the elements are forced even if their contents are not. E.g., 'Sequence.index (Sequence.fromList [0..]) 0' will diverge, but obviously 'head [0..]' won't. I can get what I want from a list of lists where the outer list is is 'iterate (drop n)' on the inner one... this is a kind of skip list, right? It seems like it should be possible to generalize this to multiple levels with increasing skip amounts, then I can seek relatively efficiently and won't force the spine beyond where I seek. Effectively, this is nested list like [[[a]]], where each level above the bottom is something like 'iterate (drop n) level_below'. Alternately, it should also be possible to do something fancy like a self-modifying data structure that constructs its index as you force bits of it, but this would require some hairy unsafePerformIO, I think. Has anyone heard of a data structure like this, either the plain list of lists or the self modifying magic one? Surely efficiently indexing a lazy list is something someone else has thought about? It looks like Luke Palmer's data-inttrie might be doing this, though it's not clear from the documentation. It looks like it lacks emptiness, so it doesn't apply to finite structures. lazyarray looks like it might be doing the magic self-modifying thing, though it wants a a static bounds right off the bat, which isn't much help when the whole point is to avoid having to figure out how long the input is.