Stemming with Haskell

Last week we worked on building a small search engine with Haskell. As you might know, when searching you’ll need some index you’ll search and possibly stemming to allow people to search for variants of a word and still come up with accurate results.

Fortunately for us, there are already good libraries and tools out there to help us. So instead of trying to write everything from scratch, we made a small library based on Snowball’s libstemmer_c and a very (very!) rough start of a Sphinx client (more about that in a later post).

We’ve released the library on Hackage so check out stemmer 0.1

A small code example to give you a taste…

module Main where
 
import qualified NLP.Stemmer as Stemming
import Control.Monad (unless)
import System.IO (hSetBuffering, stdout, BufferMode(NoBuffering))
 
main :: IO ()
main = do
    stemmer <- Stemming.new Stemming.English
    putStrLn "Enter a sentence to stem, an empty line to stop."
    hSetBuffering stdout NoBuffering -- to print a prompt
    stemUserInput stemmer
    Stemming.delete stemmer
 
stemUserInput :: Stemming.Stemmer -> IO ()
stemUserInput stemmer = do
    putStr "> "
    string <- getLine
    unless (string == "") $ do 
        string' <- mapM (Stemming.stem stemmer) $ words string
        putStrLn $ "< " ++ unwords string'
        stemUserInput stemmer

Save this to Main.hs and then do something like
$ ghc --make Main.hs -o stemmer [1 of 1] Compiling Main ( Main.hs, Main.o ) Linking stemmer … $ ./stemmer Enter a sentence to stem, an empty line to stop. > The fishes worked forever with their fins < The fish work forev with their fin > Stemming with Haskell < Stem with Haskel

It was pretty easy to implement this library and also a nice exercise in using Haskell’s Foreign Function Interface.

About this entry

You’re currently reading “Stemming with Haskell,” an entry on Tupil Code Blog

Published:: Monday, July 14th, 2008 at 16:55

Author:: Eelco Lempsink

Category:: Code

Tags:: Haskell, library, Snowball, stemmer

data Language = English | Dutch | Piraha | ... deriving (Eq, Ord) stem :: Language -> String -> String stem lang word = unsafePerformIO $ Stemming.stem stemmer word where stemmer = unsafePerformIO $ do cache <- readIORef stemmerCache case Map.lookup lang cache of Just s -> s Nothing -> do s <- Stemming.new lang writeIORef (Map.insert lang s cache) return s stemmerCache :: IORef (M.Map Language Stemming.Stemmer) stemmerCache = -- insert dirty top-level unsafePerformIO here

Eric Kow

July 15th, 2008
12:45 CEST

Thanks for doing this! I’m pleased to see the Natural Language Processing language section on hackage grow. I also like your pragmatic approach of just wrapping around a perfectly good library to get the job done asap. I’m eager for Haskell to be seen as a viable platform for doing NLP, especially by the “I just want to cobble together a bunch of Perl scripts” crowd.

Duane Johnson

July 16th, 2008
17:08 CEST

Maybe the link is just invisible to me, but where is the “last week” article regarding building a search engine (without stemming)? Thanks!

Eelco Lempsink

July 16th, 2008
19:19 CEST

Hi Duane, we will blog about it soon(ish), but we also released a library and demo-app / cli to use Sphinx as a search backend. The library only deals with the searching part, for installing Sphinx, building indexes and running the search daemon you’ll have to consult their docs.

Reinier Lamers

July 18th, 2008
11:06 CEST

It looks like you’ve done little to hide the object-oriented interface. Is that a destructor that I see there? :)

Have you thought about making the API more Haskelllike? Perhaps you could create and destroy Stemmer objects behind the scenes in global variables (unsafePerformIO FTW).

July 18th, 2008
11:53 CEST

Reinier, you’re absolutely right. That’s definitely something that’s planned for the next release ;) It will probably look something like:

withStemmer stemmerAlgorithm action = do
  stemmer <- new stemmerAlgorithm
  result <- action stemmer
  delete stemmer
  return result

What do you think?

July 18th, 2008
14:18 CEST

That’s much better :)

I was thinking of an API like this myself:

data Language = English | Dutch | Piraha | ... deriving (Eq, Ord)


stem :: Language -> String -> String

