- Haskell-Cafe - Haskell.org

ANNOUNCE: system-time-monotonic-0.1
by Joey Adams 06 Aug '12

06 Aug '12

system-time-monotonic [1] provides access to the system's monotonic clock. Usage looks like this: * Use 'newClock' to create a new monotonic clock * Use 'clockGetTime' to see how much time has elapsed since the clock was created. This package currently supports Linux and Windows. It might also work on BSD, but I haven't tested it there. Mac OS X support is currently not implemented, but patches are welcome. GHC uses mach_absolute_time and mach_timebase_info; see ticket #5865 [2]. I also added a handy utility function 'delay', a variant of threadDelay taking a DiffTime instead of Int microseconds. Thus: delay 1.5 Waits 1.5 seconds. Note that since 'delay' simply calls 'threadDelay' in a loop, it is disrupted by system clock changes (again, see ticket #5865). [1]: http://hackage.haskell.org/package/system-time-monotonic [2]: http://hackage.haskell.org/trac/ghc/ticket/5865 --- The rest of this email describes various hurdles involved in implementing this package, and how they were addressed. ## GetTickCount The most obvious one is that GetTickCount has a short wraparound (49.7 days). Two ways to address this: * Don't use GetTickCount; use QueryPerformanceCounter (or similar) instead. This is currently how it's done in GHC HEAD. * Use GetTickCount, but avoid comparing times that are far apart by tracking the total difference each time we look at the clock. I took the second approach, because I found out that QueryPerformanceCounter is actually less accurate in the long run than GetTickCount. In particular, QueryPerformanceCounter stops ticking (or maybe ticks slower, I forget) when the computer is asleep. Here's the trick I use to work around GetTickCount's wraparound (pseudocode): st1 :: Word32 t1 :: DiffTime newClock: st1 := GetTickCount() t1 := 0 clockGetTime: st2 := GetTickCount() t2 := t1 + (Int32)(st2 - st1 modulo 2^32) st1 := st2 t1 := t2 return t2 This workaround only works if clockGetTime is called at least once every 24.8 days. It's important that st2 - st1 be done modulo 2^32, to compensate for wraparound. However, the result should be converted to a signed 32-bit integer, in case st2 was recorded earlier than st1 (which can easily happen in a concurrent context). In particular, here's what you should *not* do (which GHC currently does, when QueryPerformanceCounter is not available): st1 = (bigger_type) GetTickCount(); ... st2 = (bigger_type) GetTickCount(); return (st2 - st1) This will return a bogus value if a wraparound occurred between st1 and st2. system-time-monotonic tests, at runtime, if GetTickCount64 is available. If so, it uses it. Otherwise, it falls back to GetTickCount. Here's the code I used to do the run-time system call lookup: /* cbits/dll.c */ typedef ULONGLONG (WINAPI *GetTickCount64_t)(void); GetTickCount64_t system_time_monotonic_load_GetTickCount64(void) { return (GetTickCount64_t) GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")), "GetTickCount64"); } -- System/Time/Monotonic/Direct.hsc type C_GetTickCount64 = IO #{type ULONGLONG} foreign import ccall system_time_monotonic_load_GetTickCount64 :: IO (FunPtr C_GetTickCount64) foreign import stdcall "dynamic" mkGetTickCount64 :: FunPtr C_GetTickCount64 -> C_GetTickCount64 Did I do this right? In particular: * Can I assume the kernel32.dll HMODULE won't be pulled out from under me? * Is `foreign import stdcall "dynamic"` the right incantation for using a pointer to a WINAPI function? ## CLOCK_MONOTONIC is not actually monotonic on Linux CLOCK_MONOTONIC is subject to NTP adjustments. Worse, CLOCK_MONOTONIC stops when the computer is put to sleep (unlike GetTickCount, which does the right thing). Two clocks were introduced very recently in Linux: * CLOCK_MONOTONIC_RAW * CLOCK_BOOTTIME I'd like to support CLOCK_BOOTTIME at some point. I'm not sure if it's subject to NTP adjustments or not, since the announcement [3] says: CLOCK_BOOTTIME is identical to CLOCK_MONOTONIC, except it also includes any time spent in suspend (as currently measured by read_persistent_clock()). This allows applications to get a suspend aware monotonic clock. One idea would be to hard-code the clockid_t of CLOCK_BOOTTIME and CLOCK_MONOTONIC_RAW, and try calling clock_gettime with each of these. If one of these succeeds, use it. Otherwise, fall back to CLOCK_MONOTONIC. Thus, the compiled binary can test, at runtime, if a new enough kernel is available. For now, system-time-monotonic simply uses CLOCK_MONOTONIC. [3]: http://lwn.net/Articles/428176/

1 0

Re: [Haskell-cafe] CRIP: the Curiously Reoccuring Instance Pattern
by oleg＠okmij.org 06 Aug '12

