November 2005 - Libraries

Data.Map and Haddock documentation
by Jesper Louis Andersen 06 Nov '05

06 Nov '05

Hi Haskell hackers! The library documentation I sit with for Data.Map misses some explanation: insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a O(log n). Insert with a combining function. Ok, we now have to guess about the exact semantics of this function. We expect that if k is not existing in the Map, the (k,a) pair is going to be inserted. If k is existing, the combining function will be called. When the combining function is being called, we only have 50% chance of guessing the semantics. You could, with some correctness, postulate the documentation was 50% correct. The following test is from hugs-2005Mar: Data.Map> let a = insert 0 1 empty in insertWith (curry fst) 0 2 a {0:=2} Data.Map> let a = insert 0 1 empty in insertWith (curry snd) 0 2 a {0:=1} Aha!, so now we are able to make the documentation for the function better: > -- | /O(log n)/. Insert with a combining function. `insertWith f key > -- value mp` will insert the pair (key, value) into mp if key does > -- not exist in the map. If the key does exist, the function will > -- insert the value from the function call `f new_value old_value`. Feel free to make my crude english better and to supply the same documentation for insertWithKey. If this has already been done, ignore my message ;)

1 0

Re: Performance of functional queues
by Okasaki, C. DR EECS 04 Nov '05

04 Nov '05

You might want to take a look at Graeme Moss's dissertation, which was about a system for benchmarking functional data structures, including queues. -- Chris

2 1

Performance of functional queues
by Einar Karttunen 03 Nov '05

03 Nov '05

Hello I benchmarked the various functional queue implementations including simple batched queues (data Q = Q [a] [a]), Data.Queue and Data.Sequence. The end result was that the simple batched queues are fast and toList of Data.Sequence is very slow. For most applications Data.Sequence is faster than Data.Queue, but slower than the batched queues, but the differences are not huge. Of course it offers other functionality which the other queues don't provide. For pics of the results and the code look at http://www.cs.helsinki.fi/u/ekarttun/haskell/sequence-performance/ - Einar Karttunen

3 3

RE: RFC: Time Library 0.2
by Simon Marlow 03 Nov '05

03 Nov '05

On 03 November 2005 04:24, John Meacham wrote: > On Wed, Nov 02, 2005 at 08:19:56PM -0800, John Meacham wrote: >> On Wed, Nov 02, 2005 at 11:43:16AM +0100, Sebastian Sylvan wrote: >>> On 11/2/05, Ashley Yakeley <ashley(a)semantic.org> wrote: >>>> In article >>>> <3d96ac180511010738h1e3c5206vba7318e724e3cb48(a)mail.gmail.com>, >>>> Sebastian Sylvan <sebastian.sylvan(a)gmail.com> wrote: >>>> >>>>> Which is why I requested a separate function which just gives the >>>>> picosecs since startup (or something). >>>> >>>> That's what getCPUTime in System.CPUTime does. >>> >>> No it isnt'. getCPUTime gives the.. uh.. CPU-time :-) >>> >>> If all my program does is sleep, waiting for other programs to >>> release some resource, then getCPUTime will return zero. >>> >>> What I'm requesting is a function which gives the number of >>> wall-clock picos seconds since startup, which could be used for all >>> sorts of real-time simulations etc. >> >> is this true? I always thought that is what getCPUTime was supposed >> to mean, a reading from the tsc on x86 machines for instance and >> distinct from the unix notion of 'cputime'. > > hmm.. looking at the report, you are correct. hmm.. perhaps we need > another function to read the tsc-equivalent on various CPUs. Reading the TSC doesn't work well on SMP machines, because the individual CPU counters probably aren't synchronised. As it happens, I've just been struggling with exactly this - I need to get the per-thread CPU time, and the implementation in glibc (clock_gettime()) uses the TSC, which gives bogus results. I hope they'll fix this at some point. Cheers, Simon

1 0

RFC: Time Library 0.2
by Ashley Yakeley 03 Nov '05

03 Nov '05

