Re: [Haskell-cafe] Re: How to make code least strict?

Further to all the playing with unamb to get some very cool behaviors, you might want to look at Olaf Chitil's paper here: http://www.cs.kent.ac.uk/pubs/2006/2477/index.html It outlines a tool for checking if your programs are as non-strict as they can be. Bob On 21 Jan 2009, at 02:08, Conal Elliott wrote:

Lovely reformulation, Ryan!

I think lub [4] is sufficient typeclass hackery for unambPatterns:

unambPatterns == lubs == foldr lub undefined

[4] http://conal.net/blog/posts/merging-partial-values

I think performance is okay now, if you have very recent versions of unamb *and* GHC head (containing some concurrency bug fixes). See http://haskell.org/haskellwiki/Unamb . The GHC fix will take a while to get into common use.

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.

I tried out this idea, and it seems to work out very nicely. See the brand-new blog post http://conal.net/blog/posts/lazier-function-definitions-by-merging-partial-v... . Blog comments, please!

- Conal

On Mon, Jan 19, 2009 at 3:01 PM, Ryan Ingram wrote: Actually, I see a nice pattern here for unamb + pattern matching:

...

zip xs ys = foldr unamb undefined [p1 xs ys, p2 xs ys, p3 xs ys] where p1 [] _ = [] p2 _ [] = [] p3 (x:xs) (y:ys) = (x,y) : zip xs ys

Basically, split each pattern out into a separate function (which by definition is _|_ if there is no match), then use unamb to combine them.

The invariant you need to maintain is that potentially overlapping pattern matches (p1 and p2, here) must return the same result.

With a little typeclass hackery you could turn this into

...

zip = unambPatterns [p1,p2,p3] where {- p1, p2, p3 as above -}

Sadly, I believe the performance of "parallel-or"-style operations is pretty hideous right now. Conal?

-- ryan

...

I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased (symmetric) laziness.

The zip definition could also be written as

zip xs@(x:xs') ys@(y:ys') = assuming (xs == []) [] `unamb` assuming (ys == []) [] `unamb` (x,y) : zip xs' ys'

The 'assuming' function yields a value if a condition is true and otherwise is bottom:

assuming :: Bool -> a -> a assuming True a = a assuming False _ = undefined

This zip definition is a special case of the annihilator pattern, so

zip = parAnnihilator (\ (x:xs') (y:ys') -> (x,y) : zip xs' ys') []

where 'parAnnihilator' is defined in Data.Unamb (along with other goodies) as follows:

parAnnihilator :: Eq a => (a -> a -> a) -> a -> (a -> a -> a) parAnnihilator op ann x y = assuming (x == ann) ann `unamb` assuming (y == ann) ann `unamb` (x `op` y)

[1] http://haskell.org/haskellwiki/Unamb [2] http://hackage.haskell.org/packages/archive/unamb/latest/doc/html/Data-Unamb... [3] http://conal.net/blog/tag/unamb/

- conal

On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram wrote:

...

On Mon, Jan 19, 2009 at 9:10 AM, ChrisK

...

wrote:

...

Consider that the order of pattern matching can matter as well,

On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott wrote: the

...

...

...

simplest common case being zip:

zip xs [] = [] zip [] ys = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys

If you are obsessive about least-strictness and performance isn't a giant concern, this seems like a perfect use for Conal's unamb[1] operator.

zipR xs [] = [] zipR [] ys = [] zipR (x:xs) (y:ys) = (x,y) : zip xs ys

zipL [] ys = [] zipL xs [] = [] zipL (x:xs) (y:ys) = (x,y) : zip xs ys

zip xs ys = unamb (zipL xs ys) (zipR xs ys)

This runs both zipL and zipR in parallel until one of them gives a result; if neither of them is _|_ they are guaranteed to be identical, so we can "unambiguously choose" whichever one gives a result first.

-- ryan

[1] http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice/ _______________________________________________

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe