September 2008 - Libraries

Performance horrors
by Adrian Hey 06 Sep '08

06 Sep '08

Hello Folks, I was looking at the definitions of nub (and hence nubBy) recently in connection with a trac ticket and realised that this is O(n^2) complexity! Ouch! I was going to say I sure hope nobody uses this in real programs, but I thought I'd better check first and I see that darcs seems to use it in a few places. Hmm.. How did we ever get stuff like this in the standard libs? I can only imagine this is relic from the days when Haskell was only used for research or pedagogical purposes only (not for real programs). Seeing as practically all Eq instances are also Ord instances, at the very least we could have O(n*(log n)) definitions for .. nub :: Ord a => [a] -> [a] nub = nubBy compare nubBy :: (a -> a -> Ordering) -> [a] -> [a] nubBy cmp xs ys = -- something using an AVL tree perhaps. ..or even better using the generalised trie stuff Jamie Brandon has been working on. Of course I'm not actually advocating this as it's probably bad policy to have a simple standard lib dependent on any complex non-standard lib. But if it just isn't possible to implement some functions with reasonable efficiency using simple definitions only then I think they really shouldn't be there at all. Instead we should make users "roll their own" using whatever complex non-standard lib they want. So could nub and nubBy be deprecated and an appropriate health warning added to the Haddock? In the mean time I think I'll put appropriate alternative definitions in the next AVL release and ask Jamie Brandon to consider doing the same in his generalised tries lib (GMap). Also, looking at a few other functions there like union(By) and intersection(By) make me quite suspicious. Maybe we need a thorough performance audit to get rid of implementations that are so insanely inefficient they should *never* be used. Regards -- Adrian Hey

16 32

Generalize groupBy in a useful way?
by Bart Massey 06 Sep '08

06 Sep '08

I experienced some interesting behavior with groupBy tonight, and thought I'd run it by folks as a proposal for the Haskell libraries. Consider the predicate incp e1 e2 = e1 + 1 == e2 Naively, one might expect groupBy incp [2,3,4,5,6] == [[2,3,4,5,6]] but one actually gets [[2,3],[4,5],[6]] from the standard library implementation. The Haskell98 Report makes it clear that "When the 'By' function replaces an Eq context by a binary predicate, the predicate is assumed to define an equivalence." Thus, the observed behavior is technically correct, or at least technically not incorrect. The incp predicate does not follow the equivalence laws (it is neither symmetric nor reflexive), so groupBy is probably permitted to return most any result of the correct type. What is actually happening is that the groupBy implementation is using span with a predicate (incp a) where a is the first element in the list. I think it would be better to expand the definition of of groupBy such that the equality test is applied only to adjacent elements (with the arguments in proper order). This would not change the behavior for true equality predicates, but would permit cases like incp to have sensible behavior, which can occasionally be useful. (It was to me in this case: I was identifying straights in poker hands.) Here's a suggested (untested) implementation. (See also http://hpaste.org/10134?#a0 ) It relies on a new "chain" function that is the binary equivalent of span. This function seems to me to be useful in its own right. chain :: (a -> a -> Bool) -> [a] -> ([a],[a]) chain _ [] = ([], []) chain _ [e] = ([e], []) chain p (e1 : es@(e2 : _)) | p e1 e2 = let (s1, s2) = chain p es in (e1 : s1, s2) | otherwise = ([e1], es) groupBy' _ [] = [] groupBy' p l = s1 : groupBy' p s2 where (s1, s2) = chain p l The implementation of groupBy' is actually a bit cleaned up compared to that of groupBy. Regardless of what is done here, it would be nice to expand the Haddock for groupBy in the standard library to make it clear how the predicate is used. Comments and suggestions are welcome. Am I way off base here? Bart Massey bart(a)cs.pdx.edu

5 4

darcs patch: Export the Positive constructor.
by Nicolas Pouillard 06 Sep '08

06 Sep '08

Others types like NonNegative, NonZero have their constructor exported in Test.QuickCheck, the Positive constructor deserve the same :) Sat Sep 6 14:23:22 CEST 2008 Nicolas Pouillard <nicolas.pouillard(a)gmail.com> * Export the Positive constructor.

1 1

darcs patch: Unbreak the GHC build with older versions of gcc
by kili＠outback.escape.de 04 Sep '08

04 Sep '08

