[Haskell-cafe] Mystery operator?

[Ryan Ingram]

Consider these two functions:

z = ([], [])

alt1 = foldr f z where
    f a (x,y) = (a:y, x)

alt2 = foldr g z where
    g a ~(x,y) = (a:y, x)

alt1 (1:2:3:undefined)
= foldr f z (1:2:3:undefined)
= f 1 (foldr f z (2:3:undefined))
-- Now f 1 needs to evaluate its second argument for the pattern match
= f 1 (f 2 (foldr f z (3:undefined)))
-- ditto for f 2
= f 1 (f 2 (f 3 (foldr f z undefined)))
-- ditto for f 3
= f 1 (f 2 (f 3 undefined))
= undefined

If you replace "undefined" with [], at this point we would start being
able to return results.  But notice how we had to evaluate the entire
list before we can output any data at all.

alt2 (1:2:3:undefined)
= foldr g z (1:2:3:undefined)
= g 1 (foldr g z (2:3:undefined))
-- g is a lazy pattern match for the 2nd argument
= let (x,y) = foldr g z (2:3:undefined)
   in (1:y, x)

Here we've already output a pair and the first element of the output,
before we have even evaluated the tail of the list!  Now if we
continue demanding the output...

= let (x,y) = g 2 (foldr g z (3:undefined))
   in (1:y, x)
= let (x1,y1) = foldr g z (3:undefined)
       (x,y) = (2:y1, x1)
   in (1:y,x)
= let (x1,y1) = foldr g z (3:undefined)
       x = 2:y1
       y = x1
   in (1:y,x)
= let (x1,y1) = foldr g z (3:undefined)
   in (1:x1,2:y1)
= let (x1,y1) = g 3 (foldr g z undefined)
   in (1:x1, 2:y1)
= let (x2,y2) = foldr g z undefined
       (x1,y1) = (3:y2, x2)
   in (1:x1, 2:y1)
= let (x2,y2) = foldr g z undefined
       x1 = 3:y2
       y1 = x2
   in (1:x1, 2:y1)
= let (x2,y2) = foldr g z undefined
   in (1:3:y2, 2:x2)
= let (x2,y2) = undefined
   in (1:3:y2, 2:x2)
= (1:3:undefined, 2:undefined)

The lazy pattern match is allowing us to output as much of the result
as possible; this implementation is "maximally lazy".

As for guidelines:
- Only use lazy pattern matching on single-constructor data types.
Tuples are the prime candidate here.
- Lazy pattern matches involve allocating additional thunks for the
variables, so you are paying a cost.  If you are immediately going to
demand the contents of those variables (like in your 'add' example),
there's no point.

  -- ryan

On Mon, Nov 30, 2009 at 11:29 AM, David Menendez <dave at zednenem.com> wrote:
> On Mon, Nov 30, 2009 at 2:01 PM, michael rice <nowgate at yahoo.com> wrote:
>>
>> Hi all,
>>
>> A lot of things posted here I wasn't aware of. My original example involved ~(x,y), so,
>> returning to that context, how would these two simple cases vary:
>>
>> add2 :: (Int,Int) -> Int
>> add2 (x,y) = x+y
>>
>> add2 :: (Int,Int) -> Int
>> add2 ~(x,y) = x+y
>>
>> I guess what I'm looking for is the concept that would dictate choosing one over the other.
>
> These particular two functions are identical, because (+) is strict for Ints.
>
> But consider these two functions:
>
> swap ~(x,y) = (y,x)
> swap' (x,y) = (y,x)
>
> swap is non-strict, and swap' is strict.
>
> swap _|_ = (_|_, _|_)
> swap' _|_ = _|_
>
>
> --
> Dave Menendez <dave at zednenem.com>
> <http://www.eyrie.org/~zednenem/>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>