06 Aug '12

> I think instead you should have: > - abandoned FunDeps > - embraced Overlapping more! Well, using TypeCast to emulate all FunDeps was demonstrated three years later after HList (or even sooner -- I don't remember when exactly the code was written): http://okmij.org/ftp/Haskell/TypeClass.html#Haskell1 We demonstrate that removing from Haskell the ability to define typeclasses leads to no loss of expressivity. Haskell restricted to a single, pre-defined typeclass with only one method can express all of Haskell98 typeclass programming idioms including constructor classes, as well as multi-parameter type classes and even some functional dependencies. The addition of TypeCast as a pre-defined constraint gives us all functional dependencies, bounded existentials, and even associated data types. Besides clarifying the role of typeclasses as method bundles, we propose a simpler model of overloading resolution than that of Hall et al. > So here's my conjecture: > 1. We don't need FunDeps, except to define TypeCast. > (And GHC now has equality constraints, which are prettier.) > 2. Without FunDeps, overlapping works fine. > ... I agree on point 1 but not on point 2. The example of incoherence described in Sec `7.6.3.4. Overlapping instances' of the GHC User Guide has nothing to do with functional dependencies.

2 2

Knight Capital debacle and software correctness
by Vasili I. Galchin 05 Aug '12

05 Aug '12

Hello Haskell Group, I work in mainstream software industry. I am going to make an assumption .... except for Jane Street Capital all/most "Wall Street" software is written in an imperative language. Assuming this why is Wall Street not awaken to the dangers. As I write, Knight Capital may not survive the weekend. Regards, Vasili

9 12

Talk about Haskell at Ubucon in Berlin
by Robert Clausecker 05 Aug '12

05 Aug '12

Hello Haskellers! I'm going to give a talk on Haskell at Ubucon 2012 in Berlin (In German). I want to give an introduction about the concept of functional programming and the special language concepts of Haskell. Any ideas what to focus on? Yours, Robert Clausecker

2 1

Sorting efficiency
by David Feuer 05 Aug '12

05 Aug '12

I'm writing a toy program (for a SPOJ problem--see https://www.spoj.pl/problems/ABCDEF/ ) and the profiler says my performance problem is that I'm spending too much time sorting. I'm using Data.List.sort on [Int32] (it's a 32-bit architecture). Others, using other languages, have managed to solve the problem within the time limit using the same approach I've taken (I believe), but mine is taking too long. Any suggestions? Do I need to do something insane like sorting in an STUArray? David Feuer

3 5

do vs. pattern matching
by Matthew 04 Aug '12

04 Aug '12

I'm a somewhat experienced coder but I am relatively new to Haskell. I've got a question about whether a usage of do notation is idiomatic, or whether it's better to use pattern matching. I've got two functions which take an input and return Maybe SomeType. If either returns Nothing, I also want to return Nothing. If they both return something, then I'll return something unrelated. With do notation, I can write something like this: do foo <- callFoo x bar <- callBar x return (baz) Alternatively, there's a straightforward pattern match. After binding foo, bar in a couple of where clauses: case (foo,bar) of (Just x, Just y) -> baz _ -> Nothing So which approach is more idiomatic, do you think? Thanks, - Matthew

5 5

Deprecating packages on Hackage
by Andrey Chudnov 04 Aug '12

04 Aug '12

Hello. What are the best practices in deprecating packages on Hackage? I've seen packages marked "DEPRECATED" in the synopsis field on Hackage, and one could add GHC "deprecated" pragmas for every module, but is that the best one can do? Thank you in advance, Andrey Chudnov

2 1

cabal-dev + haskell mode (vim)
by Benjamin Edwards 04 Aug '12

04 Aug '12

Hello Café, I am struggling to get ctags and / or haskell mode to work with cabal-dev. This is quite annoying. Has anyone worked around this? Ben

2 2

Why is the the transpose function in Data.List more complicated?
by KC 03 Aug '12

03 Aug '12

Transpose in Data.List is the following: transpose :: [[a]] -> [[a]] transpose [] = [] transpose ([] : xss) = transpose xss transpose ((x:xs) : xss) = (x : [h | (h:_) <- xss]) : transpose (xs : [ t | (_:t) <- xss]) Yet this seems to work. transp :: [[b]] -> [[b]] transp ([]:_) = [] transp rows = map head rows : transp (map tail rows) Why is the the transpose function in Data.List more complicated? -- -- Regards, KC

2 1

Re: [Haskell-cafe] What Haskell Records Need
by Andrew Butterfield 03 Aug '12

03 Aug '12

