- Libraries - Haskell.org

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

Data.IntMap/Set fixes and testsuite for collections.
by Jean-Philippe Bernardy 31 Oct '05

31 Oct '05

Hello folks, Could fptools maintainers apply the attached patch (or give me cvs access, at your convenience ;) which fixes Int* collections? Also, I've written a beginning of a testsuite for collections types. The basic idea is that test-code for multiple modules/types is generated from a signle haskell source by a simple pre-processing phase. This allows to circumvent the current lack of a class framework, and is also somewhat more flexible. Do you think this should be integrated to the ghc testsuite? (Does the preprocessing model fit it?) Cheers, JP.

1 0

Buglet in Data.IntSet.split and Data.IntSet.splitMember, patch included.
by Arthur van Leeuwen 30 Oct '05

30 Oct '05

Hello mailinglist-members, on the #haskell IRC channel Ketil Z. Malde noted that Data.IntSet.split failed on the case > let m = 1000000 in Data.IntSet.split (16*m) $ Data.IntSet.fromList $ map (*m) [17,18,19,30,40] so Bertram Felgenhauer (int-e(a)gmx.de) and I set out to fix that, noting along the way that Data.IntSet.splitMember was broken as well, and that negative numbers were not handled correctly either. The following patch fixes the problems: ----- 8< --- cut here --- >8 ----- --- IntSet.hs 2005-10-27 17:18:15.000000000 +0200 +++ FixedIntSet.hs 2005-10-27 17:59:49.000000000 +0200 @@ -35,7 +35,7 @@ -- (32 or 64). ------------------------------------------------------------------------ ----- -module Data.IntSet ( +module IntSet ( -- * Set type IntSet -- instance Eq,Show @@ -454,8 +454,23 @@ split x t = case t of Bin p m l r - | zero x m -> let (lt,gt) = split x l in (lt,union gt r) - | otherwise -> let (lt,gt) = split x r in (union l lt,gt) + | m < 0 -> if x >= 0 then let (lt,gt) = split' x l in (union r lt, gt) + else let (lt,gt) = split' x r in (lt, union gt l) + | otherwise -> split' x t + Tip y + | x>y -> (t,Nil) + | x<y -> (Nil,t) + | otherwise -> (Nil,Nil) + Nil -> (Nil, Nil) + +split' :: Int -> IntSet -> (IntSet,IntSet) +split' x t + = case t of + Bin p m l r + | match x p m -> if zero x m then let (lt,gt) = split' x l in (lt,union gt r) + else let (lt,gt) = split' x r in (union l lt,gt) + | otherwise -> if x < p then (Nil, t) + else (t, Nil) Tip y | x>y -> (t,Nil) | x<y -> (Nil,t) @@ -468,8 +483,23 @@ splitMember x t = case t of Bin p m l r - | zero x m -> let (lt,found,gt) = splitMember x l in (lt,found,union gt r) - | otherwise -> let (lt,found,gt) = splitMember x r in (union l lt,found,gt) + | m < 0 -> if x >= 0 then let (lt,found,gt) = splitMember' x l in (union r lt, found, gt) + else let (lt,found,gt) = splitMember' x r in (lt, found, union gt l) + | otherwise -> splitMember' x t + Tip y + | x>y -> (t,False,Nil) + | x<y -> (Nil,False,t) + | otherwise -> (Nil,True,Nil) + Nil -> (Nil,False,Nil) + +splitMember' :: Int -> IntSet -> (IntSet,Bool,IntSet) +splitMember' x t + = case t of + Bin p m l r + | match x p m -> if zero x m then let (lt,found,gt) = splitMember x l in (lt,found,union gt r) + else let (lt,found,gt) = splitMember x r in (union l lt,found,gt) + | otherwise -> if x < p then (Nil, False, t) + else (t, False, Nil) Tip y | x>y -> (t,False,Nil) | x<y -> (Nil,False,t) ----- 8< --- ereh tuc --- >8 ----- Hope this helps. :) Doei, Arthur. -- /\ / | arthurvl(a)cs.uu.nl | Work like you don't need the money /__\ / | A friend is someone with whom | Love like you have never been hurt / \/__ | you can dare to be yourself | Dance like there's nobody watching

2 1

cabal installation
by Frederik Eaton 30 Oct '05

30 Oct '05

It would be nice if cabal would unlink destination files before installing over them, rather than just calling "copyFile". It appears that when "copyFile" finds that a destination file already exists, rather than removing it, it tries to open and truncate it, which leads cabal to fail with the following error message when a new version of a running program is installed: *** Exception: bar: copyFile: resource busy (Text file busy) The commonly-used 'install' command does not suffer from this bug. Frederik

2 1

Data.Monoid
by Ross Paterson 27 Oct '05

27 Oct '05

(regurgitating http://www.haskell.org/pipermail/libraries/2005-July/004057.html) I propose to replace the instance instance Monoid (a -> a) where mempty = id mappend = (.) with newtype Endo a = Endo { runEndo :: a -> a } instance Monoid (Endo a) where mempty = Endo id Endo f `mappend` Endo g = Endo (f . g) instance Monoid b => Monoid (a -> b) where mempty _ = mempty mappend f g x = f x `mappend` g x

7 14

RE: [Haskell] Read Instances for Data.Map and Data.Set
by Simon Marlow 27 Oct '05

27 Oct '05

On 21 October 2005 08:43, Johannes Waldmann wrote: > Georg made the point that if a type is an instance of Show, > then it should also be an instance of Read, and read . show == id I rather think that this should be an explicit design requirement for Read/Show instances in the libraries, along with the requirement that the Show instance outputs valid Haskell syntax that can be included in a program (assuming appropriate imports, and possibly an appropriate type signature). Show is not for pretty-printing, it is for serialising. Are there any Show instances that violate these requirements in the base/haskell98 packages currently? Cheers, Simon

7 7