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.

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