<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">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?<br>
<br>
Dne 08/19/2013 04:14 PM, Edward Kmett napsal(a):<br>
</div>
<blockquote
cite="mid:CAJumaK_ihE6Gvf+VBucEvRSob3tqAaOqE4DtEiWAPwpVtcu2Vw@mail.gmail.com"
type="cite">
<div dir="ltr">With foldMap one can have structures that get to
explicitly reuse previous intermediate results.
<div><br>
</div>
<div>e.g. <a moz-do-not-send="true"
href="http://hackage.haskell.org/packages/archive/compressed/3.0.3/doc/html/Data-Compressed-Internal-LZ78.html">http://hackage.haskell.org/packages/archive/compressed/3.0.3/doc/html/Data-Compressed-Internal-LZ78.html</a>
gives you a list with a more efficient fold by using LZ78 to
identify sharing with earlier parts of the list.
<div>
<br>
</div>
<div>With foldr you can't exploit such regularity as you can
merely append one element at a time.</div>
<div><br>
</div>
<div>Less drastically, with foldMap, you can binary search a
tree structure if the foldMap preserves the original
associativity of the structure.</div>
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>In my current work I'm using "sequence-algebras" and
"sequence-trees" to exploit even more structure than foldMap
gives me. </div>
<div><br>
</div>
<div>I'll probably write up an article at some point soon on
the School of Haskell.</div>
<div><br>
</div>
<div>-Edward</div>
</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Mon, Aug 19, 2013 at 9:31 AM, Petr
Pudlák <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:petr.mvd@gmail.com" target="_blank">petr.mvd@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>This is exactly how I run into the Monoid problem. My
original `foldr` version works fine, but when I saw this
Gabriel's post:<br>
<a moz-do-not-send="true"
href="http://www.haskellforall.com/2013/08/composable-streaming-folds.html"
target="_blank">http://www.haskellforall.com/2013/08/composable-streaming-folds.html</a><br>
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.<br>
<br>
Could you elaborate a bit when/how the asymptotic
difference occurs?<br>
<br>
Best regards,<br>
Petr<br>
<br>
Dne 08/19/2013 02:03 PM, Edward Kmett napsal(a):<br>
</div>
<div>
<div class="h5">
<blockquote type="cite">
<div dir="ltr">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.
<div> <br>
</div>
<div>-Edward</div>
</div>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Mon, Aug 19, 2013 at
3:29 AM, Petr Pudlák <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:petr.mvd@gmail.com"
target="_blank">petr.mvd@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0
0 0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Thank you all for the responses.<br>
<br>
Edward's objection is very serious, I
didn't think of it.<br>
Because of it I retract the proposal, this
would indeed create big problems. (I just
wish someone invents an oracle strictness
analyzer...)<br>
<br>
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?<br>
<br>
Dne 08/18/2013 11:21 PM, Gabriel Gonzalez
napsal(a):<br>
</div>
<div>
<blockquote type="cite">
<div>I'm guessing this proposal is
related to this Stack Overflow answer
you gave:<br>
<br>
<a moz-do-not-send="true"
href="http://stackoverflow.com/a/18289075/1026598"
target="_blank">http://stackoverflow.com/a/18289075/1026598</a><br>
<br>
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:<br>
<br>
* The `foldl` solution is for left
folds and uses a strict tuple
internally to prevent space leaks<br>
* Your solution is for right folds and
uses an extra-lazy tuple internally to
promote laziness<br>
<br>
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.<br>
</div>
</blockquote>
</div>
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.)<br>
<br>
Best regards,<br>
Petr<br>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</blockquote>
<br>
</body>
</html>