- Haskell-Cafe - Haskell.org

Re: Nice way to calculate character frequency in a string
by Scherrer, Chad 25 Oct '05

25 Oct '05

> Hello, I need to calculate the frequency of each character in a > String. And if I can do this really well in C, I don't find a nice (and > fast) answer in haskell. I tried several functions, listed below, and > even the fastest do a lot of unnecessary things : A while back, I was trying to build a "table" function similar to what you describe, and Dean Herrington helped me speed it up and stop the stack overflows I had been getting. Here it is, in case this is useful to you... table :: (Ord a) => [a] -> [(a,Int)] table xs = Map.assocs $! foldl' f Map.empty xs where f m x = let m' = Map.insertWith (+) x 1 m Just v = Map.lookup x m' in v `seq` m' I would be interested in whether this is much slower than the other approaches you've tried. If a faster approach could be made polymorphic, I'd have a faster way to build tables! Chad Scherrer Computational Mathematics Group Pacific Northwest National Laboratory "Time flies like an arrow; fruit flies like a banana." -- Groucho Marx

1 0

RE: [Haskell-cafe] Nice way to calculate character frequency inastring
by Simon Peyton-Jones 25 Oct '05

25 Oct '05

| > Better still, help us make it faster! | > | > Simon | | What can your average Haskell user do to help other than | point out things they don't like? Well-characterised test cases are always motivating: small programs that should go fast, and don't. Why does the brain-twisting version work fast, and the obvious code go slow. Ian Lynagh's recent message was a good example [although I'm afraid we have still not done anything about it] http://urchin.earth.li/~ian/bench/bench-0.2/ghc-6.4.1.html. The next step is to look at the intermediate code that GHC produces, and try to see what's different about the good and bad version. Sometimes, as Simon M's recent message mentioned, there are things that aren't easy to change, like auto-unboxing of arrays. Other times there are just missing SPECIALISE pragmas and the like. The more the problem is characterised, the more likely we are to do something about it. Simon

1 0

Re: [Haskell-cafe] Nice way to calculate character frequency in a string
by Jon Fairbairn 25 Oct '05

25 Oct '05

On 2005-10-25 at 13:42+0200 "Charles SDudu" wrote: > > okay, it took me some time to make your solution work, but it's as fast as > the precedent solution, and really more elegant. Thank you, but I dont know > how to structure the function, see yourself : > > calc str = filter (\p -> snd p > 0) $ assocs $ ((accumArray (+) 0 (toEnum 0, > toEnum 255) (map (\x->(x,1)) str)) :: UArray Char Int) > > It's not so nice but it works, isn't there a solution to put the type > elsewhere, and another type than UArray ? Well, you can do this: import Array calc::String->[(Char, Int)] calc = filter (\p-> snd p > 0) . assocs . accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) You can import whatever sort of array you want, so long as it has assocs and accumArray. You don't want to change minBound and maxBound to toEnum x, since they are the bounds of Char, which might or might not be 0 and 255. Jón -- Jón Fairbairn Jon.Fairbairn at cl.cam.ac.uk

2 1

RE: [Haskell-cafe] Nice way to calculate character frequency in astring
by Simon Marlow 25 Oct '05

25 Oct '05

On 25 October 2005 11:59, Jon Fairbairn wrote: > On 2005-10-25 at 12:20+0200 Lemmih wrote: >> On 10/25/05, Charles SDudu <iwin_1(a)hotmail.com> wrote: >>> Hello, I need to calculate the frequency of each >>> character in a String. And if I can do this really well >>> in C, I dont find a nice (and fast) answer in haskell. I >>> tried several functions, listed below, and even the >>> fastest do a lot of unnecessary things : >>> >>> calc :: String -> [ (Char, Int) ] >>> calc = filter (\p -> snd p > 0) . assocs . >>> foldl (\k c -> unsafeReplace k [(fromEnum c, >>> (unsafeAt k (fromEnum c))+1)] ) k where k = array >>> (toEnum 0, toEnum 255) [(toEnum i, 0) | i <- [0 .. 255]] >>>>> UArray Char Int > > [snip even more disagreable code] > > Ugh! These are all horrid. If something on the lines of > >> calc = accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) > > isn't fast enough, complain to the implementors! What's the > point of functional programming if one has to twist into a > shape that allows inspection of one's own fundament to get > stuff to run in decent time? To make that go fast, you'd want to use a UArray. Could the compiler figure this out for itself? Not really, it might be able to figure out certain special cases where changing an Array to a UArray doesn't affect the semantics, but not in general (and GHC certainly makes no attempt to do it). Sometimes, you just need to give the compiler a bit of help. And you really want to read the file as a packed string, not a String. Or hope that GHC manages to deforest calc with whatever is generating the String. It's possible that calc deforests, but highly unlikely that hGetContents does, so I'm afraid you'll have to do the packed string conversion yourself. To make it go even faster, you need to inline & specialise accumArray. I'm not sure how much of this GHC currently does. Cheers, Simon

