zhanrnl/haskell-sofo — pull request #1 by matthewSorensen (2013-01-01 02:33:45+00:00)
Title: Incorrect Definition of mapWithIndex 

The definitions of *mapWithIndex* are not equivalent and the second doesn't typecheck as is. After correcting it, consider:

*Main> head $ mapWithIndex (,) [1..]
(0,1)
*Main> head $ mapWithIndex' (,) [1..]
^CInterrupted.

It is impossible to write a correct definition of *mapWithIndex* with *foldl* as foldl'ing over an infinite list can't terminate. It is possible to write an implementation with *foldr* that behaves correctly on infinite lists, but I think it is ugly and not pedagogically useful:

mapWithIndex' :: (Int -> a -> b) -> [a] -> [b]
mapWithIndex' f = map (uncurry f) . foldr (\x acc -> (0,x): map incFst acc) []
where incFst (a,b) = (a + 1, b)

The critical bit of this implementation is that it generates a little bit of the result before requiring the evaluation of the rest of the result. [sigfpe](http://blog.sigfpe.com/2007/07/data-and-codata.html) has a nice post explaining the relevance of this.

More interestingly, this is a great problem to introduce *unfoldr* with:

mapWithIndex' f l = unfoldr go (0,l)
where go (_,[]) = Nothing
go (n,(x:xs)) = Just (f n x,(n+1,xs))