How do purely functional languages handle index-based algorithms?

Believe it or not, that function is actually built-in to Haskell.

> scanl (+) 0 [1..9]
[0,1,3,6,10,15,21,28,36,45]

So the broad answer is very often: There are convenient list-related primitives that we build up from rather than writing loops by hand. People like to say that recursion is the closest analogue in FP to “for loops” in imperative programming. While that may be true, the average functional program uses a lot less explicit recursion than the average imperative program uses for loops. Most of what we do (especially with lists) is built up of map, filter, foldl, and all of the other (highly-optimized) goodies in Data.List, Data.Foldable, Data.Traversable, and the rest of base.

As for how we implement those functions, you can look at the source for scanl. The one on GHC is written a bit differently for efficiency reasons, but the basic gist is this

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl _ q [] = [q]
scanl f a (b:xs) = a : scanl f (f a b) xs

You don’t need indices. You need to keep track of the single previous value as you build the list, and we can do that with a function argument. If you genuinely do have an algorithm that needs random access to various indices, we have Data.Vector for that. But 99% of the time, the answer is “stop thinking about indices”.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)