But either way, you haven't done the same thing as the GP. It's not actually clear what the GP's algorithm is supposed to do, and I made the same reading mistake at first as well.
> I tend to think that as the accumulation condition gets more complicated, the for loop begins to be the clearer choice
You can just use recursion. It's very easy to translate a loop into a tight tail-recursive function in Haskell. The generated assembly code usually looks about the same.
In the most extreme case, you can just do a loop inside the State monad, which allows you to get (better defined) imperative semantics without mutability (although the compiler will often generate mutable-equivalent assembly when it sees that doing so is safe).
> This can lead to a bunch of allocation overhead for the intermediate lists
Haskell uses list fusion so this usually isn't a concern.
I transliterated the OP's example in another comment. It's a pretty straightforward recursive function of type e.g. "Int -> ByteString -> Int". Substitute ByteString with whatever constant-lookup data structure you want.