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