Just in time for HCAR... Please take a look at my second attempt at writing a replacement for the standard time library. http://semantic.org/TimeLib/ Take a look at the Haddock documentation: http://semantic.org/TimeLib/doc/html/ Download the source: http://semantic.org/TimeLib/TimeLib-0.2.tar.gz Or keep up-to-date: darcs get http://semantic.org/TimeLib/TimeLib/ It needs GHC 6.4.1. (I haven't tested with 6.4.) Just run "make" to build the library, tests and documentation. There's also a cabal file (as a completely separate build process), but I've been having trouble with that on Mac OS X. I'm particularly interested in comments from people who try to write little applications for it. What did you have trouble with? What made no sense? Also have a look at some use-cases, which get compiled as part of the package tests: http://semantic.org/TimeLib/TimeLib/test/UseCases.lhs Major changes since 0.1: * Moved to Data.Time, since the actual "System" part (getting the current time and time-zone) is relatively small. * Big simplification of types. Now tuples are used for calendar data (such as (year,month,day) for the Gregorian calendar), and the confusing DayEncoding class has been dropped. Some points: 1. There is no leap second table provided, though there is a type (LeapSecondTable) for such things. Any software compiled with a fixed table would soon become out of date. 2. There is no table of time-zones provided, since these also change. However, if there's a good way of getting this from the TZ database on the machine, I'll add that. It is actually possible to get the local time-zone for any given time, indeed one of the test programs finds your local summertime transitions. The Timezone type includes name, minutes of offset, and a "summertime" flag. 3. The TimeLocale type comes from the already existing System.Locale. 4. It's not possible to expunge POSIX time. Why? Because it's the only way to do sensible arithmetic on UTC times without knowing the leap second table and without worrying about one-second offsets. 5. I include Data.Fixed which provides a fixed-point arithmetic type (wrapper around Integer). It probably should be in a separate package. It allows dealing with seconds as a single thing, rather than as an integer/picoseconds pair. 6. I don't have any text-parsing functionality for times. This is a fair amount of work, so it would be good to know sensible requirements. 7. Time as measured by the CPU since system startup remains in System.CPUTime, which TimeLib does not intend to replace. -- Ashley Yakeley, Seattle WA

6 11

RE: RFC: Time Library 0.2
by Simon Marlow 02 Nov '05

02 Nov '05

On 02 November 2005 07:08, Ashley Yakeley wrote: > In article <slrndmetn6.i4l.jgoerzen(a)erwin.complete.org>, > John Goerzen <jgoerzen(a)complete.org> wrote: > >> There are just a few functions that a lot of people need, and they >> are: > > These can all be done easily if you use UTCTime for epoch time. > [ good examples snipped ] This discussion raises a good point, I think: the library is carefully designed, but perhaps lacks something in accessibility. Many of the questions that John raised occurred to me when I browsed the docs, in general it isn't obvious how to do the easy things. You demonstrated that the easy things are in fact easy to do, so it's just a problem of presentation. That can be addressed in two ways: - change names to be more friendly. If UTCTime is going to be the "linear" time scale that everyone uses to do simple calculations, then we should call it something like ClockTime or Epoch (better suggestions welcome), noting in the documentation that it is UTC. It should be the first thing that you find when you browse the docs, too. - write up some docs that describe how to do the simple things. (I'm not necessarily expecting Ashley to do this, I hope someone else will volunteer). Cheers, Simon >> (C functions in parens) >> >> * Convert epoch time to a printable string (ctime) > > ctime :: UTCTime -> String > ctime t = show (utcToLocalTime utc t) > > TODO: add a "Show UTCTime" instance, allowing > > ctime = show > >> * Convert epoch time to something like struct tm (localtime/gmtime) > > gmtime :: UTCTime -> ZonedTime > gmtime = zonedTimeFromUTC utc > > TODO: rename zonedTimeFromUTC to utcToZonedTime. > > Depending on exactly what you want it to do, localtime is one of > these: > > -- use time zone at given time > localtime :: UTCTime -> IO ZonedTime > localtime = utcToLocalZonedTime > > -- use time zone at current time > localtime' :: UTCTime -> IO ZonedTime > localtime' t = do > zone <- getCurrentTimeZone > zonedTimeFromUTC zone t > > The current time zone is different at different times according to the > summertime rule. It's possible to find out what it is for a given > time. > >> * Convert a struct tm to epoch time (mktime) > > mktime :: ZonedTime -> UTCTime > mktime = ztUTC > > TODO: rename ztUTC to something more sensible. > >> * Convert a struct tm to a printable string (asctime) > > asctime = ZonedTime -> String > asctime = show > >> * Get the current time in epoch seconds (time) > > time :: IO UTCTime > time = getCurrentTime > >> For many programmers, myself included, the Unix epoch is the most >> common, pervasive, and useful way to work with time. Calculations >> are simple (no need for various TimeDiff sort of things -- just add >> on x number of seconds), and it is used *everywhere* in the OS, >> databases, etc. Something that is based on that, such as the C API, >> is a plus, IMHO. > > Simon Marlow seems to be generally of the opinion that POSIX time is > evil and should be expunged (because it's a broken representation of > UTC). I do however have a few POSIX functions exposed. > > My UTCTime is more or less the simplest correct representation > (consisting of a day count and a time offset). I think UTCTime should > remain the main representation of UTC time, but perhaps there should > be another module (Data.Time.POSIX) for people who need to muck about > with seconds since epoch. It would have POSIXTime with arithmetic, > conversion to UTCTime, and getting the current time. > > Thanks...

2 1