February 2010 - Haskell-Cafe

Linguistic hair-splitting
by Andrew Coppin 16 Feb '10

16 Feb '10

Here's one for you to ponder. 7 is a number. 7 is an integer, and integers are numbers. 7 is not a field. 7 is an element of [at least one] field, but 7 itself is not a field. 7 is not a group. 7 is a member of the set of integers, but the set of integers is not a group either. The set of integers form a group when taken together with the addition operator. (And, actually, forms another, different, group when taken with the multiplication operator.) Now, here's the question: Is is correct to say that [3, 5, 8] is a monad? Is it correct to say that lists are a monad? Or would it be more correct to say that lists "form" a monad?

14 17

Microsoft Research PhD Scholarship, University of Leeds
by David Duke 16 Feb '10

16 Feb '10

I'm pleased to announce a PhD Scholarship within the Visualization and VR group at Leeds, generously funded by Microsoft Research. We are seeking a student to investigate how visualization techniques can be further developed to understand and improve the performance of parallel Haskell programs running on multi-core CPUs. Closing date for applications is 22 March 2010. Could you please pass on this call to anyone who might be interested in applying. Further details are included below, and are also available on the web, at http://www.engineering.leeds.ac.uk/pg/studentships/duke.shtml thanks, David Duke PROJECT TITLE: "Visualizing Performance for Multicore Haskell" SUPERVISION: Dr. David Duke, School of Computing, University of Leeds, UK MRL CO-SUPERVISION: Dr. Satnam Singh Prof. Simon Peyton Jones Dr. Simon Marlow Microsoft Research Laboratory, Cambridge, UK OUTLINE: The GHC Haskell compiler now provides high-level abstractions that allow the programmer to benefit from multi-core CPUs. These abstractions support implicit parallelism - the programmer can indicate expressions that could usefully be evaluated in parallel, but is freed from concerns about when parallel evaluation takes place. However, it now becomes more difficult to isolate and resolve performance issues. Visualization of run-time behaviour can help. The Haskell community already have the benefit of a tool, ThreadScope, developed at Microsoft Research Cambridge (research.microsoft.com/en-us/labs/ Cambridge/) that provides insight into resource utilisation. However ThreadScope, like other performance visualization tools, presents the programmer with a view of low-level resources that differs from the level of abstraction at which Haskell programmers are encouraged to work. This studentship will investigate visualization techniques for linking high-level program abstractions with low-level runtime performance data. It should allow Haskell programmers to exploit parallelism more effectively. The student will join the Visualization and VR group at Leeds (www.comp.leeds.ac.uk/vvr) . Work on the PhD will involve: understanding how information about run-time resources can be extracted and visualized, and how programmers use these representations to reason about design and implementation choices; building or extending visualization tools; conducting user evaluations; modify components of the GHC compiler and runtime system. Work will be undertaken with support from the GHC/ ThreadScope team at Microsoft Research (Satnam Singh, Simon Peyton Jones, and Simon Marlow). At the discretion of Microsoft Research, the student may also be offered an internship at MRL Cambridge. FUNDING: The Scholarship provides a bursary of £20,000 per year for three years, covering fees and maintenance. A further £3000 per annum has been reserved for travel expenses to attend conferences and visits to Microsoft Research in Cambridge. Applicants from outside of the EU should note that higher student fees (currently £13,300) will necessarily reduce the amount available for maintenance. Home/EU fees stand at £3,390 currently. Microsoft Research will provide the successful candidate with a laptop equipped with a suite of software. ENTRY REQUIREMENTS: Applicants must hold a First-Class BSc (Hon) degree in Computer Science or equivalent. It is essential that applicants have excellent knowledge of functional programming and significant practical experience writing software in Haskell, Clean, or ML. Experience with GUI programming and/or information visualization is highly desirable. Knowledge of programming technologies, in particular compilers and implementation techniques for functional languages is also desirable. The position is open to students of all nationalities. SCHOOL OF COMPUTING, LEEDS: The School of Computing (www.comp.leeds.ac.uk) is among the 10 best Computing departments in the UK according to the 2008 Research Assessment Exercise (RAE). An impressive 80% of staff is rated internationally excellent or world leading. This clearly confirms the School’s position as one of the leading computing departments in the UK and a leader in the field internationally. APPLICATION PROCEDURE: Formal applications for research degree study must be made either online through the University website, or on the University’s application form. Detailed information of how to apply on line can be found at: www.leeds.ac.uk/students/apply_research.htm The paper application form is available at: www.leeds.ac.uk/rds/Admissions/Admis_home.htm Please return the completed application form to: Research Degrees & Scholarships Office, University of Leeds, LS2 9JT. Please provide all the documents required as soon as possible, either included with your paper application or sent directly to the School of Computing secretary (rsadmit(a)comp.leeds.ac.uk) if you apply online. Scanned copies are acceptable for a conditional offer; however you will need to provide originals or certified copies at registration. These will include your degree certificate(s), transcripts of marks achieved in previous degrees, plus evidence of English language qualifications if your first language is not English and you do not hold a degree from an English-speaking country. Please note, if you intend to send academic references we can only accept them if they are on official letter headed paper and contain an original signature and stamp; they must arrive in sealed envelopes. Alternatively, the School will contact your named academic referees directly. CLOSING DATE: Applications must be received by 22 March 2010. ACADEMIC CONTACT: For questions about the research topic, please contact Dr. David Duke, University of Leeds; Tel: +44 113 343 6800; Email: D.J.Duke(a)leeds.ac.uk; Web: www.comp.leeds.ac.uk/djd/

