- Haskell-Cafe - Haskell.org

threadDelay granularity
by Ulrik Rasmussen 07 Apr '09

07 Apr '09

Hello. I am writing a simple game in Haskell as an exercise, and in the rendering loop I want to cap the framerate to 60fps. I had planned to do this with GHC.Conc.threadDelay, but looking at it's documentation, I discovered that it can only delay the thread in time spans that are multiples of 20ms: http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Control.Concurrent.… I need a much finer granularity than that, so I wondered if it is possible to either get a higher resolution for threadDelay, or if there is an alternative to threadDelay? I noticed that the SDL library includes the function "delay", which indeed works with a resolution down to one millisecond. However, since I'm using HOpenGL and GLUT, I think it would be a little overkill to depend on SDL just for this :). Thanks, Ulrik Rasmussen

3 5

advice on space efficient data structure with efficient snoc operation
by Manlio Perillo 07 Apr '09

07 Apr '09

Hi. I'm still working on my Netflix Prize project. For a function I wrote, I really need a data structure that is both space efficient (unboxed elements) and with an efficient snoc operation. I have pasted a self contained module with the definition of the function I'm using: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=3453 The movie ratings are loaded from serialized data, and the result is serialized again, using the binary package: transcodeIO :: IO () transcodeIO = do input <- L.hGetContents stdin let output = encodeZ $ transcode $ decodeZ input L.hPut stdout output (here encodeZ and decodeZ are wrappers around Data.Binary.encode and Data.Binary.decode, with support to gzip compression/decompression) This function (transcodeIO, not transcode) takes, on my Core2 CPU T7200 @ 2.00GHz: real 30m8.794s user 29m30.659s sys 0m10.313s 1068 Mb total memory in use The problem here is with snocU, that requires a lot of copying. I rewrote the transcode function so that the input data set is split in N parts: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=3453#a3456 The mapReduce function is the one defined in the Real World Haskell. The new function takes (using only one thread): real 18m48.039s user 18m30.901s sys 0m6.520s 1351 Mb total memory in use The additional required memory is probably caused by unionsWith, that is not strict. The function takes less time, since array copying is optimized. I still use snocU, but on small arrays. GC time is very high: 54.4% Unfortunately I can not test with more then one thread, since I get segmentation faults (probably a bug with uvector packages). I also got two strange errors (but this may be just the result of the segmentation fault, I'm not able to reproduce them): tpp.c:63: __pthread_tpp_change_priority: Assertion `new_prio == -1 || (new_prio >= __sched_fifo_min_prio && new_prio <= __sched_fifo_max_prio)' failed. internal error: removeThreadFromQueue: not found (GHC version 6.8.2 for i386_unknown_linux) Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug Now the question is: what data structure should I use to optimize the transcode function? IMHO there are two solutions: 1) Use a "lazy" array. Something like ByteString.Lazy, and what is available in storablevector package. Using this data structure, I can avoid the use of appendU. 2) Use an "unboxed" list. Something like: http://mdounin.ru/hg/nginx-vendor-current/file/tip/src/core/ngx_list.h That is: a linked list of unboxed arrays, but unlike the lazy array solution, a snoc operation avoid copying if there is space in the current array. I don't know if this is easy/efficient to implement in Haskell. Any other suggestions? Thanks Manlio Perillo

2 2

CFP: JFP Special Issue on Generic Programming
by Matthew Fluet (ICFP Publicity Chair) 07 Apr '09

07 Apr '09

OPEN CALL FOR PAPERS JFP Special Issue on Generic Programming Deadline: 1 October 2009 http://www.comlab.ox.ac.uk/ralf.hinze/JFP/cfp.html Scope ----- Generic programming is about making programs more adaptable by making them more general. Generic programs often embody non-traditional kinds of polymorphism; ordinary programs are obtained from them by suitably instantiating their parameters. In contrast to normal programs, the parameters of a generic program are often quite rich in structure; for example they may be other programs, types or type constructors, classes, concepts, or even programming paradigms. This special issue aims at documenting state-of-the-art research, new developments and directions for future investigation in the broad field of Generic Programming. It is an outgrowth of the series of Workshops on Generic Programming, which started in 1998 and which continues this year with an ICFP affiliated workshop in Edinburgh. Participants of the workshops are invited to submit a suitably revised and expanded version of their paper to the special issue. The call for papers is, however, open. Other contributions are equally welcome and are, indeed, encouraged. All submitted papers will be subjected to the same quality criteria, meeting the standards of the Journal of Functional Programming. The special issue seeks original contributions on all aspects of generic programming including but not limited to o adaptive object-oriented programming, o aspect-oriented programming, o case studies, o concepts (as in the STL/C++ sense), o component-based programming, o datatype-generic programming, o generic programming with dependent types, o meta-programming, o polytypic programming, and o programming with modules. Submission details ------------------ Manuscripts should be unpublished works and not submitted elsewhere. Revised versions of papers published in conference or workshop proceedings that have not appeared in archival journals are eligible for submission. Deadline for submission: 1 October 2009 Notification of acceptance or rejection: 15 January 2010 Revised version due: 15 March 2010 For submission details, please consult http://www.comlab.ox.ac.uk/ralf.hinze/JFP/cfp.html or see the Journal's web page http://journals.cambridge.org/jfp Guest Editor ------------ Ralf Hinze University of Oxford Computing Laboratory Wolfson Building, Parks Road, Oxford OX1 3QD, UK. Telephone: +44 (1865) 610700 Fax: +44 (1865) 283531 Email: ralf.hinze(a)comlab.ox.ac.uk WWW: http://www.comlab.ox.ac.uk/ralf.hinze/ -------------------------------------------------------------------------------

