September 2007 - Libraries

Trac/1417 - add pseudoterminal support to the unix library
by Bryan O'Sullivan 19 Sep '07

19 Sep '07

This is a very simple enhancement. openPseudoTerminal :: IO (Fd, Fd) getSlaveTerminalName :: Fd -> IO FilePath Here's the ticket: http://hackage.haskell.org/trac/ghc/ticket/1417 The code ought to work on Linux, Solaris, BSD, HP/UX, and Cygwin, too. I've compile-tested it on Linux, using both openpty and explicit open of /dev/ptmx. I propose a discussion period of one week. Thanks, <b

1 1

substring search api
by Duncan Coutts 19 Sep '07

19 Sep '07

I want to start a discussion about a string searching api, especially with respect to ByteStrings. I'm concerned that we're about to release a bytestring package along with ghc-6.8 that will freeze a less than ideal string search api in stone. We have an opportunity to make that better since at the moment I think there are few serious users of that api since the current implementation is very slow. However in this release cycle we're going to get optimised string searching algorithms and then I expect the number of users to pick up. I'd be a shame if that forces us to keep a not very nice api. That said, here is the current api. -- | Find the indexes of all (possibly overlapping) occurances of a -- substring in a string. findSubstrings :: ByteString -- ^ String to search for. -> ByteString -- ^ String to seach in. -> [Int] -- | Get the first index of a substring in another string, -- or 'Nothing' if the string is not found. findSubstring :: ByteString -- ^ String to search for. -> ByteString -- ^ String to seach in. -> Maybe Int findSubstring p s = listToMaybe (findSubstrings p s) -- | Check whether one string is a substring of another. isSubstringOf :: ByteString -- ^ String to search for. -> ByteString -- ^ String to search in. -> Bool isSubstringOf p s = not (null (findSubstrings p s)) We only have it implemented for strict ByteStrings at the moment. This api isn't too bad for the strict ByteString implementation since we can use indexes to select substrings in O(1) time. However for lazy bytestrings index are much less good since we have to traverse the list of chunks to use the indexes. A more compelling argument is that it's not very Haskelly to use indexes. We normally deal in spans rather than offsets and lengths. One possible alternative that I think is more Haskelly and would suit the strict and lazy (and indeed ordinary list []) implementation is: findSubstring :: ByteString -- ^ String to search for. -> ByteString -- ^ String to seach in. -> (ByteString, -- span before search string ByteString) -- span beginning search string, or empty compare this to our standard List.break function. > break isSpace "foo bar" = ("foo", " bar") > break isSpace "foobar" = ("foo bar", "") So for findSubstring we'd have: > findSubstring "bar" "foo bar baz" = ("foo ","bar baz") > findSubstring "notfound" "foo bar baz" = ("foo bar baz", "") I quite like this as the primitive. isSubstringOf is easily definable in terms of that. I should note that there is really no performance penalty for working in terms of spans rather than indexes. Indeed for the lazy case it'd be faster. findSubstrings is much less clear. What's not clear is what the result type and content should be. The current impl that gives us a list of indexes of possibly-overlapping occurrences seems straightforward. What is the break/span style equivalent? A couple possibilities: findSubstrings :: ByteString -> ByteString -> [ByteString] where each result begins an occurrence and includes the trailing text before the next occurrence. Of course that means we loose any initial span. So we could have: findSubstrings :: ByteString -> ByteString -> (ByteString, [ByteString]) that includes the initial span. Then there's the issue of overlapping spans or not. Overlapping seems more general but also seems confusing when done in terms of spans. Or we could just side-step the issue and not provide a findSubstrings at all and let people implement the behavior they want in terms of findSubstring. Afterall there is no 'many' tokenising variant of List.span or List.break, probably because of the wide variation in requirements. I'd very much appreciate peoples opinions on this. Though bear in mind that I'm not looking for a large string searching framework, I want to pick a supportable primitive for strict and lazy bytestring searching that can go into the bytestring library now so we can avoid freezing a worse api. Duncan

7 9