1 0

RE: [Haskell-cafe] Nice way to calculate character frequency in astring
by Simon Peyton-Jones 25 Oct '05

25 Oct '05

| Ugh! These are all horrid. If something on the lines of | | > calc = accumArray (+) 0 (minBound, maxBound) . (map (\x->(x,1))) | | isn't fast enough, complain to the implementors! What's the | point of functional programming if one has to twist into a | shape that allows inspection of one's own fundament to get | stuff to run in decent time? I agree. Better still, help us make it faster! Simon

2 1

RE: [Haskell-cafe] Safe FFI calls, -threaded and killThread
by Simon Marlow 25 Oct '05

25 Oct '05

On 25 October 2005 09:07, Einar Karttunen wrote: > I noticed that killThread in GHC behaves in a problematic fashion with > -threaded when the killed thread is in a midle of performing a safe > FFI call. If the behaviour (blocking until the call is done) is > intended adding documentation might be nice. > > The example below demonstrates the problem. Tthe program gets stuck > in the killThread call which is not very intuitive. Wrapping every > killThread in forkIO does not sound very nice either. > > - Einar Karttunen > > import Control.Concurrent > import Foreign.C > > foreign import ccall threadsafe "sleep" sleep :: CInt -> IO CInt > > main = do mv <- newEmptyMVar > tid <- forkIO $ sleep 100 >> putMVar mv () > threadDelay 10000 > e <- isEmptyMVar mv > if e then do putStrLn "killing sleeper" > killThread tid > putStrLn "done" > else do putStrLn "sleeper already done" This is correct, I'll document the behaviour. killThread/throwTo is currently synchronous - that is, it blocks until the exception has been delivered to the target thread (unlike the version in our PLDI paper which was non-blocking, IIRC). A non-blocking version can easily be constructed by using forkIO, as you noted. We can't kill a thread that is involved in a safe foreign call, because we have no control over the thread involved in the call. This is the really the only sensible behaviour. In the case of an unbound Haskell thread it would be possible to kill the Haskell thread while leaving the foreign call running, but this can't be done if the Haskell thread is bound (because the OS thread it is bound to is currently running foreign code). Cheers, Simon

1 0

Safe FFI calls, -threaded and killThread
by Einar Karttunen 25 Oct '05

25 Oct '05

Hello I noticed that killThread in GHC behaves in a problematic fashion with -threaded when the killed thread is in a midle of performing a safe FFI call. If the behaviour (blocking until the call is done) is intended adding documentation might be nice. The example below demonstrates the problem. Tthe program gets stuck in the killThread call which is not very intuitive. Wrapping every killThread in forkIO does not sound very nice either. - Einar Karttunen import Control.Concurrent import Foreign.C foreign import ccall threadsafe "sleep" sleep :: CInt -> IO CInt main = do mv <- newEmptyMVar tid <- forkIO $ sleep 100 >> putMVar mv () threadDelay 10000 e <- isEmptyMVar mv if e then do putStrLn "killing sleeper" killThread tid putStrLn "done" else do putStrLn "sleeper already done"

1 0

RE: [Haskell-cafe] Template Haskell -- Bug?
by Simon Marlow 24 Oct '05

24 Oct '05

