January 2008 - Haskell-Cafe

Libraries need a new owner
by Adrian Hey 27 Mar '08

27 Mar '08

Hello Folks, As some of you will be aware, I have been working on various Map implementations that currently live here.. http://code.haskell.org/collections/collections-ghc6.8 The libs in question being Data.Tree.AVL, Data.Trie.General and a few other bits like Data.COrdering and the AVL based Data.Map/Set clones. Well, I have decided to stop work on these. So they need a new owner if they're going to go anywhere. If anyone is interested in the job then I suggest they contact myself or Jean-Philippe Bernardy. Of course I will be happy to provide any help or advise anyone who takes over these libs may feel they need from me. I might even contribute a few patches from time to time myself :-) Thanks -- Adrian Hey

3 7

Implementing fixed-sized vectors (using datatype algebra?)
by Alfonso Acosta 15 Mar '08

15 Mar '08

Hi, The EDSL implementation (system design) I'm working on would really benefit from an implementation of fixed-sized vectors. I thought this would be a generally desired ADT but it turned out I wasn't able to find an implementation. I was thinking about using datatype algebra plus GADTs to implement a type-level parameter indicating the size of the vector. I'm a total noob with regard to GADTs and type-level algebra trickery. So my questions are: 1) Do you think it is feasible? Can you think about a better approach? 2) An implementation of type-level Naturals would really help. What has already been done? Thanks in advance, Fons

13 84

fast graph algorithms without object identities
by Henning Thielemann 26 Feb '08

26 Feb '08

It seems that algorithms on graphs can be implemented particularly efficient in low-level languages with pointers and in-place updates. E.g. topological sort needs only linear time, provided that dereferencing pointers requires constant time. I could simulate pointer dereferencings and pointer updates by Map yielding linear logarithmic time for topological sort. I wonder if it is possible to write a linear time topological sort using lazy evaluation, since the runtime system of Haskell implementations is a graph processor based on pointers.

4 5

Re: [Haskell-cafe] Haskell maximum stack depth
by Neil Mitchell 19 Feb '08

19 Feb '08

Hi > ghc uses a pretty conventional stack AFAIK, and it is arbitrarily > limited, but you can change the limit with +RTS options. GHC uses a conventional stack (in that you put stuff at the top, and take it off from the top), but it is not a conventional stack in the way imperative programs work. In an imperative program if you make a function call, a frame gets pushed on the stack. When the function call returns, the frame gets popped off the stack. In Haskell, lazy evaluation makes it massively more confusing. > Also, stack "overflows" are a pretty common cause of program failure > IME, not at all rare. At least, far more common than whatever error > message you get from heap exhaustion (can't even remember the last > time I saw one of those). Yes, I agree. However, in imperative programming stack overflow nearly always means you've exceeded some recursion depth in the program, and should think about refactoring it to use explicit loops. In Haskell, stack overflow is usually a laziness bug. Same error message, completely different causes. In Haskell, the solution to stack overflow is almost never "increase the stack depth", but "fix your laziness leak". To answer the question if Haskell has a "stack depth restriction ... like Java" the answer is no. It has a stack depth restriction, but its absolutely nothing like Java in the way it uses the stack, so you can't compare them. My guess is that Istarex's inner thought might have been along the lines of "in Java if I do too much recursion I get a stack overflow, but Haskell only has recursion, does that mean I get into stack overflows all the time?". I could of course be entirely wrong ;-) Thanks Neil

14 47

threads + IORefs = Segmentation fault?
by David Roundy 14 Feb '08

14 Feb '08

Hi all, I'm working on some new progress-reporting code for darcs, and am getting segmentation faults! :( The code uses threads + an IORef global variable to do this (with lots of unsafePerformIO). So my question for the gurus who know more about this than I do: is this safe? I thought it would be, because only one thread ever modifies the IORef, and the others only read it. I don't really care if they read a correct value, as long as they don't segfault. The code (to summarize) looks like: {-# NOINLINE _progressData #-} _progressData :: IORef (Map String ProgressData) _progressData = unsafePerformIO $ newIORef empty updateProgressData :: String -> (ProgressData -> ProgressData) -> IO () updateProgressData k f = when (progressMode) $ modifyIORef _progressData (adjust f k) setProgressData :: String -> ProgressData -> IO () setProgressData k p = when (progressMode) $ modifyIORef _progressData (insert k p) getProgressData :: String -> IO (Maybe ProgressData) getProgressData k = if progressMode then lookup k `fmap` readIORef _progressData else return Nothing The key function is beginTedious :: String -> IO () beginTedious k = do tid <- forkIO $ handleProgress k debugMessage $ "Beginning " ++ k setProgressData k $ ProgressData { sofar = 0, latest = Nothing, total = Nothing, handler = Just tid } which is called before an action that may be so tedious for our users that they need their day brightened by messages such as "Applying patch 137/1436". The handleProgress function alternates between threadDelay and reading the progress data to see whether any progress has been made and printing messages. Meanwhile the main thread calls functions that update _progressData. Anyhow, the point is that I'm getting segfaults, even after recompiling everything from scratch! Is this in fact that unsafe? Do I really need to switch to MVars, even though no locking is required? -- David Roundy Department of Physics Oregon State University

