Are cons and snoc really O(n) operations?

[JeffreyBenjaminBrown]

That's what the documentation on Hackage says. I would have expected them to be O(1).

[chessai]

Edited your link to point to cons instead of the section on Folds.

[cartazio]

yes, it has to. vectors are flat, prepending/appending a single element requires a vector with 1 additional slot! Theres perhaps alternative design approaches which would do a memmove/reallocation, but thats kinda not something in vector as its designed.

uncons/unsnoc can be O(1), via slicing.

if you know of an O(1) worst case approach that works for flat sequence in virtual memory structures rather than nested pointer/references, please do share.

[JeffreyBenjaminBrown]

Ah, yes, of course, you're right. Thanks!