On 20 October 2005 14:03, Gracjan Polak wrote: > $ ghc --make THTest1.hs > Chasing modules from: THTest1.hs > Skipping THTest1TH ( ./THTest1TH.hs, ./THTest1TH.o ) > Compiling THTest1 ( THTest1.hs, THTest1.o ) > Loading package base-1.0 ... linking ... done. > Loading package haskell98-1.0 ... linking ... done. > Loading package template-haskell-1.0 ... linking ... done. > (here core dump, aka 0xc00000001) > > > > First of all, I do not understand the error in first compilation. > Second, core dump is not nice :) > > My config: > > Windows XP Home, > > $ ghc -v > Glasgow Haskell Compiler, Version 6.4, for Haskell 98, compiled by GHC Please try again with 6.4.1; lots of bugs were fixed. Cheers, Simon

2 1

Help using QuickCheck
by Benjamin Franksen 23 Oct '05

23 Oct '05

Hello All, I am asking help with using QuickCheck. I tried everything I could think of, but invariably as soon as I start invoking the quickCheck function on my property it fails with *Data.FingerSearchTreeUtil> Top level: No instance for (Show (IO ())) arising from use of `print' at Top level Probable fix: add an instance declaration for (Show (IO ())) In a 'do' expression: print it <interactive>:1:0: No instances for (Arbitrary (OrdSeq Int), Show (OrdSeq Int)) arising from use of `quickCheck' at <interactive>:1:0-20 Probable fix: add an instance declaration for (Arbitrary (OrdSeq Int), Show (OrdSeq Int)) In the definition of `it': it = quickCheck prop_DeleteInsert The property is quite a simple one: prop_DeleteInsert x xs = delete x (insert x xs) == xs where types = xs :: OrdSeq Int My code compiles just fine with ghc. I tried some examples from the QuickCheck manual and these seem to work; at least I get the expected "OK, passed 100 tests.". What am I doing wrong? Besides, there are some really non-obvious quirks with QuickCheck. For instance, the following one caused me some headache: I downloaded the haskell script 'quickCheck' and modified the line where ghci is executed like this: system ("/usr/bin/ghci -cpp -package QuickCheck "++options opts'++" <hugsin") (I am using ghc 6.4.1, btw). Running 'quickCheck Data/FingerSearchTreeUtil.hs' gives me: <interactive>:1:0: Failed to load interface for `QuickCheck': Could not find module `QuickCheck': it is a member of package util-1.0, which is hidden Strange. Replacing 'ChickCheck' with 'util' gives me the above error message about "No instance for (Show (IO ()))..." Ben

3 6

RE: [Haskell-cafe] FastString a misnomer
by Simon Marlow 22 Oct '05

22 Oct '05

On 21 October 2005 02:53, Donald Bruce Stewart wrote: > john: >> On Thu, Oct 20, 2005 at 10:45:28AM +0100, Simon Marlow wrote: >>> I think when this is ready it should replace Data.PackedString. >>> >>> I don't necessarily mean put it into fptools/libraries/base - we >>> could just remove the existing Data.PackedString from there and >>> your separate package can provide Data.PackedString. That is, >>> unless we decide to use it in GHC in some way, in which case we'll >>> have to pull (a copy of) it into fptools/libraries. >> >> We should make 'PackedString' the UTF8 wrapper though and provide >> Data.ByteArray as a separate library. If it has string in the name, >> one should be able to replace strings with it everywhere and expect >> the right thing to happen as enforced by the type system. that and >> C's conflation of characters and bytes and Haskell 98s lack of >> clearing up the issue has been a huge pet peeve of mine. > > Ok, so a rough structure of the final lib would be: > > Data Data System > | | | > ByteArray (?) PackedString Posix > | | | > UTF8 Latin1 ... MMap (providing > mmapFile :: FilePath -> ByteArray) Remind me what Data.ByteArray is for? Seems like it would overlap a lot with Data.PackedString.Latin1 and UArray Word8. We should have Data.PackedString.UTF16 too; it'll make interoperating with Win32 APIs easier as Bulat pointed out. I like John Meacham's suggestion of changing the UTF8 representation to include a count of characters as well as bytes. I'm not volunteering to do it, just adding my "+1" in case anyone else wanted to :-) Cheers, Simon

3 2