Re: Building "production stable" software in Haskell
by Simon Marlow 19 Sep '07

19 Sep '07

Adrian Hey wrote: > Neil Mitchell wrote: >> Hi >> >>>> They are less stable and have less quality control. >>> Surely you jest? I see no evidence of this, rather the contrary in fact. >> >> No, dead serious. The libraries have a library submission process. > > It does not follow that libraries that have not been submitted > to this process "are less stable and have less quality control". Nor > does it follow that libraries that have been through this submission > process are high quality, accurately documented, bug free and efficient > (at least not ones I've looked at and sometimes even used). Adrian's right - the set of libraries that are shipped with GHC is essentially random. A bit of history: Originally we shipped pretty much all freely-available non-trivial Haskell libraries with GHC. At some point (about 5 years ago or so) the number of Haskell libraries started to grow beyond what we could reasonably ship with GHC, and some of them were providing duplicate functionality, so we stopped adding to the set. We made a few small exceptions (e.g. filepath) for things that we felt really should be in the default GHC install, but to a large extent the set of libraries that are "shipped with GHC" has remained constant over the last 3 major releases. In 6.6, we made a nomenclature change: we divided the packages "shipped with GHC" into two: those that are required to bootstrap GHC (the "boot" libraries, until recently called the "core" libraries), and the others that we just include with a defualt binary install (the "extra" libraries). On some OSs, e.g. Debian, Ubuntu, Gentoo, you don't even get the "extra" libraries by default. This was intended to be a stepping stone to decoupling GHC from these libraries entirely, which is possible now that we have Cabal and Hackage. What I'm getting around to is that being "shipped with GHC" is not a category that has any particular meaning right now. I think it's time the community started to look at what libraries we have in Hackage, and identify a subset that we should consider "standard" in some sense - that is, those to which the library submission process applies, at the least. If there were such a set, we could easily make GHC's "extra" libraries equal to it. Cheers, Simon

2 1

Re: [Haskell-cafe] Library Process (was Building "productionstable" software in Haskell)
by Claus Reinke 18 Sep '07

18 Sep '07

>> I thought the master plan was that less would come with the compiler / >> interpreter and the user would install packages using cabal. > > Ideally, yes. I think a useful model would be GNU/Linux, where there is > the Linux kernel, developed by core hackers, and then there are > "distributions", which package up particular kernels with a load of > different GNU libraries and utilities to form a complete operating > environment. The maintainers of the distributions do not work on the > kernel, but they do test their own combinations of kernel/libraries + > utilities to ensure that everything plays together nicely. > > I would like to see the same separation forming between the ghc compiler > itself (which would minimally include only the small number of libraries > needed to build the compiler), and larger "distributions" which would be > maintained by other people, and include much larger collections of > packages that the maintainer has tested and verified to work together. > In the best of all worlds, a Haskell "distribution" would include > multiple compilers, not just ghc. i think that such separately maintained distributions would be one way to avoid the version skew chaos that might otherwise result from dropping all but the minimal set of libraries from ghc/hugs/.. distributions. now everybody take a step back to make room for the volunteers?-) a slightly more lightweight approach, that could grow into the above, would be if cabal packages supported nesting/grouping, so that sets of useful/proven libs could be bundled into a single package (the whole package builds if all the subpackages build individually, and form a coherent whole; that is, there'd need to be tests checking that the subpackages are actually compatible versions). then, instead of extra-libs in ghc/hugs/.., there'd be a standard-libs package on hackage showing exactly which haskell implementations it builds&tests with successfully and which not. and one could still get a whole consistent and maintained? bunch of standard libs in one go. </dream> claus

1 0

library submission: Data.Either.unzipEithers :: [Either a b] -> ([a], [b])
by Jeremy Shaw 18 Sep '07

18 Sep '07

http://hackage.haskell.org/trac/ghc/ticket/1695 This function is like unzip for a list of Eithers instead of tuples. According to google code search, I am at least the 5th person to implement this function: http://www.google.com/codesearch?hl=en&lr=&q=%22%5BEither+a+b%5D+-%3E+%28%5… I opted for the name unzipEithers because the function is similar to two existing functions: unzip and catMaybes. It seems less similar to partition, because partition does not desconstruct the values, it just divides them into to two groups. I have no particular attachment to the name however. I modeled the implementation after unzip and partition. Hopefully I made effective use of the irrefutable patterns and laziness, but someone else should verify. j.

4 5

Statistics Module
by Marshall Beddoe 17 Sep '07

17 Sep '07

For my first contribution to the Haskell community, I was thinking of releasing a statistical computing module. Using google code, I found a few Stats.hs files contained in various projects, therefore I think it would be a good idea to have a unified module. Currently, my module contains all the base functions one would expect: arithmetic/geometric/harmonic mean, median, mode, range, average/standard deviation, variance, interquartile range, kurtosis and skew. Plans moving forward include histograms, covariance and principal and independent components. What would you all like to see in a module like this? Thanks very much, Marshall

2 1

instance Eq (TChan a)
by Ashley Yakeley 15 Sep '07

15 Sep '07

Like most reference-like things, Control.Concurrent.STM.TChan should be in Eq, shouldn't it? It's not in stm=2.0, though it does have Eq (TVar a). -- Ashley Yakeley Seattle WA

1 0

Parsec issue
by Lennart Kolmodin 11 Sep '07

11 Sep '07

Hi dear list, while using parsec for a project I ran into this issue. Take the following program: import Text.ParserCombinators.Parsec import Text.ParserCombinators.Parsec.Language import Text.ParserCombinators.Parsec.Token main = do run "0xf" run "xf" run str = putStrLn $ str ++ " parses as: " ++ show (parse p "" str) p = hexadecimal $ makeTokenParser emptyDef ----- Running it yields: 0xf parses as: Left (line 1, column 1): unexpected "0" xf parses as: Right 15 ----- Looking at the code for hexadecimal in Parsec.Token it looks like: hexadecimal = do{ oneOf "xX"; number 16 hexDigit } clearly not handling the leading zero as the docs states: hexadecimal :: CharParser st Integer Parses a positive whole number in the hexadecimal system. The number should be prefixed with "0x" or "0X". Returns the value of the number. Same goes for 'octal' in the same module. Parsing using 'natural' works though: nat = zeroNumber <|> decimal zeroNumber = do{ char '0' ; hexadecimal <|> octal <|> decimal <|> return 0 } Also, neither hexadecimal nor octal eat the trailing whitespaces as natural, integer and float does (using lexme). Am I missing something? Cheers, Lennart K

2 1

Network.Socket.getaddrinfo
by Peter Simons 11 Sep '07

11 Sep '07

Hi, the module Network.Socket provides 'getaddrinfo' only if IPv6 support is enabled. That surprises me because, as far as I know, there is nothing IPv6-specific about that function. Does anyone know why that choice was made? Best regards, Peter

2 2

Second Request for code review - Knuth Morris Pratt for Data.Sequence
by Justin Bailey 11 Sep '07

11 Sep '07

Using the code developed for ByteStrings by myself, Christ Kuklewicz and Daniel Fischer, I've implemented Knuth-Morris-Pratt substring searching on Data.Sequence "Seq" values. Attached you'll find the library in kmp.zip.safe. The algorithm is implemented in the module Data.Sequence.KMP. At the root, SpeedTest.hs can be compiled on Windows with the "prof_compile.bat" file included (you'll need to install the "regex-dfa" and "regex-base" packages from Hackage to build). SpeedTest searches for a known value in the 7 MB file "endo.dna" (which can be downloaded from http://www.icfpcontest.org/endo.zip) using several different algorithms and methods: strict and lazy bytestrings, regular expressions, and the KMP algorithm for "Seq" values. SpeedTest is pretty fast but I worry about its space usage. It may just be the nature of Seq values, but I cannot get it to run in constant space when I think it should be. I'm especially interested in help here. All comments and feedback are welcome. Since the zip file includes a darcs context file, feel free to send patches. Justin

1 0