[Haskell-cafe] Unnecessarily strict implementations

[Daniel Fischer]

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