Hello, We know about Foldable, but sometimes you just want more functionality like: give me the rest of the string! Or a function to build pieces back together. I've been experimenting a bit and come up with 6 flavors of Iterators that do the same thing. Of course they all work for containers like ByteStrings, Text. 1) Haskell98 version (I like) data Iterator98 list ele = Iterator98 { next98 :: Maybe (ele, Iterator98 list ele), ... rest98 :: list, concat98 :: [list] -> list } -- How we can create an Iterator98 listIter98 :: [a] -> Iterator98 [a] a -- How the sum type looks sum98 :: (Num n) => Iterator98 listN n -> n Performance: *3 I'll also usually give the type of the constructor and sum functions. I also benchmarked the sum functions for [] and compared them to the best sum function I could come up with (which is significantly faster than the sum in Prelude!!! because it's strict. Whoever came up with the idea of making it non-strict, must have been drunk at the time :)). I like how handy and simple typed the Haskell98 version is. There are absolutely no superfluous Types or Contexts. However, *3 is quite a heavy penalty and it might even get worse when more functions are added. 2) Haskell98 Explicit (ambivalent) data IteratorExplicit98 iter list ele = IteratorExplicit98 { iterExplicit98 :: iter, nextExplicit98 :: iter -> Maybe (ele, iter) ... restExplicit98 :: iter -> list } listIterExplicit98 :: [a] -> IteratorExplicit98 [a] [a] a sumExplicit98 :: (Num n) => IteratorExplicit98 it list n -> n Performance: *1 It is explicit and it is still quite nice to use. There is however always that extra argument. Note: `iter` and `list` could potentially be different (in all examples). They are in Haskell however usually the same. Performance could be different, if you create and destroy a lot of data of type IteratorExplicit98. However, that won't usually be the case. 3) TypeFamilies (I don't like) class IteratorTF i where type ListTF i type ElemTF i nextTF :: i -> Maybe (ElemTF i, i) ... restTF :: i -> ListTF i instance IteratorTF2Class [ele] ele where ... sumTF :: (Num n, IteratorTF it, ElemTF it ~ n) => it -> n Performance: *1 I used to like type families. But now I'm a bit fed up with ~ contexts. This would be the "Rust" version. Interesting point: List and Elem functions could be separated into two classes. I.e. Note that no list type exists in the type of "sum". 4) TypeFamilies2 (ambivalent) class IteratorTF2Class list ele where data IteratorTF2 list ele nextTF2 :: IteratorTF2 list ele -> Maybe (ele, IteratorTF2 list ele) ... restTF2 :: IteratorTF2 list ele -> list instance IteratorTF2Class [ele] ele where data IteratorTF2 [ele] ele = ListIterTF2 [ele] sumTF2 :: (Num n, IteratorTF2Class list n) => IteratorTF2 list n -> n Performance: *1 Better than the last. However, IteratorTF2Class, IteratorTF2 are two Type-ish things where one would be preferred. This is my preferred method where all functions are carried in the type. 5) MultiParameterTypeClasses and Functional Dependencies (ambivalent) class IteratorMPTC iter list ele | iter -> list, iter -> ele where nextMPTC :: iter -> Maybe (ele, iter) ... restMPTC :: iter -> list instance IteratorMPTC [a] [a] a where sumMPTC :: (Num n, IteratorMPTC it list n) => it -> n Performance: *1 About the same as 3). The user will still be exposed to various individual types ":: it". That is not as bad as it is in "Rust", since (as already stated) in Haskell usually "list == it". This is similar to the parsec approach. class (Monad m) => Stream iter m ele | iter -> ele Parsec has no "rest" function so the "list" type is not needed. But they have an additional monad type. 6) Existential Quantification (my favorite) data IteratorEQ list ele = forall iter . IteratorEQ { iterEQ :: iter, nextEQ :: iter -> Maybe (ele, iter) ... restEQ :: iter -> list } listIterEQ :: [a] -> IteratorEQ [a] a sumEQ :: (Num n) => IteratorEQ list n -> n Performance: *1 Looks as nice as Haskell98 and is as fast as Haskell98Explicit. Btw. This is probably how It would be done in "C" with iter = void*. Additional thoughts: * Do we really need the "list" type. Couldn't we simply return iterators instead of the original "list" type. In 3) and 5), they will *usually* be the same anyway. * In 3) and 5) the typeclasses could be split to separate ele and list. * On the other hand combining Iterators will be very annoying for 3) and 5) data ZipIterator ... instance IteratorMPTC (ZipIterator (?) (elem, elem')) ? (elem, elem') where zip :: (IteratorMPTC iter list elem, IteratorMPTC iter' list' elem') -> ZipIterator ? (elem, elem') Which is your favorite? Why? Did I forget any good ones? Cheers Silvio