1 0

on finding abstractions ...
by Günther Schmidt 16 Feb '10

16 Feb '10

Hello, I've got a problem, in short my haskell code sucks. While it does work and I do manage to use higher-orderish aspects quite extensively to make my code more concise it still is nowhere abstract, always concrete and thus always with lots of boilerplate. Oh I have gotten better compared to when I started but on the abstraction slope I'm still stuck. So fellows, what is the next stop on my road to enlightenment? I really think I need best to start from scratch. I think I'm sufficiently familiar now with most of Haskell's technicalities but how do I climb the ladder of abstraction? Günther

7 7

Interpreting profiling results
by Patrick LeBoutillier 16 Feb '10

16 Feb '10

Hi, This question didn't get any replies on the beginners list, I thought I'd try it here... I've written (and improved using other solutions I've found on the net) a simple sudoku solver which I'm trying to profile. Here is the code: import Array import List (transpose, nub, (\\)) import Data.List data Sudoku = Sudoku { unit :: Int, cells :: Array (Int, Int) Int, holes :: [(Int, Int)] } cell :: Sudoku -> (Int, Int) -> Int cell s i = (cells s) ! i instance Read Sudoku where readsPrec _ s = [(Sudoku unit cells holes, "")] where unit = length . words . head . lines $ s cells = listArray ((1, 1), (unit, unit)) (map read . words $ s) holes = [ c | c <- indices cells, (cells ! c) == 0] instance Show Sudoku where show s = unlines [unwords [show $ cell s (x,y) | x <- [1 .. unit s]] | y <- [1 .. unit s]] genNums :: Sudoku -> (Int, Int) -> [Int] genNums s c@(i,j) = ([1 .. u] \\) . nub $ used where used = (row s u i j) ++ (col s u i j) ++ (square s sq u i j) u = unit s sq = truncate . sqrt . fromIntegral $ u row s u i j = [cell s (i, y) | y <- [1 .. u]] col s u i j = [cell s (x, j) | x <- [1 .. u]] square s sq u i j = [cell s (x, y) | y <- [1 .. u], x <- [1 .. u], f x i, f y j] where f a b = div (a-1) sq == div (b-1) sq solve :: Sudoku -> [Sudoku] solve s = case holes s of [] -> [s] (h:hs) -> do n <- genNums s h let s' = Sudoku (unit s) ((cells s) // [(h, n)]) hs solve s' main = print . head . solve . read =<< getContents When I compile as such: $ ghc -O2 --make Sudoku.hs -prof -auto-all -caf-all -fforce-recomp and run it on the following puzzle: 0 2 3 4 3 4 1 0 2 1 4 0 0 3 2 1 I get the following profiling report: Fri Jan 1 10:34 2010 Time and Allocation Profiling Report (Final) Sudoku +RTS -p -RTS total time = 0.00 secs (0 ticks @ 20 ms) total alloc = 165,728 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc CAF GHC.Handle 0.0 10.7 CAF Text.Read.Lex 0.0 2.1 CAF GHC.Read 0.0 1.2 square Main 0.0 2.8 solve Main 0.0 1.3 show_aVx Main 0.0 3.7 readsPrec_aYF Main 0.0 60.6 main Main 0.0 9.6 genNums Main 0.0 5.0 cell Main 0.0 1.2 individual inherited COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 1 0 0.0 0.3 0.0 100.0 main Main 186 1 0.0 9.6 0.0 85.6 show_aVx Main 196 2 0.0 3.7 0.0 3.7 cell Main 197 16 0.0 0.0 0.0 0.0 solve Main 188 5 0.0 1.3 0.0 11.8 genNums Main 189 8 0.0 5.0 0.0 10.4 square Main 194 88 0.0 2.8 0.0 3.2 cell Main 195 16 0.0 0.4 0.0 0.4 col Main 192 4 0.0 0.7 0.0 1.1 cell Main 193 16 0.0 0.4 0.0 0.4 row Main 190 4 0.0 0.7 0.0 1.1 cell Main 191 16 0.0 0.4 0.0 0.4 readsPrec_aYF Main 187 3 0.0 60.6 0.0 60.6 CAF GHC.Read 151 1 0.0 1.2 0.0 1.2 CAF Text.Read.Lex 144 8 0.0 2.1 0.0 2.1 CAF GHC.Handle 128 4 0.0 10.7 0.0 10.7 CAF GHC.Conc 127 1 0.0 0.0 0.0 0.0 Does the column 'entries' represent the number of times the function was called? If so, I don't understand how the 'square' function could be called 88 times when it's caller is only called 8 times. Same thing with 'genNums' (called 8 times, and solve called 5 times) What am I missing here? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

5 6

Undecidable instances with functional dependencies
by Henning Thielemann 16 Feb '10

16 Feb '10

I have the following class and instance class Register a r | a -> r where instance (Register a ra, Register b rb) => Register (a,b) (ra,rb) where and GHC refuses the instance because of violated Coverage Condition. I have more instances like instance Register Int8 (Reg Int8) where instance Register Word8 (Reg Word8) where and for the set of instances I plan, the instance resolution will always terminate. I remember that the term 'undecidable instance' is not fixed and may be relaxed if a more liberal condition can be found. Is there a place, say a Wiki page, where we can collect examples where we think that the current check of GHC is too restrictive?

4 3

How to find unused exported symbols?
by John D. Ramsdell 15 Feb '10

15 Feb '10

I would like to find symbols exported from each module in a program that are not used outside the module. I'm worried my program is accumulating cruft. I'm looking for suggestions on how to find unused exported symbols. Do I have to analyse .hi files? Thanks in advance. John

3 3

Darcs fundraising 2010 - success!
by Eric Kow 15 Feb '10

15 Feb '10

Hi everybody, Here's the final report on our Darcs 2010 fundraising effort. In a word, success! I wasn't sure we could pull it off, but thanks to all of your contributions, we reached our target of $2000. Thanks, everyone! We'll be using this money to fund travel expenses for our bi-annual Darcs hacking sprints. I'm looking forward to seeing what kind of impact this has, how much easier this makes it for us to bring our community together (literally). Finally, I think this would be a good time to call your attention to our new thank-you page <http://www.darcs.net/thanks.html>. This is just a small way for us to make a note of all the ways that you have helped the Darcs project, and how much we appreciate your contributions (your feedback, patches, support). Most recently, I've added a new section to this page, which makes a nod to some of ours larger donors. They also had some rather nice things to say about Darcs, so do have a look :-) Rah! Eric PS. Please let me know if you'd like to make a travel claim for ZuriHac -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9

1 0

IDL - compilers
by Günther Schmidt 15 Feb '10

15 Feb '10

Hi, are there any IDL compilers that can create Haskelk modules from header files or type-libs? Günther

3 4

Two authors especially likely to be spammed.
by Jason Dusek 15 Feb '10

15 Feb '10

I recently discovered that many haskell-cafe mails are being dumped in my SPAM folder. A lot of them are from John Lato and Simon Marlow. I wonder if anyone else has experienced this? -- Jason Dusek

3 2

How many "Haskell Engineer I/II/III"s are there?
by Jason Dusek 15 Feb '10

15 Feb '10

Although I'm fond of Haskell, in practice I am not a Haskell programmer -- I'm paid for Ruby and Bourne shell programming. Many of the jobs posted on this list end up being jobs for people who appreciate Haskell but will work in C# or O'Caml or some-such. I wonder how many people actually write Haskell, principally or exclusively, at work? -- Jason Dusek

32 60