stem lang word = unsafePerformIO $ Stemming.stem stemmer word

    where stemmer = unsafePerformIO $ do

                                    cache  s

                                        Nothing -> do

                                            s <- Stemming.new lang

                                            writeIORef (Map.insert lang s cache)

                                            return s

stemmerCache :: IORef (M.Map Language Stemming.Stemmer) stemmerCache = -- insert dirty top-level unsafePerformIO here

This gives you a nice functional API at the price of making the implementation unsafe*-ridden. What do you think about such a thing?

July 18th, 2008
14:22 CEST

The blog needs a preview feature… I hope the code is rendered readably this time.

data Language = English | Dutch | Piraha | ...
                            deriving (Eq, Ord)
 
stem :: Language -&gt; String -&gt; String
stem lang word = unsafePerformIO $ Stemming.stem stemmer word
    where stemmer = unsafePerformIO $ do
                                    cache &lt;- readIORef stemmerCache
                                    case Map.lookup lang cache of
                                        Just s -&gt; s
                                        Nothing -&gt; do
                                            s &lt;- Stemming.new lang
                                            writeIORef (Map.insert lang s cache)
                                            return s 
 
stemmerCache :: IORef (M.Map Language Stemming.Stemmer)
stemmerCache = -- insert dirty top-level unsafePerformIO here

July 18th, 2008
20:25 CEST

Two things come to mind: I don’t really like unsafePerformIO, especially not as ‘default’. Also, at what point (in your code) do you delete the reference (to free the memory)? Using a cache implies having the user to do the deletion still by hand.

That said, I’m not a seasoned library developer, so I’m not sure if unsafePerformIO might be fine in these cases. From the documentation: “If the I/O computation wrapped in unsafePerformIO performs side effects, then the relative order in which those side effects take place (relative to the main I/O trunk, or other calls to unsafePerformIO) is indeterminate.” If I understand that correctly it might be that deleting the pointer could happen before a stemmer has been assigned. Since the ‘delete’ function will not fail when passed a nullPtr, this probably should work fine, except the occasional lack of freeing the memory. It’s probably possible to implement it in a way that’s still perfectly safe, I’ll investigate it a bit ;)

July 18th, 2008
21:57 CEST

You don’t delete, you just make sure you never create a second stemmer for the same language. So you never create more stemmers than there are languages and you hopefully never run out of memory.

If your memory were so precious that that would be a problem, you’d not be writing your app in Haskell anyway.

I’m pretty comfortable with using unsafePerformIO in a library (but I’m no more seasoned in Haskell than you of course!). You have something that is essentially a pure computation (namely a stemming algorithm) and it should be exposed as such to Haskell application writers.

Using unsafePerformIO in a pure Haskell application usually means that the author made a design mistake, but when you’re talking to C it is OK with me to write wrapper code that deals with the statefulness of the underlying C API, and then run the wrapper code inside unsafePerformIO.

That doesn’t mean you shouldn’t be very cautious when using unsafePerformIO. Looking at my example code, and what you say about the dangers of unsafePerformIO, I see that I should probably have one unsafePerformIO call in the “stem” function, because now it might call “Stemming.stem ” too early.

July 18th, 2008
22:12 CEST

It took me a couple of attempts and a number of segfaults (brrr), but now I’ve solved in a way I (and hopefully you) am happy with it. Thank you very much for your feedback!

I’ll release it, together with a new blogpost tomorrow. (Don’t have time now, it’s a friday night and I’m on vacation ;)

To give you a preview, I’ve removed ‘unsafeStem’, moved the low-level stuff to a new module (NLP.Stemmer.C) and added (to the exported functions)

withStemmer :: Algorithm -> (Stemmer -> IO a) -> IO a
stem :: Algorithm -> String -> String
stemWords :: Algorithm -> [String] -> [String]

July 19th, 2008
0:11 CEST

Haskelling on a vacation… watch out for becoming the first person diagnosed with Haskell addiction.

That API looks great! But I think you should ask dons for an authoritative opinion :-)

Tupil Code Blog » Blog Archive » Stemming with Haskell reloaded

July 19th, 2008
16:46 CEST

[...] to the nice discussion with Reinier Lamers of the previous post, I’ve updated and released the stemmer library with a more Haskell-like interface. As a point [...]

Tupil Code Blog

Stemming with Haskell

About this entry

12 Comments

Have your say

About

Recently

Tags