[Haskell-beginners] Testing a data structure, etc
matthew coolbeth
mac01021 at engr.uconn.edu
Sat Jun 19 09:17:02 EDT 2010
As an excercise, I have created a small module defining a data structure
which is intended to be an efficient map from sequences (possibly very long
ones) to objects of some other type. The source code is below for anyone
interested.
Three questions. Hopefully they aren't too naive:
1) Can anyone point me toward whatever standard modules would be most
appropriate for timing this (or measuring other kinds of performance)
against the naive Data.Map?
2) Any suggestions on how to improve the module itself are more than
welcome.
3) In a language like this with meaningful white-space, how do people keep
their lines of source code from getting too wide? There is one line below
that stretched beyond the desired 80 characters and, in general, I seem to
have a hard time avoiding this.
Thanks for your help.
--
mac
-- A map from [a] to p
module SequenceMap (SequenceMap, empty, insert, lookup, test) where
import Prelude hiding (lookup)
import qualified Data.Map
import Data.Maybe
data Ord a => SequenceMap a p =
SequenceMap (Maybe p) (Data.Map.Map a (SequenceMap a p))
empty :: Ord a => SequenceMap a p
empty = SequenceMap Nothing Data.Map.empty
lookup :: Ord a => [a] -> SequenceMap a p -> Maybe p
lookup [] (SequenceMap p m) = p
lookup (a:as) (SequenceMap p m) =
let msm = Data.Map.lookup a m in
case msm of
Nothing -> Nothing
Just sm -> lookup as sm
insert :: Ord a => [a] -> p -> SequenceMap a p -> SequenceMap a p
insert [] p (SequenceMap oldP othrs) = SequenceMap (Just p) othrs
insert (a:as) p (SequenceMap notP othrs) =
let msm = Data.Map.lookup a othrs in
case msm of
Nothing -> SequenceMap notP (Data.Map.insert a (insert as p empty)
Data.Map.empty)
Just sm -> SequenceMap notP (Data.Map.insert a (insert as p sm) othrs)
test :: Bool
test = fromMaybe False (lookup "qwerty" (insert "qwerty" True empty))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100619/048f1757/attachment.html
More information about the Beginners
mailing list