1 0

Re: [Haskell-cafe] threadDelay granularity
by Ulrik Rasmussen 07 Apr '09

07 Apr '09

On Tue, Apr 07, 2009 at 04:01:01PM +0200, Peter Verswyvelen wrote: > Are you on Windows? Because this might be because GHC is not using a high > resolution timer for doing its scheduling, I don't know... No, Ubuntu 8.10. That may very well be, I'm not that much into the details of GHC. I'm thinking about importing a system dependent delay method through the FFI to get more control over the delay interval, but that seems like overkill too. Also, I don't know if that would introduce some nasty problems, again, I'm not that into the inner workings of GHC. For now I'll just allow the application to render as fast as possible, the primary motivation for capping the framerate was to prevent my laptop from getting so hot that I can't have it in my lap :). (I see that I replied to you instead of to the list by accident. I'm CC'ing the message to the list now) /Ulrik > On Tue, Apr 7, 2009 at 3:21 PM, Ulrik Rasmussen <haskell(a)utr.dk> wrote: > > > On Tue, Apr 07, 2009 at 02:53:20PM +0200, Peter Verswyvelen wrote: > > > I think this is an RTS option. > > > > > http://www.haskell.org/ghc/docs/latest/html/users_guide/using-concurrent.ht… > > > > Ahh, I found it now. Seems like the `-C' option didn't work because it > > still limited by the master tick interval. Using `+RTS -V0.001' helps. > > It is a bit inaccurate at that resolution though. > > > > > > > > > > > > > > On Tue, Apr 7, 2009 at 1:41 PM, Ulrik Rasmussen <haskell(a)utr.dk> wrote: > > > > > > > Hello. > > > > > > > > I am writing a simple game in Haskell as an exercise, and in the > > > > rendering loop I want to cap the framerate to 60fps. I had planned to > > do > > > > this with GHC.Conc.threadDelay, but looking at it's documentation, I > > > > discovered that it can only delay the thread in time spans that are > > > > multiples of 20ms: > > > > > > > > > > > > > > http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Control.Concurrent.… > > > > > > > > I need a much finer granularity than that, so I wondered if it is > > > > possible to either get a higher resolution for threadDelay, or if there > > > > is an alternative to threadDelay? > > > > > > > > I noticed that the SDL library includes the function "delay", which > > > > indeed works with a resolution down to one millisecond. However, since > > > > I'm using HOpenGL and GLUT, I think it would be a little overkill to > > > > depend on SDL just for this :). > > > > > > > > > > > > Thanks, > > > > > > > > Ulrik Rasmussen > > > > _______________________________________________ > > > > Haskell-Cafe mailing list > > > > Haskell-Cafe(a)haskell.org > > > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > > >

1 0

System.Process.Posix
by Cristiano Paris 07 Apr '09

07 Apr '09

Is it me or the above package is not included in Hoogle? Cristiano

7 8

tail recursion
by Daryoush Mehrtash 07 Apr '09

07 Apr '09

Is the call to "go" in the following code considered as tail recursion? data DList a = DLNode (DList a) a (DList a) mkDList :: [a] -> DList a mkDList [] = error <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:error> "must have at least one element" mkDList xs = let (first,last <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:last>) = go last <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:last> xs first in first where go :: DList a -> [a] -> DList a -> (DList a, DList a) go prev [] next = (next,prev) go prev (x:xs) next = let this = DLNode prev x rest (rest,last <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:last>) = *go this xs next* in (this,last <http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v:last>) Daryoush

2 1

automatically inserting type declarations
by FFT 07 Apr '09

07 Apr '09

