From: http://www.haskell.org/haskellwiki/Blow_your_mind#Polynomials -- splitting in two (alternating) -- "1234567" -> ("1357", "246") -- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists foldr (\a ~(x,y) -> (a:y,x)) ([],[]) This works but can't find (~) operator anywhere. Please explain or site a reference. Michael
michael rice wrote:
From: http://www.haskell.org/haskellwiki/Blow_your_mind#Polynomials
-- splitting in two (alternating) -- "1234567" -> ("1357", "246") -- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists foldr (\a ~(x,y) -> (a:y,x)) ([],[])
This works but can't find (~) operator anywhere. Please explain or site a reference.
This is called a "lazy pattern". See: http://www.haskell.org/tutorial/patterns.html section 4.4 Cheers, Jochem -- Jochem Berndsen | jochem@functor.nl | jochem@牛在田里.com
On Nov 30, 2009, at 12:47 , michael rice wrote:
From: http://www.haskell.org/haskellwiki/Blow_your_mind#Polynomials
-- splitting in two (alternating) -- "1234567" -> ("1357", "246") -- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists foldr (\a ~(x,y) -> (a:y,x)) ([],[])
This works but can't find (~) operator anywhere. Please explain or site a reference.
http://haskell.org/onlinereport/exps.html#pattern-matching --- see the last alternative for "apat", and rule #2 of section 3.17.2. Basically it changes a (normally strict) pattern into a lazy pattern. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
So, ALL patterns are strict, unless one precedes them with "~"? Michael --- On Mon, 11/30/09, Brandon S. Allbery KF8NH <allbery@ece.cmu.edu> wrote: From: Brandon S. Allbery KF8NH <allbery@ece.cmu.edu> Subject: Re: [Haskell-cafe] Mystery operator? To: "michael rice" <nowgate@yahoo.com> Cc: "Brandon S. Allbery KF8NH" <allbery@ece.cmu.edu>, haskell-cafe@haskell.org Date: Monday, November 30, 2009, 1:10 PM On Nov 30, 2009, at 12:47 , michael rice wrote: From: http://www.haskell.org/haskellwiki/Blow_your_mind#Polynomials -- splitting in two (alternating) -- "1234567" -> ("1357", "246") -- the lazy match with ~ is necessary for efficiency, especially enabling processing of infinite lists foldr (\a ~(x,y) -> (a:y,x)) ([],[]) This works but can't find (~) operator anywhere. Please explain or site a reference. http://haskell.org/onlinereport/exps.html#pattern-matching --- see the last alternative for "apat", and rule #2 of section 3.17.2. Basically it changes a (normally strict) pattern into a lazy pattern. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.comsystem administrator [openafs,heimdal,too many hats] allbery@ece.cmu.eduelectrical and computer engineering, carnegie mellon university KF8NH
On Nov 30, 2009, at 13:26 , michael rice wrote:
So, ALL patterns are strict, unless one precedes them with "~"?
"case" patterns are strict (this includes pattern matching in function arguments). "let" patterns are lazy. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
Am Montag 30 November 2009 19:32:01 schrieb Brandon S. Allbery KF8NH:
On Nov 30, 2009, at 13:26 , michael rice wrote:
So, ALL patterns are strict, unless one precedes them with "~"?
"case" patterns are strict (this includes pattern matching in function arguments). "let" patterns are lazy.
And of course, wildcard patterns (_) and variable patterns (var) are lazy too.
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. Thanks, Michael --- On Mon, 11/30/09, Daniel Fischer <daniel.is.fischer@web.de> wrote: From: Daniel Fischer <daniel.is.fischer@web.de> Subject: Re: [Haskell-cafe] Mystery operator? To: haskell-cafe@haskell.org Date: Monday, November 30, 2009, 1:35 PM Am Montag 30 November 2009 19:32:01 schrieb Brandon S. Allbery KF8NH:
On Nov 30, 2009, at 13:26 , michael rice wrote:
So, ALL patterns are strict, unless one precedes them with "~"?
"case" patterns are strict (this includes pattern matching in function arguments). "let" patterns are lazy.
And of course, wildcard patterns (_) and variable patterns (var) are lazy too. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Mon, Nov 30, 2009 at 2:01 PM, michael rice <nowgate@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@zednenem.com> <http://www.eyrie.org/~zednenem/>
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@zednenem.com> wrote:
On Mon, Nov 30, 2009 at 2:01 PM, michael rice <nowgate@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@zednenem.com> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Am Montag 30 November 2009 20:01:04 schrieb michael rice:
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
For the type (Int,Int) -> Int, the two definitions wouldn't expose different behaviour (okay, faced with add2 undefined, one would raise the Prelude.undefined exception while pattern-matching undefined to (x,y), the other a few nanoseconds later when trying to extract to bona fide Ints from undefined for the addition). For other types, it can make a difference: ----------------------------------- module TestLazyPat where add2' :: Num a => (a,a) -> a add2' (x,y) = x+y add2 :: Num a => (a,a) -> a add2 ~(x,y) = x+y data StupidNum = S deriving (Eq, Ord, Show) instance Num StupidNum where _ + _ = S _ - _ = S _ * _ = S signum _ = S abs _ = S negate _ = S fromInteger _ = S --------------------------------- *TestLazyPat> add2 undefined :: StupidNum S *TestLazyPat> add2' undefined :: StupidNum *** Exception: Prelude.undefined *TestLazyPat> add2' (undefined,undefined) :: StupidNum S That's not a very useful example, though.
I guess what I'm looking for is the concept that would dictate choosing one over the other.
One thing may be "would you like your function to be able to cope with undefined?". More common is the usecase of the example from your first post, foldr (\a (~(x,y)) -> (a:y,x)) ([],[]) xs With a strict tuple-pattern, the system can't know whether the computation produces a pair or bottom, so it can't actually start building the answer before the whole list has been traversed to make sure that yes, indeed, we have a tuple. And if the list is infinite, the second argument to the folded function is indeed not a tuple but bottom. When you tell the compiler to just assume it will receive a pair here, it can start assembling right away (and thus making the assumption come true). When *you* know something will have a certain structure, but the compiler can't know it (for it might be bottom), use a lazy pattern to get things underway.
Thanks,
Michael
participants (6)
-
Brandon S. Allbery KF8NH -
Daniel Fischer -
David Menendez -
Jochem Berndsen -
michael rice -
Ryan Ingram