Re:It never makes sense to use foldl on lists in Haskell (2019)
by adwn on Saturday March 21, 2020 @05:36AM
(#22645501)
> Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants.
Re-read my original post: "[...] especially if you have callbacks which store a pointer to a list element [...]"
This happens all the time in kernel code or bare-metal programming.
What else can I say? Open the Linux source code [1] and see for yourself.
Re:It never makes sense to use foldl on lists in Haskell (2019)
by Retric on Saturday March 21, 2020 @06:20AM
(#22645622)
Look we can all agree if you’re writing ASM your going to use goto’s. Further if linked lists are tiny or rarely used, it’s not a problem. If you can ensure the data stays in L2 cache it’s far less of an issue. If any number of things they don’t create problems, but frankly the general case encountered by most programmers are not that.
PS: If you don’t feel like pointing to a concrete example, I am going to counter with 99% of the stuff you can find here: www.google.com.
If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.