Finding the Missing 'Reduce' Typeclass from Finger Tree Article

Question

Yesterday's Wikibender that started with this stackoverflow qestion on Comonads ended up at MarkCC's article on Finger Trees. In the article he makes extensive use of the `Reduce` type class. He writes about this typeclass as if it is a very common and frequently use library, but I cannot find it on hackage, nor can I find enough documentation to really understand the code. Can someone help me understand what the `Reduce` typeclass is doing, how the `(-<)` and `(>-)` operators work, and what should tell me about the code in the article (copied below)? Code Listing from Finger Trees Done Right (I hope): Listing 1: instance declaration for Node ``` instance Reduce Node where reducer (-<) (Node2 a b) z = a -< (b -< z) reducer (-<) (Node3 a b c) z = a -< (b -< (c -< z)) reducer (>-) (Node2 b a) = (z >- b) >- a reducer (>-) (Node3 c b a) = ((z >- c) >- b) >- a ``` Listing 2: instance declaration for FingerTree ``` instance Reduce FingerTree where reducer (-<) Empty zero = zero reducer (-<)…

Accepted Answer

Given that `reduce` is a common alternate name for a "fold" function, I'd guess that it's something similar to the `Foldable` type class. The instance definitions seem to make sense as such, as well.

The `Foldable` class can be defined using just `foldr`, which has the type signature `foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b`, whereas the `reducer` in that code appears to be `reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b`. Other than a different argument order, it should work the same.

Note that the operators are just arguments to the function--you could replace them all with `f` or another similarly generic identifier. Using an operator as the name of a binary function argument is... a slightly unusual choice, but it does emphasize some aspects of the structure of the fold, I guess.

Finding the Missing 'Reduce' Typeclass from Finger Tree Article

Solution

Problem

Related problems