Return to Answer

Writing [2] tells the compiler that this is a list, <> on lists is ++, so 2++2++2++2 is [2,2,2,2].

Writing [2] tells the compiler that this is a list, <> on lists is ++, so [2]++[2]++[2]++[2] is [2,2,2,2].

Another type of generalization is to apply the folds not to lists but to other Foldable data structures. Often, an immutable linear linked list is not the data structure you want for a given algorithm.

Another type of generalization is to apply the folds not to lists but to other Foldable data structures. Often, an immutable linear linked list is not the data structure you want for a given algorithm. One issue I did not get into above is that it’s a lot more efficient to add elements to the front of a list than to the back, and when the operation is not commutative, applying x on the left and the right of the operation aren’t the same. So you would need to use another structure, such as a pair of lists or binary tree, to represent an algorithm that could apply x on the right of <> as well as to the left.

times _ 0 = mempty times x 1 = x times x n | even n = y <> y | otherwise = x <> y <> y where y = times x (n `quot` 2) 

times :: Monoid a => a -> Word -> a times _ 0 = mempty times x 1 = x times x n | even n = y <> y | otherwise = x <> y <> y where y = times x (n `quot` 2)