[Haskell-cafe] Mystery operator?
Ryan Ingram
ryani.spam at gmail.com
Mon Nov 30 15:07:21 EST 2009
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
>
More information about the Haskell-Cafe
mailing list