November 2006 - Haskell-Cafe

Finding Memory Leaks
by Matthew Bromberg 03 Nov '06

03 Nov '06

I have a rather complex Haskell program that performs an engineering simulation using a lot of large complex valued matrices. The imperative components of the simulation are written in C and interfaced into Haskell which handles the higher level logic. This has served me fairly well, and I've been pleased with both the development style and the performance of my code. However I've run into a fairly major issue with an unresolvable memory leak in the Haskell code. The memory leak is apparent since both private allocated bytes and page file bytes associated with the process increase linearly over time while the process is running. Eventually it causes the process to crash. I believe it's in the Haskell code because I have replaced malloc, free, realloc etc. in the C code with a memory leak detector and the C code appears to free all allocated resources. I also know that the memory leak is due to unmatched free's from a call to malloc from one of the windows XP system libraries. Unfortunately GHC's heap profiler does not reveal the memory leak. All my code is compiled using the -prof -auto flag and then run using +RTS -hc -RTS. The resulting plots do not show a linear increase in heap usage, although the Windows XP operating system does report such an increase. This leaves me in a difficult position in terms of finding the offending code. I am currently resorting to commenting out code line by line, but it's very tedious since I have to preserve the state functionality of the code to get it to run. Is there a way to compile Haskell into C using GHC and then forcing the C code to hook up to the memory leak detecting versions of malloc? I know that GHC can produce intermediary C code, but I have no idea how to access it and how to setup all the run time libraries etc, so that I can compile the C code separately. Any advice for me in this situation would be appreciated.

4 5

[Haskell-cafe]Prime Generator time limit exceeded
by alaiyeshi 03 Nov '06

03 Nov '06

Hi I'm new to Haskell. I found this site on the Haskell wiki https://www.spoj.pl. But I got some trouble on trying to solve the problem titled "Prime Generator" https://www.spoj.pl/problems/PRIME1. The online-judge system tells me "time limit excedded" Would you be so kind to tell me how to make it more faster? And any other suggestion is welcome. Thanks in advance. --------------------------------------Code begin------------------------------------------------------------ module Main where import IO import List main = do input_size<-getLine content<-get_contents (read input_size) mapM_ (\r-> do mapM_ (print) (primeGenerator (parse r)); putStrLn "") content get_contents n | n == 0 = return [] | otherwise = do content<-getLine rests<-get_contents (n-1) return ([content]++rests) primeGenerator [start,end] = [x | x<-[start..end], all (== 1) (map (gcd x) [2..(x-1)]), x/=1] parse s = unfoldr (\x-> case x of [] -> Nothing _ -> Just (head (reads x))) s -------------------------------Code ends-------------------------------------------------------------------------------- (BTW: I'm new to this mailling list also, forgive my rudeness if I am, and forgive my poor English)

5 11

Cost of seq (sorry about the old subject)
by Chad Scherrer 03 Nov '06

03 Nov '06

On 11/2/06, Bulat Ziganshin <bulat.ziganshin(a)gmail.com> wrote: > Hello Chad, > > Thursday, November 2, 2006, 8:49:17 PM, you [Chad] wrote: > > Would it be possible for the type system to distinguish at compile > > time whether something would need to be evaluated, and optimize away > > redundant `seq`s? Maybe this is what the strictness analyzer does > > already. > > afaik, seq cost is zero (except for evaluating expressions, of course) > So if x has already been evaluated, does x `seq` y evaluate just as quickly as y alone, or does it require extra cycles to make sure x has been evaluated? -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

2 1

Re: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

