[Haskell-cafe] Unnecessarily strict implementations
daniel.is.fischer at web.de
Wed Sep 1 19:35:18 EDT 2010
On Thursday 02 September 2010 00:05:03, Jan Christiansen wrote:
> 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
> 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
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
> Cheers, Jan
More information about the Haskell-Cafe