What guidelines should one follow to make Haskell code least-strict? -- Robin _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Robin Green wrote: > What guidelines should one follow to make Haskell code least-strict?
Obviously the use of "seq" and bang-patterns make code more strict.
Code is strict when it evaluates values to determine a pattern match. So avoiding that makes code lazier. Values are evaluated when decisions have to be make in order to choose what an expression will evaluate to. Avoiding "case" statements and things that de-sugar to case statements such as "if then else" and pattern matching. Put off examining the input values. Occasionally the use of "lazy" patterns, preceded by ~, can help make code both more compact and less strict.
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
The order of the first two lines of zip's definition affects whether zip [] (error "boom") or zip (error "bam") [] will be an error. This shows that "least-strict" is not a unique goal.
For the choice I just made the "zip [] (error "boom")" will cause an error because the first definition line of zip checks the second argument, while "zip (error "bam") []" will evaluate to [].
The other way to reduce strictness is to be more polymorphic because this reduces what can be sensibly done with the arguments.
"Thomas DuBuisson" <thomas.dubuis...@gmail.com> wrote: > On Mon, Jan 19, 2009 at 4:48 PM, Robin Green <gree...@greenrd.org> > wrote: > > What guidelines should one follow to make Haskell code least-strict?
> There was a great Cafe discussion started by Henning on just this. He > provided this link:
Thanks - wow, my memory is terrible! I submitted this page to the Haskell reddit myself 20 days ago! I had a sneaking feeling of deja vu after I asked the question. :-D -- Robin _______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <hask...@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.
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.
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)
On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram <ryani.s...@gmail.com> wrote: > On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <hask...@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.
> 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.
On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott <co...@conal.net> wrote: > I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased > (symmetric) laziness.
> 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)
> On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram <ryani.s...@gmail.com> wrote:
>> On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <hask...@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.
>> 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.
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.
> 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 <co...@conal.net> wrote: > > I second Ryan's recommendation of using unamb [1,2,3] to give you > unbiased > > (symmetric) laziness.
> > 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)
> > On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram <ryani.s...@gmail.com> > wrote:
> >> On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <hask...@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.
> >> 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.
> 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.
> 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 <co...@conal.net> > wrote: > > I second Ryan's recommendation of using unamb [1,2,3] to give you > unbiased > > (symmetric) laziness.
> > 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)
> > On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram > <ryani.s...@gmail.com> wrote:
> >> On Mon, Jan 19, 2009 at 9:10 AM, ChrisK <hask...@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.
> >> 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.
> It outlines a tool for checking if your programs are as non-strict as > they can be.
We have discussed StrictCheck on the thread "Maintaining Laziness" which also covered the topic least strictness but wasn't as popular as this one.
I have put up a page with functions from Data.List which are not least strict. I want to extend this with other examples from standard libraries. The page can be found at http://www.informatik.uni-kiel.de/~jac/strictcheck/.
