- Haskell-Cafe - Haskell.org

Optimizing spelling correction program
by Kamil Dworakowski 25 Jun '09

25 Jun '09

Hi all, I want to learn how to optimize Haskell code on the Norvig's spelling correction program [1]. Peter Norvig has written the program in Python, quite a literate translation to Haskell (thanks to Grzegorz Chrupala) [2] was also available. Both versions are about 23 LOCs, and Haskell version is four times slower, 2m25s versus 36s. All the numbers I give come from running the program on a list of 806 misspellings, Haskell version compiled with - O2 and -fforce-recomp flags. I started with trial and error approach. Just preventing a repetitive call to keysSet brought the running time down to 1m48s. I also restructured the edits1 function and dropped all uses of sets, which haven't been pulling their own weight. This brought the running time down to 55s. Not quite there yet but close. Reading the Profiling chapter in the RWH book enabled me to do some more informed optimizing. At this point the GC time was about 2% of the overall runnig time, Grzegorz has done a good job of using strict versions of functions where necessary. The timing per expression however showed something useful, 70% of the time was being spent around determining membership in the known words dictionary (Data.Map). There are about 30 000 items in the dictionary. Right... Python uses hashtables while here I have a tree with log n access time. I did not want to use the Data.HashTable, it would pervade my program with IO. The alternative is an ideal hashmap that never gets changed. This program creates a dictionary at start which then is only being used to read from: an ideal application for the Data.PerfectHash by Mark Wotton available on Hackage [3]. The PerfectHash is a dictionary keyed by ByteStrings, so I had to migrate the program to use these instead of Strings. Sadly it increased the running time to 59s. Adding PerfectHash brought the running time down to 39s. I have done some code restructuring with the view to publishing it, which brought the running time up to 45s. The code is available on patch-tag [4] for anyone to scrutinize and hopefully point out mistakes (it uses big.txt and misspellings file which are linked to from Norvig's page [1]). At this point [5] I don't know how to proceed. The program is still slower than Python. The -ddump-simpl dump does not give me any clues, there is too much of it and I don't understand most of it. The GC time is about 10% of the total, and according to the profiler almost half the time is spent in the member function, and almost all the rest in edits1. Shouldn't it run much faster than the interpreted Python? Frankly, I am not impressed with the PerfectHash performance; It looks as if it is only two times faster than Data.Map. Is this because of the number of elements? 1. http://www.norvig.com/spell-correct.html 2. http://pitekus.blogspot.com/2007/04/norvigs-spelling-corrector-in-haskell.h… 3. http://hackage.haskell.org/package/PerfectHash 4. http://patch-tag.com/r/spellcorrect/ 5. http://patch-tag.com/r/spellcorrect/snapshot/hash/20090621192727-a99e5-fed4…

8 23

Re: [Haskell-cafe] Suggestion for Network.Socket in regards to PortNumber
by Johan Tibell 24 Jun '09

24 Jun '09

On Mon, Jun 22, 2009 at 7:27 PM, Tim Sheard <sheard(a)cs.pdx.edu> wrote: > My idea is to use types to ensure that any > sequence of operations adheres to a path on > a finite state automata. For example > if we wanted to implement the following > automata (This needs to read in a fixed width font) > Here's the reply Oleg gave me when I asked about using monadic regions to enforce similar constraints (published with Oleg's permission): Oleg writes: > First of all, protocols of using API functions are essentially > session types, right? Thus various implementations of session types > could be taken advantage of (including the one presented by Jesse Tov > on Haskell 2008 Symposium). Aliasing is responsible for a lot of the > complexity: if the variable 's' is bound to a value of the type socket > and we execute "do s' <- bindS s" so to bind the socket, the old > variable s is still available and could be used. But it should not be > used because bindS "consumed" the unbound socket and produced the new > one. To properly describe these resource restrictions (a resource can > be consumed and after that it is not available any more), we need > linear, affine or various other kinds of substructural logics and type > systems. It seems they all can be emulated in Haskell, but with some > hackery (see for example Sec 6 of our monadic regions > paper). Parameterized monads are necessary. > > The lightweight monadic regions paper relied on a simple > session protocol: open -> (read+write)* -> close. That protocol can be > ensured without parameterized monads: the only aliasing to mind is > the accessibility of the file handle after the closing operation. We > can get rid of `close' (make it implicit ar region's exit) and use > rank-2 types to prevent file handles from leaking out. There is some > dynamic overhead, in the function open. However, the most frequent > operation, reading and writing from the handle, involves no overhead > and its correctness ensured statically. > > That design can be extended to sockets. For example: > > data Socket sort = Socket Int > > data UnconnectedSocket > data ConnectedSocket s > > connect :: RMonadIO (m s) => SocketProto -> SAddress -> > m s (Socket (ConnectedSocket s)) > > sendto :: RMonadIO (m s) => (Socket (ConnectedSocket s)) -> Buffer > -> m s (ReturnCode) > > -- polymorphic in the socket sort > send :: MonadIO m => Socket sort -> Buffer -> m ReturnCode > > > In this design, the operation of creating a socket and connecting it > are bundled together -- which is very common and is the case for > System V, I think (where it is called openActive, I think). If you for > some reason want to keep 'socket' and 'connect' separate, then > 'connect' has to check at run-time that the socket in question is not > connected yet. Still, the most common operations like send and write > should be overhead-free. Cheers, Johan

3 5

Using unsafePerformIO safely
by Hector Guilarte 24 Jun '09

24 Jun '09

Hello, I made a GCL compiler using Alex and Happy and now I'm making the interpreter to that program. Here's the deal: First of all, I'm no expert in the usage of monads. Now: Whenever a "show" instruction is found in any GCL program while the interpretation is being done it is supposed to print on the stdout the string or the aritmetic expresion it was called with, so I guessed I need to run an IO operation and continue the interpretation of my program. I managed to do this using unsafePerformIO and `seq` like is shown below. My question is: Is it safe to use it this way? So far it is working great, but I need to be sure I'm using it in a "safe" way. Like I said, I'm no expert in monads and the System.IO.Unsafe documentation says: " *unsafePerformIO* :: IO<http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t…>a -> a This is the "back door" into the IO<http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t…>monad, allowing IO<http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t…>computation to be performed at any time. For this to be safe, the IO<http://www.haskell.org/ghc/docs/latest/html/libraries/base/System-IO.html#t…>computation should be free of side effects and independent of its environment. " I don't know if the IO computation I'm doing is free of side effects and independent of its enviroment :s. (is just hPutStr stdout ....) Also I've read something about my code not being executed for sure or something like that. Can somebody check the code and tell me if I'm "safe" with it? Thanks a lot! Here's the code: -- Tabla is my Symbol Table of the program being interpreted evalInstruccion:: Instruccion -> Tabla -> Tabla evalInstruccion (ShowY showY) tabla = myRunIO (evalShow showY tabla) evalInstruccion _ tabla = tabla -- There are many other Instructions here missing wich are not relevant to my question {-# NOINLINE myRunIO #-} myRunIO:: (Tabla, IO()) -> Tabla myRunIO tupla = ((unsafePerformIO (snd tupla)) `seq` (fst tupla)) -- Here's the unsafePerformIO.... Am I safe? evalShow:: ShowY -> Tabla -> (Tabla, IO()) evalShow (ShowS string) tabla = (tabla,(hPutStr stdout string)) evalShow (ShowE expr) tabla = (tabla,(hPutStr stdout (show (evalExpr expr tabla)))) -- Don't worry about evalExpr, it works and returns an Int

2 1

Which one is right?
by Linker 24 Jun '09

24 Jun '09

Hi,All, Construct a list: [0,0.1..1] ==================================== || || || || || || ||__ Hugs 98: Based on the Haskell 98 standard ||___|| ||__|| ||__|| __|| Copyright (c) 1994-2005 ||---|| ___|| World Wide Web: http://haskell.org/hugs || || Bugs: http://hackage.haskell.org/trac/hugs || || Version: September 2006 _________________________________________ Haskell 98 mode: Restart with command line option -98 to enable extensions Type :? for help Hugs> [0,0.1..1] [0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0] Hugs> ==================================== GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> [0,0.1..1] [0.0,0.1,0.2,0.30000000000000004,0.4,0.5,0.6,0.7,0.7999999999999999,0.8999999999999999,0.9999999999999999] Prelude> ==================================== Thanks. -- Regards, Linker Lin linker.m.lin(a)gmail.com

5 4

Suggestion for Network.Socket in regards to PortNumber
by John Van Enk 24 Jun '09

24 Jun '09

Hello List, Is there any one else in favor of hiding the PortNum constructor in Network.Socket in the next release? Here's why: Prelude> :m + Network.Socket Data.Word Prelude Network.Socket Data.Word> let p = 5000 :: Word16 Prelude Network.Socket Data.Word> let p' = PortNum p Prelude Network.Socket Data.Word> let p'' = fromIntegral p :: PortNumber Loading package parsec-2.1.0.1 ... linking ... done. Loading package network-2.2.1.1 ... linking ... done. Prelude Network.Socket Data.Word> p 5000 Prelude Network.Socket Data.Word> p' 34835 Prelude Network.Socket Data.Word> p'' 5000 Notice that using the PortNum constructor does not at all do what the user expects. This really should be a hidden constructor. Perhaps we can add the following: mkPortNum :: (Num a) => a -> PortNumber mkPortNum p = fromIntegral p /jve

4 12

Re: [Haskell-cafe] GHCi infers a type but refuses it as type signature
by papa.eric＠free.fr 24 Jun '09

24 Jun '09

> That depends on the monad library. In transformers it would be: > > (Monad m, Eq a) => a -> StateT [a] m Bool > > State s is just a type synonym for StateT s Identity, so this works for State as well. I like it, it is simpler than the one using MonadState. I had read many tutorials and wiki articles, and saw nowhere that there were different implementations of what seemed to be standard libraries. > On a higher level, in case you are interested, here's a description of > how I would model your problem. Actually using a monad transformer was the goal of it all, tutorial-like. The example was contrived. Another question would be: when is it relevant to use monad transformers? I'm not sure to have enough haskell practice to be ready for that one, though. :^) And for sure, my example didn't need it. Thanks Eric

2 1

Haskell on the iPhone
by Ryan Trinkle 24 Jun '09

24 Jun '09

Dear Haskellers, Recently, there's been a groundswell of activity in the Haskell community regarding the Haskell's use in developing iPhone games. The iPhone is a powerful, innovative platform (with a great monetization scheme, to boot), and it's not surprising that many of us would want to develop apps for it in our favorite language. I am proud to announce today that my company, iPwn Studios Inc., is currently preparing to release an open source patch to GHC that allows it to output binaries for iPhone OS. The patch will be released under a BSD license as soon as possible and hopefully integrated into the GHC main-line in the near future. As the first (to my knowledge) Haskell-based game studio, iPwn Studios is committed to giving back to the Haskell community through open source - contributing to a rising tide that lifts us all. I would like to take this opportunity to propose the creation of a haskell-iphone mailing list, so that all Haskellers working with the iPhone - whether for profit or for pleasure - can come together to make Haskell a force to be reckoned with in the burgeoning iPhone App marketplace. Best wishes, Ryan Trinkle President, iPwn Studios Inc. P.S.: If you wish to be involved in the preparation of the GHC patch or in the creation of iPwn Studios' first game, don't hesitate to contact me by email (ryant5000(a)gmail.com) AIM (RyanT5000), or IRC (RyanT5000 on irc.freenode.net)

10 15

rewrite rules
by Sjoerd Visscher 24 Jun '09

24 Jun '09

Hi all, I have a rewrite rule as follows: {-# RULES "transform/transform" forall (f::forall m. Monoid m => (a -> m) -> (b - > m)) (g::forall m. Monoid m => (b -> m) -> (c -> m)) (l::FMList c). transform f (transform g l) = transform (g.f) l #-} It fires on this code: print $ transform (. (*2)) (transform (. (+1)) (upto 10)) But it doesn't fire on this code: print $ map (*2) (map (+1) (upto 10))) with map g x = transform (. g) x and with or without {-# INLINE map #-}. What am I doing wrong? -- Sjoerd Visscher sjoerd(a)w3future.com

3 6

ICFP contest
by Rafael Gustavo da Cunha Pereira Pinto 24 Jun '09

24 Jun '09

Hi, The good folks here are really quiet about the ICFP Contest. Is anyone participating this year? As in the previous four years, I will probably download the problem, take a look, and try for a while... Having a family don't allow me to go much further, especially when teaming up with myself! Best regards, Rafael Gustavo da Cunha Pereira Pinto

4 4

ANN: darcs 2.3 beta 1
by Petr Rockai 24 Jun '09

24 Jun '09

Hi! I'd like to announce immediate availability of a first beta release of darcs 2.3. There is a number of improvements and bugfixes over the last stable release (2.2). Moreover, work has been done on performance of "darcs whatsnew" for large repositories. This has also introduced a slight risk of regressions, but please note that all of the disruptive changes are in read-only code paths: the new code will never touch your repository, so it is unable to cause permanent harm. The worst that could happen is that you get no or bad diff from "darcs whatsnew". (This is also a reason why we need your testing!) There is only a single installation package for this release of darcs: cabalised source. (Please note that the final version with also come with the legacy autoconf-based buildsystem, for the last time.) You can either download a tarball from <http://repos.mornfall.net/darcs/darcs-2.2.98.1.tar.gz> and build manually (see the build instructions in README inside the tarball), or, alternatively, you can use cabal-install to obtain a copy (the beta release is now available on Hackage): $ cabal update $ cabal install darcs-beta This should give you a darcs binary in `~/.cabal/bin` -- you should probably add that to your PATH. (Note: The package name on Hackage is different, since people installing darcs from Hackage are expecting a stable version. The name change means that you cannot use the Hackage version to build other packages that depend on the darcs library: you either need the tarball for this, or you can use the stable version from Hackage.) There is a quick (possibly incomplete) list of important changes: * lots and lots of documentation changes (Trent) * haskeline improvements (Judah) * cabal as default buildsystem (many contributors) * fixes in darcs check/repair memory usage (Bertram, David) * performance improvement in subtree record (Reinier) * --summary --xml (Florian Gilcher) * changes --max-count (Eric and myself) * fix changes --only-to-files for renames (Dmitry) * performance fix in "darcs changes" (Benedikt) * hardlinks on NTFS (Salvatore) * coalesce more changes when creating rollbacks (David) * new unit test runner (Reinier) * darcs-shell in contrib (László, Trent) * .authorspellings (Simon) -- I find this to be controversial though * working directory index and substantial "darcs wh" optimisation (myself) * gzip CRC checking and repair feature (Ganesh) and there is a number of issues that has been resolved since 2.2: * 948: darcsman (Trent) * 1206: countable nouns (Trent) * 1285: cabal test v. cabal clean (Trent) * 1302: use resolved, not resolved-in-unstable (Trent) * 1235: obliterate --summary (Rob) * 1270: no MOTD for --xml-output (Lele) * 1311: cover more timezones (Dave) * 1292: re-encoding haskeline input (Judah) * 1313: clickable ToC and refs in PDF manual Trent) * 1310: create merged \darcsCommand{add} (Trent) * 1333: better "cannot push to current repository" warning (Petr) * 1347: (autoconf) check for unsafeMMapFile if mmap use enabled (Dave) * 1361: specify required includes for curl in cabal file (Reinier) * 1379: remove libwww support (Trent) * 1366: remove unreachable code for direct ncurses use (Trent) * 1271: do not install two copies of darcs.pdf (Trent) * 1358: encode non-ASCII characters in mail headers (Reinier) * 1393: swap "darcs mv" and "darcs move" (Trent) * 1405: improve discoverability of global author file (Trent) * 1402: don't "phone home" about bugs (Trent) * 1301: remove obsolete zsh completion scripts (Trent) * 1162: makeAbsolute is now a total function (Ben F) * 1269: setpref predist - exitcode ignored bug (Ben M) * 1415: --edit-long-comment, not --edit-description, in help (Trent) * 1413: remove duplicate documentation (Trent) * 1423: complain about empty add/remove (Trent) * 1437: Implement darcs changes --max-count (Eric) * 1430: lazy pattern matching in (-:-) from Changes command module (Dmitry) * 1434: refactor example test (Trent) * 1432: refer to %APPDATA%, not %USERPROFILE% (Trent) * 1186: give a chance to abort if user did not edit description file (Dmitry) * 1446: make amend-record -m foo replace only the patch name (Dmitry) * 1435: default to get --hashed from a darcs-1.0 source (Trent) * 1312: update and reduce build notes (Trent) * 1351: fix repository path handling on Windows (Salvatore) * 1173: support hard links on NTFS (Salvatore) * 1248: support compressed inventories for darcs-1 repos (Ganesh) * 1455: implement "darcs help environment" (Trent) Yours, Petr. -- Petr Ročkai | http://web.mornfall.net A physicist is an atom's way of knowing about atoms. (George Wald)

1 0