I remember hearing about a Haskell mode for Vim, Emacs, Yi or VisualHaskell that inserts type declarations automatically (it's lazier to just check the type than to write it manually), but I can't remember any details. What editor mode / IDE was it? What do most people use with GHC on Linux? I'm more used to Vim than to Emacs. Yi sounds like something I might like. Is it stable enough to solve more problems than it would create? (I hate buggy and broken stuff)

3 2

replicateM should be called mreplicate?
by Sjoerd Visscher 07 Apr '09

07 Apr '09

Considering these naming conventions: http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Monad.html#3 • A postfix 'M' always stands for a function in the Kleisli category: The monad type constructor m is added to function results (modulo currying) and nowhere else. So, for example, filter :: (a -> Bool) -> [a] -> [a] filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] • A postfix '_' changes the result type from (m a) to (m ()). Thus, for example: sequence :: Monad m => [m a] -> m [a] sequence_ :: Monad m => [m a] -> m () • A prefix 'm' generalizes an existing function to a monadic form. Thus, for example: sum :: Num a => [a] -> a msum :: MonadPlus m => [m a] -> m a replicateM has the following type: replicateM :: Monad m => Int -> m a -> m [a] Am I missing something or should this have been called mreplicate? greetings, -- Sjoerd Visscher sjoerd(a)w3future.com

4 4

Infix tuple comma query (,)
by Paul Keir 07 Apr '09

07 Apr '09

module Main where data (:%^&) a b = a :%^& b deriving (Show) main = do print $ 18 :%^& (Just 99) print $ (,) 9 10 print $ 9 , 10 The last line in the code above causes a compile error. Why does infix use of the comma (tuple constructor?) function fail without brackets? Thanks, Paul

4 3

Lazy vs correct IO [Was: A round of golf]
by oleg＠okmij.org 07 Apr '09

07 Apr '09

Lennart Augustsson wrote > main = do > name:_ <- getArgs > file <- readFile name > print $ length $ lines file Given the stance against top-level mutable variables, I have not expected to see this Lazy IO code. After all, what could be more against the spirit of Haskell than a `pure' function with observable side effects. With Lazy IO, one indeed has to choose between correctness and performance. The appearance of such code is especially strange after the evidence of deadlocks with Lazy IO, presented on this list less than a month ago. Let alone unpredictable resource usage and reliance on finalizers to close files (forgetting that GHC does not guarantee that finalizers will be run at all). Is there an alternative? -- Counting the lines in a file import IterateeM count_nl = liftI $ IE_cont (step 0) where step acc (Chunk str) = liftI $ IE_cont (step $! acc + count str) step acc stream = liftI $ IE_done acc stream count [] = 0 count ('\n':str) = succ $! count str count (_:str) = count str main = do name:_ <- getArgs IE_done counter _ <- unIM $ enum_file name >. enum_eof ==<< count_nl print counter The function count_nl could have been in the library, but I'm a minimalist. It is written in a declarative rather than imperative style, and one easily sees what it does. The above code as well as the IterateeM library is Haskell98. It does not use any unsafe Haskell functions whatsoever. time wc -l /usr/share/dict/words 235882 /usr/share/dict/words real 0m0.024s user 0m0.022s sys 0m0.000s time ~/Docs/papers/DEFUN08/Wc /usr/share/dict/words 235882 real 0m0.141s user 0m0.126s sys 0m0.008s To compare with lazy IO, the code using readFile gives time ~/Docs/papers/DEFUN08/Wc /usr/share/dict/words 235882 real 0m0.297s user 0m0.262s sys 0m0.023s So, choosing correctness does not mean losing in performance; in fact, one may even gain. Can enumerators compose? Well, we already seen the example above (enum_file name >. enum_eof) where the operation (>.) e1 >. e2 = (==<<) e2 . e1 is a flipped composition if monadic bind were considered a flipped application. Here is a more interesting example: count words in all the files whose names are given on the command line. There may be many files given, thousands of them. -- Count the stream. Again, could have been in the library stream_count :: Monad m => IterateeGM el m Int stream_count = liftI $ IE_cont (step 0) where step acc (Chunk []) = liftI $ IE_cont (step acc) step acc (Chunk [_]) = liftI $ IE_cont (step $! succ acc) step acc (Chunk ls) = liftI $ IE_cont (step $! acc + length ls) step acc stream = liftI $ IE_done acc stream main = do names <- getArgs let enumerators = foldr (\name -> (enum_file name >.)) enum_eof names IE_done (IE_done counter _) _ <- unIM $ enumerators ==<< enum_words stream_count print counter We notice that the composition of enumerators corresponds to the `concatenation' of their sources. Declaratively, the meaning of the above code is: -- all the given files are concatenated -- the resulting stream of characters is converted to a stream of words -- the stream of words is counted. Operationally, the code does not open more than one file at a time. More importantly, the code *never* reads more than 4096 characters at a time. A block of the file is read, split into words, counted, and only then another chunk is read. After one file is done, it is closed, and another file is processed. One can see that only one file is being opened at a time by enabling traces. The processing is fully incremental. /usr/local/share/doc/ghc6> find . -name \*.html -print | time xargs ~/Docs/papers/DEFUN08/Wc 3043421 16.99 real 15.83 user 0.71 sys BTW, the program has counted words in 1169 files. It is interesting to compare the above main function with the corresponding lazy IO: main'' = do names <- getArgs files <- mapM readFile names print $ length $ words (concat files) The number of lines is comparable. The execution is not. If we try to run the lazy IO code, we get: /usr/local/share/doc/ghc6> find . -name \*.html -print | time xargs ~/Docs/papers/DEFUN08/Wc Wc: ./libraries/Win32/Graphics-Win32-GDI-Path.html: openFile: resource exhausted (Too many open files)

9 12