suggestion: use lazy pattern matching for Monoid instances of tuples

[Edward Kmett]

Yep.I should have reached for the easier examples. :) 

Sent from my iPad

On Aug 19, 2013, at 10:47 AM, Petr Pudlák <petr.mvd at gmail.com> wrote:

> 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> 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> 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/aa1a94bd/attachment.htm>