I'd definitely like to see an explanation of what's going on, both at a high level and the specifics of the code. As a Haskell beginner-intermediate, I don't really know what most of those functions are doing (much less the context of what that function's purpose is), but I feel I could probably understand an explanation if it were given.
foldr is a combination map/reduce in one. It takes a value (the accumulator), runs a function on the rightmost value in a list called str (that's why it's 'foldr'), and combines the two together into a new accumulator value.
Let's say we have a list of numbers, the addition operator, and an accumulator of 0.
foldr op acc list
foldr + 0 [1, 2, 3, 4]
a = 0, list = [1, 2, 3, 4]
a = 0 + 4, list = [1, 2, 3]
a = 4 + 3, list = [1, 2]
a = 7 + 1, list = [1]
a = 8, list = []
Result is 8
One thing to note is that this walks the list 'backward', and in Haskell it's a singly linked list. That means that each time it has to walk the full list. I believe this is why it's O(n^2).
It looks like the accumulator starts with (buf_empty bufOps), which from context I assume is an empty buffer structure. The operator is (flip (but_append bufOps)), which looks like it adds values onto the bufOps structure when called. Each time it goes through this process, it appends one element.
Because they're using foldr and the list is walked 'backward', this has the natural side effect that the order of the items in strs is reversed as it's added to bufOps.
New version:
buf_concat bufOps $ reverse strs
The $ is a way of controlling precedence in Haskell, you can replace it with parenthesis. So we get:
buf_concat bufOps ( reverse strs )
So reverse just reverses the order of a list, getting things in the order the code wants them. Then it calls buf_concat with the current structure and the items it wants added. So instead of taking one existing list and adding 6 new elements at the end one at a time, it takes one existing list and adds a list of 6 elements to the end once.
It seems like a relatively simple change. I wonder if using foldl or foldl' to avoid having to rewalk the list every time would have performance similar to the new line.
I find the new line simpler and cleaner either way, but was the choice of a right-fold the cause of the performance problem?
GHCI has a debugger. You can step into an expression and watch as Haskell evaluates it, in full lazy order.
Even if you understand lazy evaluation in theory, I recommend taking some non-trivial (but not too large) expression and :step'ing through the whole evaluation sometime, just to train your intuition.
Comments
I'd definitely like to see an explanation of what's going on, both at a high level and the specifics of the code. As a Haskell beginner-intermediate, I don't really know what most of those functions are doing (much less the context of what that function's purpose is), but I feel I could probably understand an explanation if it were given.
I think I know enough Haskell to explain.
Old version:
foldr is a combination map/reduce in one. It takes a value (the accumulator), runs a function on the rightmost value in a list called str (that's why it's 'foldr'), and combines the two together into a new accumulator value.Let's say we have a list of numbers, the addition operator, and an accumulator of 0.
One thing to note is that this walks the list 'backward', and in Haskell it's a singly linked list. That means that each time it has to walk the full list. I believe this is why it's O(n^2).It looks like the accumulator starts with (buf_empty bufOps), which from context I assume is an empty buffer structure. The operator is (flip (but_append bufOps)), which looks like it adds values onto the bufOps structure when called. Each time it goes through this process, it appends one element.
Because they're using foldr and the list is walked 'backward', this has the natural side effect that the order of the items in strs is reversed as it's added to bufOps.
New version:
The $ is a way of controlling precedence in Haskell, you can replace it with parenthesis. So we get: So reverse just reverses the order of a list, getting things in the order the code wants them. Then it calls buf_concat with the current structure and the items it wants added. So instead of taking one existing list and adding 6 new elements at the end one at a time, it takes one existing list and adds a list of 6 elements to the end once.It seems like a relatively simple change. I wonder if using foldl or foldl' to avoid having to rewalk the list every time would have performance similar to the new line.
I find the new line simpler and cleaner either way, but was the choice of a right-fold the cause of the performance problem?
No, foldr walks through the list forward, and exactly once. Your example is evaluated as
Is there an (easy) way to see what/how haskell evaluates such code (ie: step through)? Something like explain from sql or disassemble from lisp?
GHCI has a debugger. You can step into an expression and watch as Haskell evaluates it, in full lazy order.
Even if you understand lazy evaluation in theory, I recommend taking some non-trivial (but not too large) expression and :step'ing through the whole evaluation sometime, just to train your intuition.
Just so no one reading is confused, should be: Result is 10 in foldr example. Just forgot one element from list.
You're right. Good catch.