<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Further to all the playing with unamb to get some very cool behaviors, you might want to look at Olaf Chitil's paper here:</div><div><br></div><div><a href="http://www.cs.kent.ac.uk/pubs/2006/2477/index.html">http://www.cs.kent.ac.uk/pubs/2006/2477/index.html</a></div><div><br></div><div>It outlines a tool for checking if your programs are as non-strict as they can be.</div><div><br></div><div>Bob</div><br><div><div>On 21 Jan 2009, at 02:08, Conal Elliott wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">Lovely reformulation, Ryan!<br><br>I think lub [4] is sufficient typeclass hackery for unambPatterns:<br><br> unambPatterns == lubs == foldr lub undefined<br><br>[4] <a href="http://conal.net/blog/posts/merging-partial-values">http://conal.net/blog/posts/merging-partial-values</a><br> <br>I think performance is okay now, if you have very recent versions of unamb *and* GHC head (containing some concurrency bug fixes). See <a href="http://haskell.org/haskellwiki/Unamb">http://haskell.org/haskellwiki/Unamb</a> . The GHC fix will take a while to get into common use.<br> <br>My definitions of zip via (a) 'assuming' & 'unamb' and (b) parAnnihilator are badly broken. For one, the unamb arguments are incompatible (since i didn't check for both non-null args in the third case). Also, the types aren't right for parAnnihilator.<br> <br>I tried out this idea, and it seems to work out very nicely. See the brand-new blog post <a href="http://conal.net/blog/posts/lazier-function-definitions-by-merging-partial-values/">http://conal.net/blog/posts/lazier-function-definitions-by-merging-partial-values/</a> . Blog comments, please!<br> <br> - Conal<br><br><div class="gmail_quote">On Mon, Jan 19, 2009 at 3:01 PM, Ryan Ingram <span dir="ltr"><<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Actually, I see a nice pattern here for unamb + pattern matching:<br> <br> > zip xs ys = foldr unamb undefined [p1 xs ys, p2 xs ys, p3 xs ys] where<br> > p1 [] _ = []<br> > p2 _ [] = []<br> > p3 (x:xs) (y:ys) = (x,y) : zip xs ys<br> <br> Basically, split each pattern out into a separate function (which by<br> definition is _|_ if there is no match), then use unamb to combine<br> them.<br> <br> The invariant you need to maintain is that potentially overlapping<br> pattern matches (p1 and p2, here) must return the same result.<br> <br> With a little typeclass hackery you could turn this into<br> <br> > zip = unambPatterns [p1,p2,p3] where {- p1, p2, p3 as above -}<br> <br> Sadly, I believe the performance of "parallel-or"-style operations is<br> pretty hideous right now. Conal?<br> <font color="#888888"><br> -- ryan<br> </font><div><div></div><div class="Wj3C7c"><br> On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott <<a href="mailto:conal@conal.net">conal@conal.net</a>> wrote:<br> > I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased<br> > (symmetric) laziness.<br> ><br> > The zip definition could also be written as<br> ><br> > zip xs@(x:xs') ys@(y:ys') =<br> > assuming (xs == []) [] `unamb`<br> > assuming (ys == []) [] `unamb`<br> > (x,y) : zip xs' ys'<br> ><br> > The 'assuming' function yields a value if a condition is true and otherwise<br> > is bottom:<br> ><br> > assuming :: Bool -> a -> a<br> > assuming True a = a<br> > assuming False _ = undefined<br> ><br> > This zip definition is a special case of the annihilator pattern, so<br> ><br> > zip = parAnnihilator (\ (x:xs') (y:ys') -> (x,y) : zip xs' ys') []<br> ><br> > where 'parAnnihilator' is defined in Data.Unamb (along with other goodies)<br> > as follows:<br> ><br> > parAnnihilator :: Eq a => (a -> a -> a) -> a -> (a -> a -> a)<br> > parAnnihilator op ann x y =<br> > assuming (x == ann) ann `unamb`<br> > assuming (y == ann) ann `unamb`<br> > (x `op` y)<br> ><br> > [1] <a href="http://haskell.org/haskellwiki/Unamb" target="_blank">http://haskell.org/haskellwiki/Unamb</a><br> > [2]<br> > <a href="http://hackage.haskell.org/packages/archive/unamb/latest/doc/html/Data-Unamb.html" target="_blank">http://hackage.haskell.org/packages/archive/unamb/latest/doc/html/Data-Unamb.html</a><br> > [3] <a href="http://conal.net/blog/tag/unamb/" target="_blank">http://conal.net/blog/tag/unamb/</a><br> ><br> > - conal<br> ><br> > On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram <<a href="mailto:ryani.spam@gmail.com">ryani.spam@gmail.com</a>> wrote:<br> >><br> >> On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <<a href="mailto:haskell@list.mightyreason.com">haskell@list.mightyreason.com</a>><br> >> wrote:<br> >> > Consider that the order of pattern matching can matter as well, the<br> >> > simplest<br> >> > common case being zip:<br> >> ><br> >> > zip xs [] = []<br> >> > zip [] ys = []<br> >> > zip (x:xs) (y:ys) = (x,y) : zip xs ys<br> >><br> >> If you are obsessive about least-strictness and performance isn't a<br> >> giant concern, this seems like a perfect use for Conal's unamb[1]<br> >> operator.<br> >><br> >> zipR xs [] = []<br> >> zipR [] ys = []<br> >> zipR (x:xs) (y:ys) = (x,y) : zip xs ys<br> >><br> >> zipL [] ys = []<br> >> zipL xs [] = []<br> >> zipL (x:xs) (y:ys) = (x,y) : zip xs ys<br> >><br> >> zip xs ys = unamb (zipL xs ys) (zipR xs ys)<br> >><br> >> This runs both zipL and zipR in parallel until one of them gives a<br> >> result; if neither of them is _|_ they are guaranteed to be identical,<br> >> so we can "unambiguously choose" whichever one gives a result first.<br> >><br> >> -- ryan<br> >><br> >> [1]<br> >> <a href="http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/" target="_blank">http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/</a><br> >> _______________________________________________</div></div></blockquote></div><br> _______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>http://www.haskell.org/mailman/listinfo/haskell-cafe<br></blockquote></div><br></body></html>