[Haskell-cafe] How to make code least strict?
Robin Green
--
Robin
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
ChrisK
> 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
> 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:
http://www.haskell.org/haskellwiki/Maintaining_laziness
Robin Green
"Thomas DuBuisson" <thomas.d...@gmail.com> wrote:
> On Mon, Jan 19, 2009 at 4:48 PM, Robin Green <gre...@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:
>
> http://www.haskell.org/haskellwiki/Maintaining_laziness
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
Ryan Ingram
> 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/
Conal Elliott
(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
Ryan Ingram
> zip xs ys = foldr unamb undefined [p1 xs ys, p2 xs ys, p3 xs ys] where
> p1 [] _ = []
> p2 _ [] = []
> p3 (x:xs) (y:ys) = (x,y) : zip xs ys
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
Conal Elliott
I think lub [4] is sufficient typeclass hackery for unambPatterns:
unambPatterns == lubs == foldr lub undefined
[4] http://conal.net/blog/posts/merging-partial-values
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.
I tried out this idea, and it seems to work out very nicely. See the
brand-new blog post
http://conal.net/blog/posts/lazier-function-definitions-by-merging-partial-values/.
Blog comments, please!
- Conal
Thomas Davie
you might want to look at Olaf Chitil's paper here:
http://www.cs.kent.ac.uk/pubs/2006/2477/index.html
It outlines a tool for checking if your programs are as non-strict as
they can be.
Bob
On 21 Jan 2009, at 02:08, Conal Elliott wrote:
> Lovely reformulation, Ryan!
>
> I think lub [4] is sufficient typeclass hackery for unambPatterns:
>
> unambPatterns == lubs == foldr lub undefined
>
> [4] http://conal.net/blog/posts/merging-partial-values
>
> 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.
>
> I tried out this idea, and it seems to work out very nicely. See
> the brand-new blog post http://conal.net/blog/posts/lazier-function-definitions-by-merging-partial-values/
> . Blog comments, please!
Jan Christiansen
Thomas Davie wrote:
>
> Further to all the playing with unamb to get some very cool behaviors,
> you might want to look at Olaf Chitil's paper here:
>
> http://www.cs.kent.ac.uk/pubs/2006/2477/index.html
>
> 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/.
Jan
--
View this message in context: http://www.nabble.com/How-to-make-code-least-strict--tp21546891p21604665.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.