6 9

Export Haskell Libraries
by SevenThunders 12 Feb '08

12 Feb '08

I've finished a good sized Haskell project which I now must expose as a library (along with a lot of C code) to my fellow engineers. I had originally devoped my code on Windows XP and managed to learn how to wrap my Haskell code in a DLL and create an MSVC linkable library stub for the DLL. Although involved, the output in windows is relatively transparent in that as long as the paths are available to the Haskell runtime libraries and my DLL, linking is straightforward. Now however I find I must export the same libraries to linux. I decided to get 'smart' and repackage my build tools using CMAKE and cabal. Building the C object files is no problem and even configuring Cabal to generate my executables is not too painful. However the pain begins when one tries to link any Haskell object files or libraries to an external C program. Using ghc -v during the build reveals that gcc has about 50 -u flag arguments and links to 9 or 10 different libraries. Given that my little component is just a tiny part of a large software project involving many more engineers and many man years of work, it's not going to be fun to link my little library using all these crazy build flags to a large external project, especially when order is important. Wouldn't it be nice if there were a single run time library I could link to, (or even generate on the fly) that didn't have this intricate build step. How is ghc/Haskell supposed to integrate with the rest of the software world? A related issue in the building of my export libraries is cabal itself. I want to package my own library with some external object files etc and some Haskell code. It's easily done with ar and the correct object files. Unfortunately it is not clear from the documentation how I can force cabal to place the object files and generated stub files in a place where I can use them. (CMake is kind of forcing me to have them reside with the source for reasons I don't want to go into here.) I instead find myself copying the object files (*.o) back into the source directory from an obscure tmp directory several layers down from the source directory. This is not particularly portable and is probably quite fragile once someone decides to change the directory hiearcharchy in cabal. I guess I am surprised that on linux, with all of it's amazing software development tools, that Haskell export libraries would be this tricky to develop. -- View this message in context: http://www.nabble.com/Export-Haskell-Libraries-tf3569747.html#a9972866 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

6 10

Internships at GHC HQ
by Simon Peyton-Jones 09 Feb '08

09 Feb '08

Would you be interested in working at Microsoft Research for three months? If so, you might want to think about applying for an internship. Simon and I are looking for interns, starting in summer 2008. Lots of background info here: http://hackage.haskell.org/trac/ghc/wiki/Internships including a bunch of possible projects, although you may also have ideas of your own. But the bottom line is - apply by end Feb 2008 for this round - tell one of us that you have done so (None of this is restricted to Haskell stuff. You can apply to work at any Microsoft Research lab, on any topic. But there are a lot of applicants, so you are more likely to be successful if you are fairly specific about who at MSR you'd like to work with and why, and contact that person to say that you've applied.) Simon

5 4

Draft chapters of "Real World Haskell" now publicly available
by Bryan O'Sullivan 08 Feb '08

08 Feb '08

John, Don and I are pleased to announce the beginning of the public beta programme for our upcoming book, "Real World Haskell". For further details, please see the following blog entry: http://www.realworldhaskell.org/blog/2008/01/21/finally-the-public-beta-pro… Thanks to all of the Haskell community members who have so far performed sterling service in commenting on our closed drafts. We look forward to your feedback! <b

10 20

Poor libraries documentation
by Neil Mitchell 03 Feb '08

03 Feb '08

Hi, I went looking for the the function in Haskell to calculate cos^{-1}, inverse cosine. Unfortunately, the poor documentation in the libraries hampered my attempts. The documentation for the trig functions in Haskell is completely non-existent: http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Acos For a start, its probably a good idea to mention that cos is an abbreviation of cosine (most people will know, but its handy to state it). Secondly, and much more importantly, it should state whether these measurements are in degrees or radians. It should also state things like acos is the inverse of cos - its been a while since I last used trig and I had to look it up!!! We are also lacking documentation for things like odd/even, which are obvious enough, but its nice to say that they meet the intuition. Could haddock be extended to give a warning message (in -Wall mode perhaps) when an exported function has no comment associated with it? This would be a really nice project for someone to take on, and very much appreciated :-) Thanks Neil

13 20

SPJ on the radio (at .NET Rocks :)
by Don Stewart 03 Feb '08

03 Feb '08

Simon talks about laziness, purity and other FP concepts to some .NET guys. Simon starts 7minutes 20seconds in. http://www.dotnetrocks.com/default.aspx?ShowNum=310 Good work Simon! -- Don

3 2