On 11/2/06, Sebastian Sylvan <sylvan(a)student.chalmers.se> wrote: > On 11/2/06, Slavomir Kaslev <slavomir.kaslev(a)gmail.com> wrote: > > Little by little, I think I am getting closer. > > > > class Show a => Visible a where > > toString :: a -> String > > toString = show > > size :: a -> Int > > size = length . show > > > > Is just declaration, not definition. It doesn't define anything, even > > though it has default implementations for toString and size one still > > needs to define instance of it. Right? > > > > As Sebastian Sylvan proposed, I probably need something like this: > > > > class Visible a where > > toString :: a -> String > > size :: a -> Int > > > > instance Show a => Visible a where > > toString = show > > size = length . show > > > > But it seems ghc doesn't like instance definitions like 'instance Show > > a => Visible a where ...'. Why? > > This is not Haskell98 since instance declarations of this form could > cause the type checker to go into an infinite loop. This particular > one is okay, though, but you have to start ghc with > -fallow-undecidable-instances and -fglasgow-exts I'm afraid. > > > -- > Sebastian Sylvan > +46(0)736-818655 > UIN: 44640862 > Thanks, Sebastian. That was helpful. Are there any papers on the subject? -- Slavomir Kaslev

3 3

How to improve speed? (MersenneTwister is several times slower than C version)
by isto 03 Nov '06

03 Nov '06

