Data.HashTable bug

[Josef Svenningsson]

On Fri, 19 Mar 2004, Simon Marlow wrote:

> I did post a hash table version of this program a while back, that I
> claimed was a factor of 3 faster at the time.  Unfortunately the
> attachment in the archive is in base64 and I can't read it, and I've
> lost the code :-(  If you can decode the attachment, it's here:
>
> http://www.haskell.org/pipermail/haskell-cafe/2001-July/002061.html
>
Does the code below look familiar?

	/Josef

\begin{code}
-- compile with: ghc -O -package lang
-- run with:     ./a.out +RTS -H10m -K4m <Input.txt

import MArray
import PackedString
import IOExts
import IO
import Char
import Monad

arr_size = 20000

main = do
  h <- openFile "Usr.Dict.Words" ReadMode
  sz <- hFileSize h
  ps <- hGetPS h (fromIntegral sz)

  tbl <- newArray (0,arr_size) []
  mapM (addToHashTable tbl) (linesPS ps)

  h <- openFile "Input.txt" ReadMode
  sz <- hFileSize h
  ps <- hGetPS h (fromIntegral sz)

  let test s = do b <- elemHashTable s tbl
		  when (not b) (putStrLn (unpackPS s))
  mapM test (linesPS ps)

type HashTable = IOArray Int [PackedString]

-- Looks bad, but GHC does a great job of optimising it:
hashPS :: PackedString -> Int
hashPS ps = foldr f 0 (map (ord.indexPS ps) [1..lengthPS ps])
  where f n m = n + m * 128 `mod` 1048583

addToHashTable :: HashTable -> PackedString -> IO ()
addToHashTable tbl s = do
  let h = hashPS s
      index = h `mod` arr_size
  r <- readArray tbl index
  if (s `elem` r) then return () else do
  writeArray tbl index (s : r)

elemHashTable :: PackedString -> HashTable -> IO Bool
elemHashTable s tbl = do
  let h = hashPS s
      index = h `mod` arr_size
  r <- readArray tbl index
  return (s `elem` r)
\end{code}