Thu Aug 28 16:27:43 CEST 2008 kili(a)outback.escape.de * Unbreak the GHC build with older versions of gcc Stg.h must be included before HsBase.h, because the latter contains function definitions causing older versions of gcc (3.3.5 in my case) to bail out with "error: global register variable follows a function definition" on Regs.h, which is included by Stg.h.

2 2

Arrow without `>>>'
by Valery V. Vorotyntsev 03 Sep '08

03 Sep '08

Hi, friends, I've built GHC from darcs, and... Could anybody tell me, what's the purpose of Arrow[1] not having `>>>' method? 1. http://darcs.haskell.org/packages/base/Control/Arrow.hs $ ghci GHCi, version 6.9.20080104: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :m + Control.Arrow Prelude Control.Arrow> :i Arrow class (Control.Category.Category a) => Arrow a where arr :: (b -> c) -> a b c pure :: (b -> c) -> a b c first :: a b c -> a (b, d) (c, d) second :: a b c -> a (d, b) (d, c) (***) :: a b c -> a b' c' -> a (b, b') (c, c') (&&&) :: a b c -> a b c' -> a b (c, c') -- Defined in Control.Arrow instance Arrow (->) -- Defined in Control.Arrow instance (Monad m) => Arrow (Kleisli m) -- Defined in Control.Arrow Prelude Control.Arrow> Leaving GHCi. I can't build[2] arrows-0.3 package without `>>>' in Arrow. 2. vvv@fun:~/src/arrows$ darcs w { hunk ./Control/Arrow/Operations.hs 36 +import Control.Category ((>>>)) hunk ./Control/Arrow/Transformer/CoState.hs 23 +import Control.Category ((>>>)) } vvv@fun:~/src/arrows$ runhaskell Setup build Preprocessing library arrows-0.3... Building arrows-0.3... [ 3 of 12] Compiling Control.Arrow.Transformer.CoState ( Control/Arrow/Transformer/CoState.hs, dist/build/Control/Arrow/Transformer/CoState.o ) Control/Arrow/Transformer/CoState.hs:29:7: `>>>' is not a (visible) method of class `Arrow' The question arises "should I?", but this is one of lambdabot's[3] depencies. 3. http://code.haskell.org/lambdabot/ Thanks a lot! -- vvv

4 5

Re: Splitting SYB from the base package in GHC 6.10
by Sean Leather 02 Sep '08

02 Sep '08

On Wed, Sep 3, 2008 at 00:32, Ian Lynagh wrote: > On Tue, Sep 02, 2008 at 11:21:10PM +0100, Ross Paterson wrote: > > syb need no longer be a boot package. > > If base3-compat comes with GHC then syb must too. > So, it would still need to be a boot package. However, if base3-compat depended on the specific release version of syb (i.e. == instead of >=), then we could still install a newer version of the syb package with a different API and not break base3-compat, correct? Sean

2 1

cabal use questions
by minh thu 02 Sep '08

02 Sep '08

Hi, I've some questions related to Cabal. The command "ghc-pkg list" reports two versions of Cabal : 1.2.4.0 and 1.4.0.2. How do I get rid of the first one ? Also, I try to build a Cabal package of my own but configuring it doen't work : $ runhaskell Setup.lhs configure Configuring ae-fast-0.1... Setup.lhs: At least the following dependencies are missing: GLUT -any, OpenGL -an I have the OpenGL and GLUT packages (doing :m + them in ghci works). I run the configure command in this directory : $ ls ae-fast.cabal Graphics LICENSE Setup.lhs $ cat ae-fast.cabal name: ae-fast version: 0.1 Cabal-Version: >= 1.2 synopsis: Miscellaneous stuffs to easily try new ideas description: Miscellaneous stuffs to easily try new ideas category: Graphics license: BSD3 license-file: LICENSE author: Vo Minh Thu maintainer: Vo Minh Thu build-type: Simple Library Build-Depends: base, OpenGL, GLUT Exposed-Modules: Graphics.AE.Fast.GLUT What's wrong ? Thank you, Thu

2 2

Re: Bugfix for QuickCheck 1.1.0.0
by Patrick Perry 02 Sep '08

02 Sep '08

Jed Brown wrote: > The idea with QC is that you start with `simple' random input and > progress to more `complicated' input. If say, you are testing a > function that builds a list with length equal to the output of the > QC-generated function (Double->Int) (with positive precondition) you > could be building a huge list very early. This wouldn't happen with > other types since `simple' QC-generated functions for, say, (Int->Int) > will map small integers to small integers. I don't think this has anything to do with the definition of coarbitrary. As I understand things: coarbitrary is a function of type x -> StdGen arbitrary is a function of type StdGen -> Int -> x For the type "x -> y", arbitrary is equal to \g n -> (\x -> let g' = coarbitrary x in arbitrary g' n) I did an experiment in QC1 (with patch). Here are two properties: prop_f (f :: Double -> Int) x = trace (show $ f x) True prop_g (f :: Int -> Int) x = trace (show $ f x) True Below is the output. Do you think that one is "more simple" than the other? Patrick 1 0 2 -2 0 0 0 0 2 -3 00 11 -3 -5 -9 05 06 17 -5 49 30 -1 -1 33 -8 -4 66 27 78 09 60 01 -8 83 -12 35 -4 13 38 -1 -4 -1 02 -10 -3 45 06 -10 -12 -4 20 -7 -18 -2 84 -10 -2 13 38 29 60 -6 12 20 -12 95 -8 -22 58 49 90 -12 12 -12 -1 -1 -14 -14 27 -1 00 01 -16 23 54 25 24 -15 48 14 -10 -37 02 -19 84 17 -15 -19 -1 42 -3 1 -3 1 3 -3 -4 -4 -2 -3 10 -1 02 43 14 05 -1 07 18 -1 -3 21 -4 -5 34 25 -1 17 18 -8 -4 31 13 53 64 95 06 27 -2 -6 60 10 72 -2 -3 45 36 -9 16 39 -4 01 27 -3 -22 -7 -4 -14 -1 -6 -8 -1 -23 -13 14 45 -24 17 -1 49 -5 25 -13 11 44 05 26 12 -12 -33 00 11 27 93 35 25 -3 -6 98 -12 -20 10 -11 43 34 12 -43 17 -3 09

2 1

ANN: unicode-properties 3.2.0.0, unicode-names 3.2.0.0
by Ashley Yakeley 02 Sep '08

02 Sep '08

unicode-properties 3.2.0.0, unicode-names 3.2.0.0 These two packages are representations in Haskell of various data in the Unicode 3.2.0 Character Database. Unicode 3.2.0 was the latest version of the Unicode standard at the time I wrote most of the code; later I may move the packages to the latest version (currently 5.1.0). The unicode-properties package contains functions to determine general category, case, and a wide range of other properties, as well as to do decomposition and case-folding. The unicode-names package contains just one function, getCharacterName, for getting the name of a character. It's separated out because it's a sufficiently large proportion of the total data. Both packages use the type "Char" to represent Unicode characters (more pedantically, codepoints). In GHC Char has the range ['\x0'..'\x10FFFF'], matching the Unicode standard. The packages won't work with compilers that restrict Char to a smaller range. Hackage: <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/unicode-properti…> <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/unicode-names> Source for both packages: <http://code.haskell.org/unicode-properties/> Most of the data is auto-generated at build time from files downloadable from the Unicode web-site. I expect Don will have them both in Arch Linux within the hour. -- Ashley Yakeley

4 5

Re: Bugfix for QuickCheck 1.1.0.0
by Patrick Perry 02 Sep '08

02 Sep '08

Two things: First, the version of variant I gave will behave reasonably if given a negative argument, so the overflow is not catastrophic. Second, I'm not sure what you mean by a "simple" generator. Let's consider Int instead of Double. With the current version of variant, "coarbitrary 1" calls split one time, and "coarbitrary 1000" calls split 1000 times. At the end of the day, though, all random number generators are equally "complex". The only difference is that they have different seeds. You are correct the QuickCheck2 uses "toRational" instead of "decodeFlloat" for the coarbitrary instance. I don't think it matters either way which one gets used, though, and I would rather change as little code as possible in QuickCheck1. Patrick Jed Brown wrote: > I haven't looked at this in a while but I'm not sure this completely > fixes things with regard to coarbitrary. That is, we can produce very > simple Doubles (as defined by arbitrary) that produce (via > coarbitrary) > very complicated generators for other types (and there was an issue of > overflow with possible sign change due to nasty casting, hence variant > getting a negative argument). As I understand it, your fix to variant > means that variant will return in a reasonable amount of time even > with > a huge argument, but it doesn't fix the issue that coarbitrary should > produce a `simple' generator for a `simple' argument. I thought QC2 > had > a mechanism to fix this. >

2 1