Comparing lists using the length function is problematical because it requires counting every item in both lists. However, we only need to count up until the length of the shortest list + 1 to know which one is shorter. This can make a big difference in performance if one list is much longer than the other -- and make the difference between termination and non-termination if one list is infinite.

My change fixes this problem by avoiding the use of the length function. I've also changed the tests to make sure the solution works when one list is infinite.

Code
Diff
  • module CmpStr where
    
    import Data.Function
    import Data.Monoid
    
    cmpStr :: String -> String -> Ordering
    cmpStr = (compare `on` map (const ())) `mappend` compare
  • 11 module CmpStr where
    22
    33 import Data.Function
    44 import Data.Monoid
    55
    66 cmpStr :: String -> String -> Ordering
    7cmpStr = (compare `on` length) `mappend` compare
    7+cmpStr = (compare `on` map (const ())) `mappend` compare