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- module CmpStr where
- import Data.Function
- import Data.Monoid
- cmpStr :: String -> String -> Ordering
cmpStr = (compare `on` length) `mappend` compare- cmpStr = (compare `on` map (const ())) `mappend` compare
module CmpStr.Test where import CmpStr import Test.Hspec import Test.QuickCheck main = hspec $ do describe "test for cmpstr" $ do it "test cmpstr" $ do cmpStr "abc" "defz" `shouldBe` LT cmpStr "abcd" "def" `shouldBe` GT cmpStr "abc" "abc" `shouldBe` EQ cmpStr "abc" "def" `shouldBe` LT cmpStr "zzz" (repeat 'a') `shouldBe` LT- module CmpStr.Test where
- import CmpStr
- import Test.Hspec
- import Test.QuickCheck
- main = hspec $ do
- describe "test for cmpstr" $ do
- it "test cmpstr" $ do
- cmpStr "abc" "defz" `shouldBe` LT
- cmpStr "abcd" "def" `shouldBe` GT
- cmpStr "abc" "abc" `shouldBe` EQ
- cmpStr "abc" "def" `shouldBe` LT
- cmpStr "zzz" (repeat 'a') `shouldBe` LT