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 &lt;- getContents
    let 
        allLines = lines content
        caseCount = read (head allLines) :: Int
        cases = tail allLines
    putStr $ unlines $ map toYesNo (processCases cases caseCount)

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

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

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

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

checkNumberConsistencyVsNumber :: [Char] -&gt; [Char] -&gt; Bool
checkNumberConsistencyVsNumber number number2 =
    let
        numberLength = length number
        number2Length = length number2
    in if numberLength &gt; 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
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 &lt;- 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 -&gt; [String] -&gt; 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] -&gt; Bool
checkListConsistency [] = True
checkListConsistency (n:ns) = (checkNumberConsistency n ns) &amp;&amp; (checkListConsistency ns)



Suggested solution

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

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

yesNo :: Bool -&gt; String
yesNo True = "YES"
yesNo False = "NO"

processCase :: IO ()
processCase = do
  caseSize &lt;- readLn
  inputs &lt;- replicateM caseSize getLine
  putStrLn $ (yesNo . isConsistentPhoneList) inputs

main :: IO ()
main = do
  caseCount &lt;- readLn
  replicateM_ caseCount processCase