On Thursday 02 September 2010 00:05:03, Jan Christiansen wrote:
Hi,
there is a new ticket that Data.List.intersperse is not as non-strict as possible (http://hackage.haskell.org/trac/ghc/ticket/4282).
It's not that it's not as non-strict as possible per se. (Sorry, had to :) It's that intersperse's current definition (in GHC at least) can cause a space leak. In this case, making the function less strict can cure it, in other cases, more strictness might be the solution.
I have observed some other functions which are unnecessarily strict and it might be advantageous to change their definitions as well.
I think it is known that the current implementations of inits and tails are too strict. At least I think I have once read a post to haskell-cafe about this topic.
It's been mentioned. I don't see any drawbacks to making them less strict, so I'd support that.
Furthermore intersect is too strict. We have intersect _|_ [] = _|_
On the other hand, we currently have intersect [] _|_ = [] and one of intersect _|_ [] and intersect [] _|_ must give _|_. Which one is a matter of choice.
and the current implementation is linear in the size of xs if we evaluate intersect xs [].
Yes, that's bad.
I think simply adding a rule intersect _ [] = [] to the current implementation solves this issue.
And before that, the rule intersect [] _ = [] if the current behaviour of intersect [] should be retained.
The implication (<=) :: Bool -> Bool -> Bool is too strict as well. We have False <= _|_ = _|_ as well as _|_ <= True = _|_ while one of these cases could yield True.
I'm not convinced either should (nor that they shouldn't).
The problem is that (<=) is defined by means of compare. This effect shows up for all data types with a least element if the default implementation of (<=) by means of compare is used.
Furthermore there are a couple of functions which are too strict but whose minimally strict implementations do not provide benefits. For example, reverse is too strict as has already been observed by Olaf Chitil (http://www.cs.kent.ac.uk/people/staff/oc/Talks/ifl2006NonStrictProgramm ing.pdf ).
The last slide lists among the problems "proposes undesirably inefficient functions (reverse)". I wouldn't equate 'not minimally strict' with 'too strict'. Minimal strictness also can have negative effects, one must look at each case individually.
Cheers, Jan