Haskell Quiz/Index and Query/Solution Jethr0
From HaskellWiki
< Haskell Quiz | Index and Query(Difference between revisions)
m (added my non-bit-array solution) |
(sharpen cat) |
||
| Line 1: | Line 1: | ||
| - | [[Category: | + | [[Category:Haskell Quiz solutions|Index and Query]] |
Unfortunately this solution doesn't really address the problem :) | Unfortunately this solution doesn't really address the problem :) | ||
Current revision
Unfortunately this solution doesn't really address the problem :)
Neither are bit-arrays used nor is this solution saving much space. I just wanted to experiment with the State Monad, and I'm quite happy with what I learned.
Example:
> let docs = [("Doc1", "The quick brown fox")
,("Doc2", "Jumped over the brown dog")
,("Doc3", "Cut him to the quick")]
> finder docs "brown"
["Doc1","Doc2"]
> finder docs "the"
["Doc2","Doc3"]
Solution:
import qualified Control.Monad.State as State import qualified Data.Map as Map import qualified Data.Set as Set data Rd = Rd {rdN :: Integer ,rdMap :: Map.Map String Integer } deriving (Show) -- process words of a file and return the set of indices processWords :: [String] -> State.State Rd (Set.Set Integer) processWords = foldM step (Set.empty) where step ws x = do mp <- State.gets rdMap i <- case Map.lookup x mp of Nothing -> do n <- State.gets rdN State.modify (\s -> s{rdN=(n+1), rdMap=Map.insert x n (rdMap s)}) return n Just a -> return a return $ Set.insert i ws processFile :: (String,String) -> State.State Rd (String, [Integer]) processFile (doc,str) = do indices <- processWords (words str) return (doc, Set.toList indices) -- find all documents containing string "str" as a word. findDocs :: String -> [(String,[Integer])] -> State.State Rd [String] findDocs str indices = do mp <- State.gets rdMap case Map.lookup str mp of Nothing -> return [] Just i -> return . map fst . filter (\(_,is) -> i `elem` is) $ indices runIt f = State.evalState f (Rd {rdN=0, rdMap=Map.empty}) finder ds str = runIt (mapM processFile ds >>= findDocs str)
