How to make code least strict?

newer
Pure Haskell implementation of...

older
Cabal.exe is available...

Robin Green

19 Jan 2009 19 Jan '09

11:48 a.m.

What guidelines should one follow to make Haskell code least-strict? -- Robin

Show replies by date

ChrisK

19 Jan 19 Jan

12:10 p.m.

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.

Ryan Ingram

3:27 p.m.

On Mon, Jan 19, 2009 at 9:10 AM, ChrisK 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. 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

5:42 p.m.

I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased (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... [3] http://conal.net/blog/tag/unamb/ - conal On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram wrote:

...

On Mon, Jan 19, 2009 at 9:10 AM, ChrisK 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.

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/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Ryan Ingram

6:01 p.m.

Actually, I see a nice pattern here for unamb + pattern matching:

...

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 On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott wrote:

...

I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased (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... [3] http://conal.net/blog/tag/unamb/

- conal

On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram wrote:

...
On Mon, Jan 19, 2009 at 9:10 AM, ChrisK 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.

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/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Conal Elliott

20 Jan 20 Jan

8:08 p.m.

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-v.... Blog comments, please! - Conal On Mon, Jan 19, 2009 at 3:01 PM, Ryan Ingram wrote:

...

Actually, I see a nice pattern here for unamb + pattern matching:

...
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

On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott wrote:

...
I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased (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...

...
[3] http://conal.net/blog/tag/unamb/

- conal

On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram wrote:

...
On Mon, Jan 19, 2009 at 9:10 AM, ChrisK 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.

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/

...
_______________________________________________

Thomas Davie

21 Jan 21 Jan

3:50 a.m.

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. 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-v... . Blog comments, please!

- Conal

On Mon, Jan 19, 2009 at 3:01 PM, Ryan Ingram wrote: Actually, I see a nice pattern here for unamb + pattern matching:

...
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

...
I second Ryan's recommendation of using unamb [1,2,3] to give you unbiased (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... [3] http://conal.net/blog/tag/unamb/

- conal

On Mon, Jan 19, 2009 at 12:27 PM, Ryan Ingram wrote:

...
On Mon, Jan 19, 2009 at 9:10 AM, ChrisK
...
wrote:

...
Consider that the order of pattern matching can matter as well,

On Mon, Jan 19, 2009 at 2:42 PM, Conal Elliott wrote: 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/ _______________________________________________

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Jan Christiansen

22 Jan 22 Jan

9 a.m.

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.htm... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Thomas DuBuisson

19 Jan 19 Jan

12:36 p.m.

On Mon, Jan 19, 2009 at 4:48 PM, Robin Green 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

Robin Green

1:49 p.m.

On Mon, 19 Jan 2009 17:36:30 +0000 "Thomas DuBuisson" wrote:

...

On Mon, Jan 19, 2009 at 4:48 PM, Robin Green 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

5964

Age (days ago)

5967

Last active (days ago)

List overview

Download

9 comments

7 participants

participants (7)

ChrisK
Conal Elliott
Jan Christiansen
Robin Green
Ryan Ingram
Thomas Davie
Thomas DuBuisson

How to make code least strict?

tags

participants (7)