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-values/ .  Blog comments, please!

   - Conal

On Mon, Jan 19, 2009 at 3:01 PM, Ryan Ingram <ryani.spam@gmail.com> 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

On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott <conal@conal.net> wrote:
> 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.html
> [3] http://conal.net/blog/tag/unamb/
>
>    - conal
>
> On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram <ryani.spam@gmail.com> wrote:
>>
>> On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <haskell@list.mightyreason.com>
>> wrote:
>> > Consider that the order of pattern matching can matter as well, 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