Now that you’ve edited to ask an almost completely different question, I’ll give a different answer. Rather than point to a tutorial on maps and folds, I’ll just give one. In Scala, you first need to know how to create an anonymous function. It goes like so, from most general to more specific: (var1: Type1, … Read more
Here’s a fully parametric example: data Weird a = Weird a (a -> a) instance Foldable Weird where foldMap f (Weird a b) = f $ b a Weird is not a Functor because a occurs in a negative position.
A Fold for Every Occasion We can actually come up with a generic notion of folding which can apply to a whole bunch of different types. That is, we can systematically define a fold function for lists, trees and more. This generic notion of fold corresponds to the catamorphisms @pelotom mentioned in his comment. Recursive … Read more
Short answer: foldRight associates to the right. I.e. elements will be accumulated in right-to-left order: List(a,b,c).foldRight(z)(f) = f(a, f(b, f(c, z))) foldLeft associates to the left. I.e. an accumulator will be initialized and elements will be added to the accumulator in left-to-right order: List(a,b,c).foldLeft(z)(f) = f(f(f(z, a), b), c) fold is associative in that the … Read more
There’s a difference if your function isn’t associative (i.e. it matters which way you bracket expressions) so for example, foldr (-) 0 [1..10] = -5 but foldl (-) 0 [1..10] = -55. This is because the former is equal to 1-(2-(3-(4-(5-(6-(7-(8-(9-(10 – 0))))))))), whereas the latter is (((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10. Whereas because (+) is associative (doesn’t matter … Read more
I have found zfat (or, equally, zfit) works well for folding with HTML documents. za will toggle (open or close) an existing fold. zR opens all the folds in the current document, zM effectively re-enables all existing folds marked in the document. If you find yourself using folds extensively, you could make some handy keybindings … Read more
The key here is laziness. If the function you’re using for folding the list is strict, then neither a left fold nor a right fold will terminate, given an infinite list. Prelude> foldr (+) 0 [1..] ^CInterrupted. However, if you try folding a less strict function, you can get a terminating result. Prelude> foldr (\x … Read more
Some explanations are in order! What is the id function for? What is the role of? Why should we need it here? id is the identity function, id x = x, and is used as the equivalent of zero when building up a chain of functions with function composition, (.). You can find it defined … Read more
Welcome to the world of lazy evaluation. When you think about it in terms of strict evaluation, foldl looks “good” and foldr looks “bad” because foldl is tail recursive, but foldr would have to build a tower in the stack so it can process the last item first. However, lazy evaluation turns the tables. Take, … Read more
The easiest way to understand foldr is to rewrite the list you’re folding over without the sugar. [1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) now what foldr f x does is that it replaces each : with f in infix form and [] with x and evaluates the result. For example: sum [1,2,3] = foldr (+) 0 [1,2,3] [1,2,3] … Read more