[Haskell-cafe] Unnecessarily strict implementations

Jan Christiansen jac at informatik.uni-kiel.de
Wed Sep 1 18:05:03 EDT 2010


there is a new ticket that Data.List.intersperse is not as non-strict  
as possible (http://hackage.haskell.org/trac/ghc/ticket/4282). 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.

Furthermore intersect is too strict. We have intersect _|_ [] = _|_  
and the current implementation is linear in the size of xs if we  
evaluate intersect xs []. I think simply adding a rule intersect _ []  
= [] to the current implementation solves this issue.

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. 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  
Chitil (http://www.cs.kent.ac.uk/people/staff/oc/Talks/ifl2006NonStrictProgramming.pdf 

Cheers, Jan

More information about the Haskell-Cafe mailing list