[Haskell-cafe] attoparsec and vectors

Gregory Collins greg at gregorycollins.net
Wed Jun 29 04:42:32 CEST 2011

On Tue, Jun 28, 2011 at 6:20 PM, Eric Rasmussen <ericrasmussen at gmail.com> wrote:
> It runs quickly, but I naively thought I could outperform it by reworking
> "many" to build a vector directly, instead of having to build a list first
> and then convert it to a vector:
> manyVec :: Alternative f => f a -> f (V.Vector a)
> manyVec v = many_v
>   where many_v = some_v <|> pure V.empty
>         some_v = V.cons <$> v <*> many_v

That's an O(n^2) loop, and a thunk leak to boot. If you don't know the
size of the vector ahead of time, the only way I can think of to beat
Vector.fromList is to use a mutable vector with a "highwater" mark,
and double the size if you fill it. At the end, you'd use
"unsafeFreeze" to turn the mutable vector into a pure one, and
"unsafeTake" to truncate the vector into the correct size.

For an example of a similar technique (minus the freezing part), I did
a similar thing in the hashtables library:


It's unlikely to be worth the extra effort except for extremely
performance-critical code.

Gregory Collins <greg at gregorycollins.net>

More information about the Haskell-Cafe mailing list