Hi all, On HaWiki was an announcement of MersenneTwister made by Lennart Augustsson. On a typical run to find out 10000000th rnd num the output is (code shown below): $ time ./testMTla Testing Mersenne Twister. Result is [3063349438] real 0m4.925s user 0m4.856s I was exercising with the very same algorithm and tried to make it efficient (by using IOUArray): now a typical run looks like (code shown below): $ time ./testMT Testing Mersenne Twister. 3063349438 real 0m3.032s user 0m3.004s The original C-version (modified so that only the last number is shown) gives typically $ time ./mt19937ar outputs of genrand_int32() 3063349438 real 0m0.624s user 0m0.616s Results are similar with 64 bit IOUArray against 64 bit C variant. C seems to work about 5 to 10 times faster in this case. I have tried to do different things but now I'm stuck. unsafeRead and unsafeWrite improved a bit the lazy (STUArray-version) and IOUArray-versions but not very much. I took a look of Core file but then, I'm not sure where the boxed values are ok. E.g. should IOUArray Int Word64 be replaced with something else? Any hints and comments on how to improve the efficiency and make everything better will be appreciated a lot! br, Isto ----------------------------- testMTla.hs (MersenneTwister, see HaWiki) module Main where -- ghc -O3 -optc-O3 -optc-ffast-math -fexcess-precision --make testMTla import MersenneTwister main = do putStrLn "Testing Mersenne Twister." let mt = mersenneTwister 100 w = take 1 (drop 9999999 mt) -- w = take 1 (drop 99 mt) putStrLn $ "Result is " ++ (show w) ----------------------------- ----------------------------- testMT.hs module Main where -- Compile eg with -- ghc -O3 -optc-O3 -optc-ffast-math -fexcess-precision --make testMT import Mersenne genRNums32 :: MT32 -> Int -> IO (MT32) genRNums32 mt nCnt = gRN mt nCnt where gRN :: MT32 -> Int -> IO (MT32) gRN mt nCnt | mt `seq` nCnt `seq` False = undefined gRN mt 1 = do (r,mt') <- next32 mt putStrLn $ (show r) return mt' gRN mt nCnt = do (r,mt') <- next32 mt gRN mt' $! (nCnt-1) main = do putStrLn "Testing Mersenne Twister." mt32 <- initialiseGenerator32 100 genRNums32 mt32 10000000 ----------------------------- ----------------------------- Mersenne.hs (sorry for linewraps) module Mersenne where import Data.Bits import Data.Word import Data.Array.Base import Data.Array.MArray import Data.Array.IO -- import System.Random data MT32 = MT32 (IOUArray Int Word32) Int data MT64 = MT64 (IOUArray Int Word64) Int last32bitsof :: Word32 -> Word32 last32bitsof a = a .&. 0xffffffff -- == (2^32-1) lm32 = 0x7fffffff :: Word32 um32 = 0x80000000 :: Word32 mA32 = 0x9908b0df :: Word32 -- == 2567483615 -- Array of length 624. initialiseGenerator32 :: Int -> IO MT32 initialiseGenerator32 seed = do let s = last32bitsof (fromIntegral seed)::Word32 mt <- newArray (0,623) (0::Word32) unsafeWrite mt 0 s iG mt s 1 mt' <- generateNumbers32 mt return (MT32 mt' 0) where iG :: (IOUArray Int Word32) -> Word32 -> Int -> IO (IOUArray Int Word32) iG mt lastNro n | n == 624 = return mt | otherwise = do let n1 = lastNro `xor` (shiftR lastNro 30) new = (1812433253 * n1 + (fromIntegral n)::Word32) unsafeWrite mt n new iG mt new (n+1) generateNumbers32 :: (IOUArray Int Word32) -> IO (IOUArray Int Word32) generateNumbers32 mt = gLoop 0 mt where gLoop :: Int -> (IOUArray Int Word32) -> IO (IOUArray Int Word32) gLoop i mt | i==623 = do wL <- unsafeRead mt 623 w0 <- unsafeRead mt 0 w396 <- unsafeRead mt 396 let y = (wL .&. um32) .|. (w0 .&. lm32) :: Word32 if even y then unsafeWrite mt 623 (w396 `xor` (shiftR y 1)) else unsafeWrite mt 623 (w396 `xor` (shiftR y 1) `xor` mA32) return mt | otherwise = do wi <- unsafeRead mt i wi1 <- unsafeRead mt (i+1) w3 <- unsafeRead mt ((i+397) `mod` 624) let y = (wi .&. um32) .|. (wi1 .&. lm32) if even y then unsafeWrite mt i (w3 `xor` (shiftR y 1)) else unsafeWrite mt i (w3 `xor` (shiftR y 1) `xor` mA32) gLoop (i+1) mt next32 :: MT32 -> IO (Word32, MT32) next32 (MT32 mt i) | i >= 624 = do mt' <- generateNumbers32 mt let m = MT32 mt' (i `mod` 624) (w,m') <- next32 m return (w,m') | otherwise = do y <- unsafeRead mt i let y1 = y `xor` (shiftR y 11) y2 = y1 `xor` ((shiftL y1 7 ) .&. 0x9d2c5680) -- == 2636928640 y3 = y2 `xor` ((shiftL y2 15) .&. 0xefc60000) -- == 4022730752 y4 = y3 `xor` (shiftR y3 18) return $ (y4, MT32 mt (i+1)) mA64 = 0xB5026F5AA96619E9 :: Word64 um64 = 0xFFFFFFFF80000000 :: Word64 lm64 = 0x7FFFFFFF :: Word64 initialiseGenerator64 :: Int -> IO (MT64) initialiseGenerator64 seed = do let s = (fromIntegral seed)::Word64 mt <- newArray (0,311) (0::Word64) unsafeWrite mt 0 s iG mt s 1 generateNumbers64 mt return (MT64 mt 0) where iG :: (IOUArray Int Word64) -> Word64 -> Int -> IO (IOUArray Int Word64) iG mt lN i | mt `seq` lN `seq` i `seq` False = undefined iG mt lastNro 312 = return mt iG mt lastNro n = do let n1 = lastNro `xor` (shiftR lastNro 62) new = (6364136223846793005 * n1 + (fromIntegral n)::Word64) unsafeWrite mt n new iG mt new $! (n+1) generateNumbers64 :: (IOUArray Int Word64) -> IO () generateNumbers64 mt = gLoop 0 where gLoop :: Int -> IO () gLoop i | i `seq` False = undefined gLoop 311 = do wL <- unsafeRead mt 311 w0 <- unsafeRead mt 0 w155 <- unsafeRead mt 155 let y = (wL .&. um64) .|. (w0 .&. lm64) :: Word64 if even y then unsafeWrite mt 311 (w155 `xor` (shiftR y 1)) else unsafeWrite mt 311 (w155 `xor` (shiftR y 1) `xor` mA64) return () gLoop i = do wi <- unsafeRead mt i wi1 <- unsafeRead mt (i+1) w3 <- unsafeRead mt ((i+156) `mod` 312) let y = (wi .&. um64) .|. (wi1 .&. lm64) if even y then unsafeWrite mt i (w3 `xor` (shiftR y 1)) else unsafeWrite mt i (w3 `xor` (shiftR y 1) `xor` mA64) gLoop $! (i+1) next64 :: MT64 -> IO (Word64, MT64) next64 (MT64 mt 312) = do generateNumbers64 mt let m = MT64 mt 0 (w,m') <- next64 m return (w,m') next64 (MT64 mt i) = do y <- unsafeRead mt i let y1 = y `xor` ((shiftR y 29) .&. 0x5555555555555555) y2 = y1 `xor` ((shiftL y1 17) .&. 0x71D67FFFEDA60000) y3 = y2 `xor` ((shiftL y2 37) .&. 0xFFF7EEE000000000) y4 = y3 `xor` (shiftR y3 43) return $! (y4, MT64 mt (i+1))

5 14

Non-integer part of a Double
by Maurício 03 Nov '06

03 Nov '06

Hi, Is there a function to get that? I'm using \x -> x - fromIntegral(floor x) since I was not able to find something better, but I guess I have missed something in the standard library since there are functions with similar funcionality. Thanks, Maurício

3 3

Fwd: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

Little by little, I think I am getting closer. class Show a => Visible a where toString :: a -> String toString = show size :: a -> Int size = length . show Is just declaration, not definition. It doesn't define anything, even though it has default implementations for toString and size one still needs to define instance of it. Right? As Sebastian Sylvan proposed, I probably need something like this: class Visible a where toString :: a -> String size :: a -> Int instance Show a => Visible a where toString = show size = length . show But it seems ghc doesn't like instance definitions like 'instance Show a => Visible a where ...'. Why? -- Slavomir Kaslev

2 1

Re: [Haskell-cafe] Class
by Slavomir Kaslev 03 Nov '06

03 Nov '06

On 11/2/06, Sebastian Sylvan <sylvan(a)student.chalmers.se> wrote: > On 11/2/06, Slavomir Kaslev <slavomir.kaslev(a)gmail.com> wrote: > > > > > Visible 'subclasses' Show. Doesn't this mean that Visible should be > > defined for all types with Show instances? > > No, it just means that any type that you want to instantiate in > Visible needs to also have a Show instance (is this a restriction you > really want? See below). Well, yes that's what I meant. I want class Visible for objects that have Show instance and I want to be able to use this Show instance in the definition of Visible. Again this is not some practical example, I am just trying to grasp Haskell classes and instances. > > You could do something like > > instance Show a => Visible a > > (the default implementations that you provided in the class should be > enough, you could possibly move the implementations to the "Show > instance" and remove the Show super class from the Visible class - > then you could make even non-Show types instances of Visible without > having to define their instance for Show as well). > > /S > > > -- > Sebastian Sylvan > +46(0)736-818655 > UIN: 44640862 > This doesn't work either: import List class Visible a where toString :: a -> String size :: a -> Int instance Show a => Visible a where toString = show size = length . show instance Visible a => Visible [a] where toString = concat . map toString size = foldl (+) 0 . map size vSort :: (Visible a, Ord a) => [a] -> String vSort = toString . List.sort s = vSort [1..3] gives: Illegal instance declaration for `Visible a' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `Visible a' Failed, modules loaded: none. at instance Show a => Visible a where. Probably I should reconsider my expectations? How should something like this designed? -- Slavomir Kaslev

2 3

Decorating a list of strings
by Steve Schafer 03 Nov '06

03 Nov '06

I have a list of text strings: ["Alice", "Bob", "Cindy", "Bob", "Bob", "Dave", "Cindy"] As you can see, some of the strings occur only once; others appear two or more times. I would like to end up with a new list, according to the following rules: 1) If a string occurs only once in the original list, then that string appears unchanged in the new list. 2) If a string occurs more than once in the original list, then each occurrences of that string is "decorated" with a numerical suffix indicating its relative position among its peers. In the case of the above list, the result of applying these rules would be: ["Alice", "Bob:1", "Cindy:1", "Bob:2", "Bob:3", "Dave", "Cindy:2"] So, how do we do this? The straightforward approach is to traverse the list twice, once to build a table of repeat counts for the different strings, and a second time to generate the new list, based on the old list plus the table of repeat counts. Of course, it's possible to streamline this into a single traversal by building up a list of thunks at the same time as the table of repeat counts is generated, and then to resolve those thunks by applying them in one fell swoop to the table. But while this does _conceptually_ streamline the problem, it doesn't offer any practical improvement; it takes at least as much processing effort to resolve the thunks as it would to make a second pass through the list. Can we do better? I can't think of a way to do better, and my gut feeling is that there isn't one (in general, it's impossible to know whether the first element of the new list will be "Alice" or "Alice:1" until the entire original list has been traversed), but I thought I'd put the question out to the community to see if anyone had any brilliant insights. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

3 3

Towards an IO-Comonad that preserves referential integry (was: "comonads, io" Jan 02, 2003)
by Sven Biedermann 03 Nov '06

03 Nov '06

Dear Haskellers, The OI Comonad in Richard Kieburtz' paper does break referential integrity, but he worte, that the implementation is just something "...to experiment with". In this papers he states, that a real OI needs special properties. For instance enableOI needs "...to have the effect of copying pointers to currently accessible IO resources, in effect duplicating the current IO environment." So, I wrote a simple OI-Comonad for stdin/stdout only, that preserves referential integrity. At least, my reasoning and the tests I made didn't reveal anything different. The code and some explanations are presented at the end of this mail. Haskellers: Could you review the solution, please? Does it really preserves referential integrity? Or am I completely wrong? Do you have any suggestions on generalizing the idea? I would be glad to hear from you! Best regards Sven Biedermann ---------------------------------------------------------------- The implementation is based on two ideas: 1) The OI outside world is modeled an infinite structure (OIReality) that keeps track effects created in the outside world. All "futures" of a reality at a point of "time" are remembered in a lazy fashion. So, if one probes on referential integrity, the structure will be re-iterated through, playing back already computed results. If a reality at some point of "time" isn't referenced any more, that reality will be reclaimed by the garbage collector. The following statement is an example, that no space leaks occur as long as a specific reality isn't remembered (stdPutStr builds on basic stdPutChar using the standard operators .>> and =>>): extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStr Amazingly, extract $ mkOI 'x' .>> (cycle ['A'..'z']) =>> oiPutStrLn produces a space leak, because the implementation isn't lazy enough, yet. 2) The OI-Comonad is a pointer to the current reality, together with the value, that can be extracted from OI. Whenever an OI ist rememberable by the user, the pointer will be duplicated. This is crucial for referential integrity. Comain, as defined by Andrew Bromage in : comain :: OI a -> () comain w = extract (w .>> show (a,b) =>> oiPutStrLn) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) now works as intended and delivers, if 'x' is typed in on standard input: ('x','x') "a = ..." runs on reality w, yielding 'x' . "b = ..." is just a play back of "a = ...". "extract (w.>> show (a,b) =>> stdPutStrLn)" is another future of w, which just prints ('x','x'). module SimpleOI where import Control.Monad.Instances import System.IO.Unsafe import Data.Char import Data.IORef -------------------------------------- -- copied from http://www.eyrie.org/~zednenem/2004/hsce/ class Functor w => Comonad w where extract :: w a -> a duplicate :: w a -> w (w a) extend :: (w a -> b) -> (w a -> w b) extend f = fmap f . duplicate duplicate = extend id -- | 'fmap' defined in terms of 'extend' liftW :: Comonad w => (a -> b) -> (w a -> w b) liftW f = extend (f . extract) -- | 'extend' with the arguments swapped. Dual to '>>=' for monads. (=>>) :: Comonad w => w a -> (w a -> b) -> w b (=>>) = flip extend -- | Injects a value into the comonad. (.>>) :: Comonad w => w a -> b -> w b w .>> b = extend (\_ -> b) w -- end of copy ------------------------------------- data OIReality = OIReality GetChar [PutChar] Char data GetChar = GetChar Char OIReality data PutChar = PutChar () OIReality constructReality :: Char -> OIReality constructReality c = let r = OIReality (constructGet r) (constructPuts r) c in r constructGet :: OIReality -> GetChar constructGet r = let c = unsafePerformIO $ seq r getChar in GetChar c (constructReality c) constructPut :: OIReality -> Char -> PutChar constructPut r c = let v = unsafePerformIO $ seq r $ putChar c in PutChar v (constructReality c) constructPuts :: OIReality -> [PutChar] constructPuts r = map (constructPut r.chr) [0..255] nextGetCharReality :: OIReality -> OIReality nextGetCharReality (OIReality (GetChar c r) _ _) = r nextPutCharReality :: Char -> OIReality -> OIReality nextPutCharReality c (OIReality _ puts _) = let PutChar v r = puts !! (ord c) in seq v r data OIComonad a = OI (IORef OIReality) a -- extract OI _ a = a instance Functor OIComonad where fmap f (OI ref a) = seq a $ OI (unsafeDuplicateRef ref) (f a) -- too many seq's at the moment instance Comonad OIComonad where duplicate w = fmap (const w) w extract (OI _ a) = a mkOI :: Char -> OIComonad Char mkOI c = OI (unsafePerformIO $ newIORef $ constructReality c) c oiGetChar :: OIComonad a -> Char oiGetChar (OI ref _) = unsafePerformIO $ do { modifyIORef ref nextGetCharReality; OIReality _ _ c <- readIORef ref; return (c) } oiPutChar :: OIComonad Char -> () oiPutChar (OI ref c) = unsafePerformIO $ do { modifyIORef ref (nextPutCharReality c); OIReality _ _ d <- readIORef ref; -- not!? modified without further read return $ seq d ()} unsafeDuplicateRef :: IORef OIReality -> IORef OIReality unsafeDuplicateRef ref = unsafePerformIO $ do { r <- readIORef ref; newIORef r; } oiPutStrLn w = extract $ w =>> oiPutStr .>> '\n' =>> oiPutChar -- space leak if input string is suffiently long -- too many seqs in code oiPutStr w = extract $ oiPutStrS w .>> () oiPutStrS :: OIComonad String -> OIComonad String oiPutStrS w = case (extract w) of [] -> w (c:cs) -> oiPutStrS (w .>> c =>> oiPutChar .>> cs) oiGetLine = "t.b.d. using oiGetChar" -- adapted from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html comain w = extract (w .>> show (a,b) =>> oiPutStr) where a = extract (w .>> () =>> oiGetChar) b = extract (w .>> () =>> oiGetChar) {- Original from http://www.mail-archive.com/haskell-cafe@haskell.org/ msg02408.html -- Bootstrap into the OI comonad main :: IO () main = return $! comain stdOI -- The following are the OI functions which we use. -- stdGetChar :: OI () -> Char -- stdPutStrLn :: OI String -> () comain :: OI a -> () comain w = coeval (w .>> show (a,b) =>> stdPutStrLn) where a = coeval (w .>> () =>> stdGetChar) b = coeval (w .>> () =>> stdGetChar) -}

3 3