Hi!<br><br>I have a basic knowledge about Haskell and I am trying to put this knowledge to work with a few exercises. The one I am trying now is basically the following.<br><br>1. I must read from the standard input a series of text lines. Each line represents a command that must be performed. The possible commands are:<br>
add <id> <first-name> <last-name> <birth-date> <phone-number><br>del <id><br>info <id><br>query (key:value)+<br><br>2. Each command may or may not generate an output on the standard output according to a series of conditions (if an entry with the same ID already exists, if the id of a del does not exists, if the id of an info does not exists). Also, the info and query command also generate output on the normal working.<br>
<br>3. The program is working, I suppose, but when I submit it for testing and ranking on <a href="http://spoj.pl">spoj.pl</a> I get a timeout. The maximum allowed time for this problem is 6s.<br><br>My code is the following:<br>
<br>===== Begin of source code =====<br><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">-- Problem id: HASHADQI</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">import qualified Data.List as List</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">import qualified Data.IntMap as Map</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">import Data.Maybe</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">type Person = (String,String,String,String)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">type IntPersonMap = Map.IntMap Person</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">main = do</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> input <- getContents</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> seqAction Map.empty $ lines input</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> </span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">seqAction :: IntPersonMap -> [String] -> IO IntPersonMap</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">seqAction m [] = return m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">seqAction m (l:ls) = do</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> m' <- doAction m l</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> seqAction m' ls</span><br style="font-family:courier new,monospace">
<br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doAction :: IntPersonMap -> String -> IO IntPersonMap</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doAction m cmd = do</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> case cmd of</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> 'a':cs -> doInsert m (words cmd)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> 'd':cs -> doDelete m (words cmd)</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> 'i':cs -> doInfo m (words cmd)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> 'q':cs -> doQuery m (words cmd)</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> [] -> return m</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> </span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doInsert :: IntPersonMap -> [String] -> IO IntPersonMap</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">doInsert m [_, idText, fn, ln, bd, pn] = do</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> let id = read idText :: Int</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> if Map.member id m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> then do putStrLn $ "ID " ++ show id ++ " ja cadastrado."</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> return m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> else return (Map.insert id (fn, ln, bd, pn) m)</span><br style="font-family:courier new,monospace">
<br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doDelete :: IntPersonMap -> [String] -> IO IntPersonMap</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doDelete m [_, idText] = do</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> let id = read idText :: Int</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> if Map.member id m</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> then return (Map.delete id m)</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> else do putStrLn $ "ID " ++ show id ++ " nao existente."</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> return m</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doInfo :: IntPersonMap -> [String] -> IO IntPersonMap</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">doInfo m [_, idText] = do</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> let id = read idText :: Int</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> case Map.lookup id m of</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> Just (fn, ln, bd, pn) -> do putStrLn $ unwords [fn, ln, bd, pn]</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> return m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> Nothing -> do putStrLn $ "ID " ++ show id ++ " nao existente."</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> return m</span><br style="font-family:courier new,monospace"><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">doQuery :: IntPersonMap -> [String] -> IO IntPersonMap</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">doQuery m (_:qs) = do</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> let test = (\x -> foldl (&&) True $ map ($x) $ makePredicate qs)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> result = Map.filter test m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> putStrLn $ unwords . map show $ Map.keys result</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> return m</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> </span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">makePredicate :: [String] -> [(Person -> Bool)]</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace">makePredicate [] = []</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace">makePredicate (q:qs) = </span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> case List.break (==':') q of</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> ("fn", ':':x) -> (\(fn,_,_,_) -> fn == x) : (makePredicate qs)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> ("ln", ':':x) -> (\(_,ln,_,_) -> ln == x) : (makePredicate qs)</span><br style="font-family:courier new,monospace"><span style="font-family:courier new,monospace"> ("bd", ':':x) -> (\(_,_,bd,_) -> bd == x) : (makePredicate qs)</span><br style="font-family:courier new,monospace">
<span style="font-family:courier new,monospace"> ("pn", ':':x) -> (\(_,_,_,pn) -> pn == x) : (makePredicate qs)</span><br><br>===== End of source code =====<br clear="all"><br>Can any one explain where is the source(s) of inefficiency and suggest how to make this program more efficient?<br>
<br>Thanks in advance,<br>Jeff.<br><br><br>