suggestion: use lazy pattern matching for Monoid instances of tuples

[Petr Pudlák]

Just to be sure that I understand it correctly: If I take foldMap as the 
basis and I run it on a binary tree with First/Last monoids, I get both 
result in O(depth). But if I take foldl or foldr as the basis, either 
searching for the first or for the last element will take O(size), am I 
right?

Dne 08/19/2013 04:14 PM, Edward Kmett napsal(a):
> With foldMap one can have structures that get to explicitly reuse 
> previous intermediate results.
>
> e.g. 
> http://hackage.haskell.org/packages/archive/compressed/3.0.3/doc/html/Data-Compressed-Internal-LZ78.html 
> gives 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 
> Haskell.
>
> -Edward
>
>
> On Mon, Aug 19, 2013 at 9:31 AM, Petr Pudlák <petr.mvd at gmail.com 
> <mailto:petr.mvd at gmail.com>> 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:
>     http://www.haskellforall.com/2013/08/composable-streaming-folds.html
>     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 gmail.com
>>     <mailto:petr.mvd at gmail.com>> 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:
>>>
>>>         http://stackoverflow.com/a/18289075/1026598
>>>
>>>         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: <http://www.haskell.org/pipermail/libraries/attachments/20130819/d4668121/attachment.htm>