[Haskell-cafe] Re: Optimizing spelling correction program

[Daniel Fischer]

Am Montag 22 Juni 2009 21:31:50 schrieb Kamil Dworakowski:
> On Jun 22, 6:46 am, Bulat Ziganshin <bulat.zigans... at gmail.com> wrote:
> > Hello Kamil,
> >
> > Monday, June 22, 2009, 12:01:40 AM, you wrote:
> > > Right... Python uses hashtables while here I have a tree with log n
> >
> > you can try this pure hashtable approach:
> >
> > import Prelude hiding (lookup)
> > import qualified Data.HashTable
> > import Data.Array
> > import qualified Data.List as List
> >
> > data HT a b = HT (a->Int) (Array Int [(a,b)])
> >
> > -- size is the size of array (we implent closed hash)
> > -- hash is the hash function (a->Int)
> > -- list is assoclist of items to put in hash
> > create size hash list = HT hashfunc
> >                            (accumArray (flip (:))
> >                                        []
> >                                        (0, arrsize-1)
> >                                        (map (\(a,b) -> (hashfunc a,b))

Typo: should be

map (\(a,b) -> (hashfunc a, (a,b))


> > list) )
> >
> >   where arrsize     =  head$ filter (>size)$ iterate (\x->3*x+1) 1
> >         hashfunc a  =  hash a `mod` arrsize
> >
> > lookup a (HT hash arr) = List.lookup a (arr!hash a)
> >
> > main = do let assoclist = [("one", 1), ("two", 2), ("three", 3)]
> >               hash = create 10 (fromEnum . Data.HashTable.hashString)
> > assoclist print (lookup "one" hash)
> >           print (lookup "zero" hash)
>
> It does not compile:
>
> No instance for (Num (String, b))
>   arising from the literal `3' at foo.hs:23:61
> Possible fix: add an instance declaration for (Num (String, b))
> In the expression: 3
> In the expression: ("three", 3)
> In the expression: [("one", 1), ("two", 2), ("three", 3)]
>