# Phone List challenge

To learn Haskell, I've been going at this challenge, which is to check a list of phone numbers to ensure that no number is a prefix of another. However, my code is way too slow. I am really new to Haskell so I don't know what to look for in performance optimization.

I have generated a sample input which takes 5s (uncompiled via runhaskell) on my machine. What can I do to speed this up?

main = do
content <- getContents
let
allLines = lines content
cases = tail allLines
putStr $unlines$ map toYesNo (processCases cases caseCount)

toYesNo b
| b = "YES"
| otherwise = "NO"

processCases :: [[Char]] -> Int -> [Bool]
processCases [] num = []
processCases cases 0 = []
processCases cases remaining =
let
current = take caseLines (tail cases)
in (if (checkListConsistency current) then True else False)
: (processCases (drop (caseLines+1) cases) (remaining-1))

checkListConsistency :: [[Char]] -> Bool
checkListConsistency [] = True
checkListConsistency list =
let
rest = tail list
in if checkNumberConsistency number rest
then checkListConsistency rest
else False

checkNumberConsistency :: [Char] -> [[Char]] -> Bool
checkNumberConsistency number [] = True
checkNumberConsistency number list =
foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)

checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2 =
let
numberLength = length number
number2Length = length number2
in if numberLength > number2Length
then notStartsWith number number2
else notStartsWith number2 number

notStartsWith _ [] = False
notStartsWith [] _ = True
notStartsWith (hl:tl) (hs:ts)
| hl == hs = notStartsWith tl ts
| otherwise = True

• For me when tested with the given example input, it outputs a single YES and then freezes waiting for input, is that the correct behaviour? May 30, 2015 at 13:10
• It should output a single YES but not wait for input after that. I run it like this on windows: runhaskell phonelist.hs < file May 30, 2015 at 14:22
• the performance problem is soon understood runhaskell will interpret the programme (very slow) running it after compiling is instanteneous (< 0.1 seconds) May 30, 2015 at 14:32
• Yeah I noticed that when I compiled. But the server does compile the code and complains that it's taking too long still. But I give up for now. I think the design is wrong from the start. May 30, 2015 at 14:42
• In terms of performance design; I recommend using a Trie Jun 9, 2015 at 15:59

Inlining very short expressions

It is better to avoid the in dialect when the expression is really short, checkNumberConsistencyVsNumber can be written in a much shorter manner

checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2
| length number > length number2 = notStartsWith number number2
| otherwise = notStartsWith number2 number


Types everywhere

It is very good that your code is mostly typed, I would finish the job giving types to main and toYesNo:

main :: IO()
toYesNo :: Bool -> [Char]


Use built-ins

Built-ins make the code faster, shorter and easier, for example the below line would benefit from all

foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)


Be sure to use -O2

That is to compile with ghc -O2 phone.hs for automatically faster code

## Performance

Your program is slow because you check each number against all subsequent numbers. For a fully consistent phone book with n entries, that's O(n2).

A better strategy would be to sort each phone book first. Then you only need to check consecutive pairs. If one number is a prefix of another, then the prefix will appear just before the longer number. That's O(n log n) for the sorting, plus O(n) for the checking, which is O(n log n) in total.

## Looping

The infrastructure for handling test cases is clumsy.

One problem stems for the fact that you slurp up all the input into one list right away, with content <- getContents followed by allLines = lines content. As a result processCases has to take a list of those lines as input, and parcel them out using drop (caseLines+1) cases. A further complication is that allLines contains non-homogeneous data: the first line specifies the number of test cases, the first line within each test case specifies the size of that test case, and all other lines contain phone numbers. You're basically doing I/O by dissecting the list, and you would be better off doing real I/O.

processCases performs a countdown using its second parameter. It would be better to have a processCase function instead, which is called n times. You can't make that improvement, though, given the way all the input has been slurped up into one list.

## Style

• For readability, maintainability, and performance, declare the types of all functions. You missed toYesNo and main. Instead of [[Char]], use [String], which is easier to understand.
• Avoid function names like checkSomething, which sound more imperative than functional. For example, isListConsistent would be a better name than checkListConsistency.
• Take advantage of standard library functions — use Google and Hoogle. For example, notStartsWith is just ((not.).isPrefixOf).
• Simplify predicate tests on a list. checkNumberConsistency can be

checkNumberConsistency :: String -> [String] -> Bool
checkNumberConsistency n ns = all (checkNumberConsistencyVsNumber n) ns

• Avoid if … then … else. There is usually a better alternative. For example, (if (checkListConsistency current) then True else False) is just checkListConsistency current. Your checkListConsistency function can be simplified:

checkListConsistency :: [String] -> Bool
checkListConsistency [] = True
checkListConsistency (n:ns) = (checkNumberConsistency n ns) && (checkListConsistency ns)


## Suggested solution

import Control.Monad (replicateM, replicateM_)
import Data.List (isPrefixOf, sort)

isConsistentPhoneList :: [String] -> Bool
isConsistentPhoneList numbers = not $any (uncurry isPrefixOf) consecutivePairs where sortedNumbers = sort numbers consecutivePairs = zip sortedNumbers$ tail sortedNumbers

yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"

processCase :: IO ()
processCase = do
inputs <- replicateM caseSize getLine
putStrLn $(yesNo . isConsistentPhoneList) inputs main :: IO () main = do caseCount <- readLn replicateM_ caseCount processCase  • Thanks for your feedback regarding looping and style. I wasn't looking for a solution and I'm not going to use those parts, but they're useful nonetheless for my learning process. Jun 3, 2015 at 13:51 Using the isPrefixOffunction from Data.List The Data.Listpackage has a a function called isPrefixOf, which can be used to build a single isValidPhoneLstfunction, like this: isValidPhoneLst :: [String] -> String isValidPhoneLst [] = "YES" isValidPhoneLst [p] = "YES" isValidPhoneLst (h:t) = case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of True -> "NO" _ -> isValidPhoneLst t  Simplifying your mainfunction with replicateM and mapM_ The replicateM function performs an action n times, gathering the results. It can be used to build a list of only the test cases that you need. As for printing the results, you can use the mapM_ function to print the results of the isValidPhoneLstfunction applied to the test cases, like this: import Control.Monad(replicateM) import Data.List(isPrefixOf) main :: IO () main = do nTestCases <- readLn tests <- replicateM nTestCases$ do
replicateM testCaseSize getLine
mapM_ (putStrLn . isValidPhoneLst) tests

isValidPhoneLst :: [String] -> String
isValidPhoneLst [] = "YES"
isValidPhoneLst [p] = "YES"
isValidPhoneLst (h:t) =
case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of
True -> "NO"
_ -> isValidPhoneLst t


Using the test case you provided, the main program ran in 349 Milliseconds, compiled without any optimizations.

On Kattis

I've made a kattis account and after submitting this solution I also got Time Limit Exceed. I wish they would provide more information to us users, such as websites like Hackerrank do.

• Thanks for your feedback. I will edit my question and explain that it took 5s uncompiled (via runhaskell). It's more like 1s compiled I think. But yeah, the sample input does not reflect Kattis' input. And my brute-force design will always be too slow; see 200_success' answer why that is. Jun 3, 2015 at 13:55