suggestion: use lazy pattern matching for Monoid instances of tuples

Edward Kmett ekmett at
Mon Aug 19 16:14:54 CEST 2013

With foldMap one can have structures that get to explicitly reuse previous
intermediate results.

you a list with a more efficient fold by using LZ78 to identify
sharing with earlier parts of the list.

With foldr you can't exploit such regularity as you can merely append one
element at a time.

Less drastically, with foldMap, you can binary search a tree structure if
the foldMap preserves the original associativity of the structure.

The lens package uses this to navigate to keys in a Zipper over a Map to a
given key in O(log n) time borrowing the asymptotics from the balance of
the underlying structure.

In my current work I'm using "sequence-algebras" and "sequence-trees" to
exploit even more structure than foldMap gives me.

I'll probably write up an article at some point soon on the School of


On Mon, Aug 19, 2013 at 9:31 AM, Petr Pudlák <petr.mvd at> wrote:

>  This is exactly how I run into the Monoid problem. My original `foldr`
> version works fine, but when I saw this Gabriel's post:
> the monoid variant looked cleaner and nicer so I wanted to redesign my
> idea using monoids as well. And that was precisely when I realized that (,)
> isn't lazy enough.
> Could you elaborate a bit when/how the asymptotic difference occurs?
>   Best regards,
>   Petr
> Dne 08/19/2013 02:03 PM, Edward Kmett napsal(a):
> If you are looking into a tackling lazy foldr, I'd recommend also
> including or considering using foldMap as a basis. It can make an
> asymptotic difference for some folds. I sent Gabriel a version in that
> style. I'll dig up a copy and send it your way as well.
>  -Edward
> On Mon, Aug 19, 2013 at 3:29 AM, Petr Pudlák <petr.mvd at> wrote:
>>  Thank you all for the responses.
>> Edward's objection is very serious, I didn't think of it.
>> Because of it I retract the proposal, this would indeed create big
>> problems. (I just wish someone invents an oracle strictness analyzer...)
>> Instead, as suggested, I'll make a package with `newtype` wrappers for
>> tuples that will provide the extra-lazy monoid semantics. Any ideas for
>> what other type classes except `Monoid` (and `Semigroup`) could be
>> included? Or perhaps even other data types except tuples?
>> Dne 08/18/2013 11:21 PM, Gabriel Gonzalez napsal(a):
>> I'm guessing this proposal is related to this Stack Overflow answer you
>> gave:
>> Note that your solution is very similar to the solution in the `foldl`
>> package I just released (also based off of the same blog post you got your
>> solution from).  The key differences are that:
>> * The `foldl` solution is for left folds and uses a strict tuple
>> internally to prevent space leaks
>> * Your solution is for right folds and uses an extra-lazy tuple
>> internally to promote laziness
>> This suggests to me that it would be better to keep this extra-lazy tuple
>> as an internal implementation detail of a right-fold package that would be
>> the lazy analogy of `foldl`, rather than modifying the standard Haskell
>> tuple.
>>  Yes, this is how I encountered the problem. If I have time I'll make a
>> mirror package `foldr` based on extra-lazy tuples. (Or perhaps we could
>> merge the ideas into a single package.)
>>   Best regards,
>>   Petr
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list