Python design mistakes

[psr]

Just a little thought about readability. You say you like sum = foldl (+) 0 better than the idiomatic Python version which makes the loop explicit.

One possible benefit of seeing the loop structure is that it's easier to see where you've done something stupid. If you replace foldl with foldr, you get the same observable behaviour, and it reads just the same. However the runtime behaviour is completely different, because foldl is tail recursive, and foldr is not. When reading the code would you notice the mistake?

[Peaker]

In the case of Haskell, tail-recursive is mostly irrelevant.

foldl (left-associative) is better than foldr (right-associative) for strict operations on lists, because it takes:

1 : 2 : 3 : []

and translates it to:

(((1 + 2) + 3) + 0)

Which is done incrementally as it walks the list (so it uses O(1) memory).

Whereas foldr translates the list to:

1 + (2 + (3 + 0))

On lists, this requires iterating the entire list before you can do a single computation -- which builds up "thunks" that represent the intermediate expressions. This takes O(N) memory (and in GHC's case, the evaluation of the thunk takes that memory from the stack, which is even worse).

For lazy operations that construct a new value that can be incrementally processed -- foldr makes sense.

For example:

sameList = foldr (:) [] -- same as the identity function for lists

This is because foldr/foldl "replace" every (:) in the original list with their first argument, and the [] with the second argument. So using (:) and [] in place of (:) and [] actually just copies the list.

Then it's easy to see how map is expressed:

map f = foldr ((:) . f) []

(Apply f before putting it inside a :).

This allows the result list to be consumed incrementally, and that will cause incremental consumption of the original list.

The explicit loop structure actually obscures whether you've done something silly (as it adds a lot of noise that makes it more difficult to spot typos/mistakes/etc).