On 2 Aug 2012, at 09:25, Erik Hesselink wrote: > Isn't this exactly the problem solved by all the lens packages? > Current popular ones are fclabels [0] and data-lens [1]. > > [0] http://hackage.haskell.org/package/fclabels > [1] http://hackage.haskell.org/package/data-lens Not sure what all of these do, but I have a simple solution I use in my work: > >> Take the following types from a contrived >> example. >> >>> type Salary = Integer >>> >>> data Job = Job >>> { title :: String >>> , salary :: Salary >>> } Rather than setTitle :: String -> Job -> Job we lift the first argument and define setfTitle :: (String -> String) -> Job -> Job setfTitle f jobrec = jobrec{ title = f $ title jobrec } then setTitle = setfTitle . const This is all just boilerplate, so we continue setfSalary :: (Salary -> Salary) -> Job -> Job setfSalary f jobrec = jobrec{ salary = f $ salary jobrec } >>> >>> data Person = Person >>> { name :: String >>> , job :: Job >>> } >> setfName :: (String -> String) -> Person -> Person setfName f prec = prec{ name = f $ name prec } setfJob :: (Job -> Job) -> Person -> Person setfJob f prec = prec{ job = f $ job prec } Now we can use function composition to do two levels setfTitleInPerson :: (String -> String) -> Person -> Person setfTitleInPerson = setfJob . setfTitle setTitleInPerson :: String -> Person -> Person setTitleInPerson = setfTitleInPerson . const Simple function composition works to put these together... I was frustrated by this problem a while back, and decided to approach it formally (I write literate Haskell/LateX documents), and went to work, doing the math with the intention of writing a suitable combinator, until I discovered I didn't need one .... lifting from X -> R -> R to (X -> X) -> R -> R gave me all I needed... >> Since I've used record syntax, I get >> getter/accessor functions (title, salary, >> name, job) for free. Now suppose I want to >> create an aggregate getter function: return >> the salary of a given person. Piece of cake, >> it's just function composition >> >>> getSalary :: Person -> Salary >>> getSalary = salary . job >> >> Done! Now suppose I want to write a >> setter/mutator function for the same nested >> field >> >>> setSalaryMessy :: Salary -> Person -> Person >>> setSalaryMessy newSalary person = >>> person { >>> job = (job person) { >>> salary = newSalary >>> } >>> } >> >> Ouch! And that's not even very deeply nested. >> Imagine 4 or 5 levels deep. It really makes >> Haskell feel clunky next to `a.b.c.d = val` >> that you see in other languages. Of course >> immutability means that the semantics of >> Haskell are quite different (we're creating >> new values here, not updating old ones) but >> it's still common to model change using these >> kinds of updates. >> >> What if along with the free getters that >> the compiler generates when we use record >> syntax, we also got semantic editor >> combinator (SEC) functions[0] that could be >> used as follows? >> >>> setSalary newSalary = job' $ salary' (const newSalary) >>> >>> giveRaise amount = job' $ salary' (+amount) >>> >>> givePercentRaise percent = job' $ salary' (*(1+percent)) >> >> For each field x, the compiler generates a >> function x' (the tic is mnemonic for change). >> These little functions aren't hard to write, >> but they're classic boilerplate. >> >>> job' :: (Job -> Job) -> Person -> Person >>> job' f person = person {job = f $ job person} >> >>> salary' :: (Salary -> Salary) -> Job -> Job >>> salary' f job = job { salary = f $ salary job} >> >> These type of utility functions are a dream >> when working with any reference type or >> State Monad. >> >>> modify $ givePercentRaise 0.25 >> >> The compiler could also generate polymorphic >> SEC functions for polymorphic fields. >> Further, the compiler could disallow using >> old-style update syntax for fields whose SEC >> update function is not in scope, giving us >> fine-grained control over access and update. >> On the other hand we currently have to create >> new functions to achieve this (exporting the >> getter means exporting the ability to update >> as well, currently). >> >> Of course this doesn't address the >> namespacing issues with records, but it is >> likely nicely orthogonal to other proposals >> which do. >> >> Also note that there's a package on hackage [1] >> that will generate SEC functions using TH. >> It's nice, but I prefer the style of field >> names used above for updaters (field' vs >> editField). >> >> Let me know what you think. I'll write up an >> official proposal if there's a bit of >> general interest around this. >> >> Thanks for reading, >> >> --Jonathan >> >> [0] - http://conal.net/blog/posts/semantic-editor-combinators >> [1] - >> http://hackage.haskell.org/packages/archive/sec/0.0.1/doc/html/Data-Semanti… >> >> >> >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group Director of Teaching and Learning - Undergraduate, School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ -------------------------------------------------------------------- -------------------------------------------------------------------- Andrew Butterfield Tel: +353-1-896-2517 Fax: +353-1-677-2204 Lero@TCD, Head of Foundations & Methods Research Group Director of Teaching and Learning - Undergraduate, School of Computer Science and Statistics, Room G.39, O'Reilly Institute, Trinity College, University of Dublin http://www.scss.tcd.ie/Andrew.Butterfield/ --------------------------------------------------------------------

6 8