The standard libraries of strict languages agree. Python's `functools.reduce` and JavaScript's `Array.prototype.reduce` perform strict left folds equivalent to Haskell's `foldl'`.
Interestingly, JavaScript also has `Array.prototype.reduceRight`, but it's not equivalent to a `foldr`. It processes the list from right-to-left, so is approximately equivalent to `reverse` followed by `foldl'`.
I don't understand how that's different in practice. Can you elaborate?
`reduceRight` processes and accumulates right-to-left, so it doesn’t have the short-circuiting ability of `foldr`.
But foldl vs. foldl' is more about a badly-optimized implementation detail than anything else. It's very fair to qualify it as "in Haskell".
> foldl/3 is tail recursive and is usually preferred to foldr/3.
In most language, you should generally prefer foldleft to foldright as foldright is not tail-recursive.
(and chances are that you will still leak memory like crazy)
uncurry (/) . foldl' (\(s,l) x -> (s+x,l+1)) (0,0)
uncurry (/) . foldl' (\(!s,!l) x -> (s+x,l+1)) (0,0)> foldr can possibly save on work if the reducing function is lazy in its second argument, and the result list is not entirely consumed. In fact, foldr can operate on infinite lists this way, while foldl cannot.
And to support the idea, we look at an implementation of map in terms of foldr. But I assume that if you're programming in Haskell and you want to map a function over a list, you'll use map instead of defining an ad-hoc mapped version of your function with foldr. This would be a great example of why, when we're defining map itself, we use foldr instead of foldl. But I wanted to see an example of why I might want to use foldr instead of foldl, not why I might want to reimplement map from scratch. They couldn't imagine a reduction that produced a scalar instead of another vector?
Of course, if you're reducing the list to a scalar, you lose all the benefits this article wants to claim.
Not quite - for example, these both benefit from foldr, despite each producing a scalar:
and, or :: [Bool] -> Bool
and = foldr (&&) True
or = foldr (||) False
The distinction lies not so much in "are you reducing to a scalar?" as "can your binary operation be productive without evaluating its second parameter?" - or, if you prefer, "is it ever lazy in its second parameter?". If so, then foldr may be appropriate.
Because they suck.
That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
Yes, exactly. A lazy list is just another term for generator. If you hold on to a reference to the head of such a list as you run the generator, then you'll consume a lot of memory and will end up with a strict list, and also you'll be sad. But if you don't hold on to that reference, then it will be very efficient.
> That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
Especially strings as lists of characters. That was a mistake. Well, in some sense, character data has to be a list, since with Unicode you really can't efficiently index a string... unless it's a rope and you apply the sorts of tools that xi does (e.g., keeping track of character counts per rope segment, etc.). But strings should be sufficiently opaque that arrays, lists, and ropes are all equally able to implement their semantics.
It is also worth noting that haskell has library specified fusion rules so the closure isn't even allocated most of the time. So
sum (take 10 [0..])
Technically, if you want to really understand how the "IO monad" does its thing, this is actually how it works. Technically your program declares a probably-infinite data structure that contains all possible paths your code could take, e.g., if you have a "if user input is negative then do X else do Y", what you really have is a data structure representing the if-then clause. What keeps the infinite data structure from being manifested in RAM is that the whole thing is resolved lazily, so only one branch will be actually evaluated. That's why the "IO monad" is actually pure; it simply "purely" creates a huge data structure that is resolved by an interpreter later. In the theoriest of theories, an IO value in Haskell really doesn't execute anything either and the whole language is pure... it is only the interpretation of the IO value that finally interfaces with the real world.
It isn't always the most helpful perspective and you can become an expert Haskell programmer without ever looking at your program this way, but technically, under the theory hood, that's what's happening.
The majority of langauges web frameworks are written in do not have linked lists, at all.
Python doesn't. Ruby doesn't. Java doesn't.
Wrong. Intrusive, doubly-linked lists are extremely performant and useful in the right places, especially if you have callbacks which store a pointer to a list element (this often happens with device drivers in low level programming), or if the elements can belong to several lists.
The Linux kernel, for example, makes plenty use of linked lists.
> IMO, like goto’s it’s better to just forget they exist.
Wrong again. In a language without automatic memory management and without scoped destruction (cough C cough), they are immensely useful. Again, refer to the Linux kernel. Or any competently written, non-trivial C program for that matter. Note: I'm not defending C here, I'm defending correctly used gotos in C programs.
IDK if this is the case for device drivers, but AFAICT device drivers tend to preallocate memory on loading and manage it locally.
Look, I'm not saying that linked lists can replace arrays. In fact, I almost always use arrays instead of linked lists. What I'm arguing against is the notion that arrays always trump linked lists, which is false, and repeating that meme shows a lack of deeper understanding.
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.
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.
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.
> The way modern memory works linked lists are practically a denial of service attack on system performance.
and
> IMO, like goto’s it’s better to just forget they exist.
That's as close to "never use a linked list" as you can get without saying that literal sentence.
So do arrays, FYI.
> It's really better to aim for non-circularity and to avoid the need for locks.
How does an array avoid the need for a lock where a linked list needs one?
Now sure, if it’s small and you’re only creating then reading it once then that’s fine. But, you’re assumptions need to be accurate or you just created a problem.
But, yeah, if you’re relying heavily on random access, pick a vector/array or some kind of tree/hash table.
They're quite useful in functional languages.
In Haskell in particular they can have nice performance effects if you use them sensibly.
That's for streaming I/O. Lazy linked lists are appropriate for streaming without side effects
Don't blame the language, & learn to use the right data structure for the job.
Not trying to throw any of the other languages mentioned under the bus, I do not know them well enough to know what list structure they default too or more idiomatically rely on.
In python, for example let's say:
def f:
arr = [0, 1, 2]
g(arr)
return arr[0]
Languages that default to using linked lists do not have this problem.
there are immutable non-linked list datastructures (the most obvious one in python are tuples)
def f(some_tuple):
part_one = take_the_last_three_parts_of_the_tuple(some_tuple)
part_two = append_to_self(part_one)
part_three = tail(part_two)
>>> x = ([1,2,3,4],"whatever")
>>> x[0].append('z')
>>> x
([1, 2, 3, 4, 'z'], 'whatever')
>>> def gotcha():
... z = globals()['x']
... z = list(z)
... z.append("I've seen'em do it man!")
... globals()['x'] = tuple(z)
...
>>> x = (1,2,3,4)
>>> gotcha()
>>> x
(1, 2, 3, 4, "I've seen'em do it man!")Python is not a functional programming language....
You saying before the call to "g", you would make a deep copy of "arr" and that's faster to do with a singly linked list? Could you explain why?
What you can still do is cons new elements to the front of your copy. No other copy of the list will be affected. Because the list is singly linked, other owners of references into the list cannot walk back to observe your elements. They can even cons their new elements to the "same" list without any conflict.
All this is very useful if you want to process something with a stack, such that sub-operations can push elements to the stack that they have to remove again before returning. Pushing x and y to the stack is just constructing the list y : x : stack. Popping y and x from the stack when you're done is a no-op: "stack" is still a reference to the stack as it was before these operations.
I'd still have to say that Singly Linked List arn't ideal for that either, better use a persistent hash array mapped trie backed list instead.
there's a real memory overhead for that structure.
1. Clojure uses wide balanced trees as its general-purpose ordered collection.[0] These have probably already been adapted for Haskell, and they offer persistence and fast random access and some degree of cache-friendliness. In my opinion it makes better trade-offs as a general-purpose structure.
2. By passing an &[usize] in Rust, or a const size_t* in C (i.e. by making g accept a read-only pointer), you can be guaranteed that g doesn't modify the array.
[0]: https://hypirion.com/musings/understanding-persistent-vector...