[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

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
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.


-- 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)
    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