March 2011 - Libraries

Re: [Haskell] ANNOUNCE: incremental-parser library package
by Mario Blažević 22 Mar '11

22 Mar '11

2011/3/22 Philippa Cowderoy <postmaster(a)flippac.org> > This is what newtypes are for, no? > I did not think of that approach. I'm not sure how well it would work out, but it would solve another problem I have, which is the duplication of combinators many, some, and optional. Each of these could exist in two forms, the lazy one and the greedy one, and the only difference is the underlying choice combinator, (<|>) vs. (<<|>). I'm not aware of any other parsing library taking this road, though, and there must be a good reason. I'll try and see. > 2011/3/22 Mario Blažević <mblazevic(a)stilo.com> > >> >> This seems very interesting. One question: >>> >>> > The MonadPlus and the Alternative instance differ: the former's mplus >>> > combinator equals the asymmetric <<|> choice. >>> >>> Why? >>> >> >> >> Good question. Basically, I see MonadPlus as a union of Monad and >> Alternative. The class should not exist at all. But as long as it does, I >> figured I should provide an instance, and I made it different from the >> Monoid+Alternative combination because otherwise it would be useless. My >> second choice would be to remove the instance completely. >> > > I have to admit I really do not like having Applicative and MonadPlus with > different behavior. Yes, one is redundant, but that is more an artifact of > language evolution, than an intentional opportunity for diverging behavior. > > Every library I am aware of to date, save of course this one, has > maintained their compatibility. > > If the instance for Alternative satisfies the underspecified MonadPlus > laws, I'd just as soon have the 'useless redundant' instance. The power of > MonadPlus is in the combinators that are built on top of it. Not in the > primitives themselves. > > If the Alternative instance would not be a legal MonadPlus instance, then > I'd feel much less queasy with your second scenario, and it simply removed. > > -Edward >

1 0

efficient Bytestring mapM_ for IO/ST?
by Brandon Moore 22 Mar '11

22 Mar '11

Is there an efficient way to iterate over the bytes of a ByteString? For a benchmark, I am just computing the sum of the bytes in an STRef. This is a bit silly, but makes for simple test code. (Accumulating a sum in a boxed STRef is several times slower than computing a full histogram in an STUArray, and foldl' (\x b -> x + fromIntegral b) 0 is faster still). The skeleton of the test program is import qualified Data.ByteString.Lazy as L import Control.Monad.ST import Control.Monad import Data.STRef import Data.Word mapMBS_ST : (Word8 -> ST s ()) -> L.ByteString -> ST s () mapMBS_ST = ??? main = do bytes <- L.readFile "input" print $ runST (do v <- newSTRef (0 :: Word64) mapMBS_ST (\b -> do x <- readSTRef v writeSTRef v $! x + fromIntegral b) bytes readSTRef v) The file "input" is 1GB of random bytes (from /dev/urandom). A version which uses the internal representation and explicit peeks runs several times faster than the best implementation I could write without using the unsafe interface. The safe implementations I tried were sum3 : mapMBS_ST f bytes = L.foldr (\b r -> f b >> r) (return ()) bytes sum4 : mapMBS_ST f bytes = if L.null bytes then return () else f (L.head bytes) >> mapMBS_ST f (L.tail bytes) sum5 : mapMBS_ST f bytes = mapM_ f (L.unpack bytes) sum used an unsafe implementation, and sum2 simply uses foldl'. Here are times. Runs vary by a few hundredths of a second user time. ./sum 8.62s user 0.39s system 99% cpu 9.006 total ./sum2 1.26s user 0.34s system 99% cpu 1.604 total ./sum3 72.25s user 0.50s system 99% cpu 1:12.96 total ./sum4 20.55s user 0.66s system 99% cpu 21.251 total ./sum5 391.18s user 1.23s system 99% cpu 6:32.76 total Comparing sum and sum2 gives some idea of the overhead that comes from the boxed STRef, so the relative overhead of the different iteration routines is probably even higher. Looking at the ByteString code, I suspect the foldr version performs badly because foldr uses one unsafePerformIO over a loop which builds the value in an argument, and GHC doesn't see that pointer accesses in the loop could be lifted out of the unsafePerformIO and interleaved with the IO actions built from the argument. (I don't expect GHC to be too smart about taking advantage of unsafePerformIO). Perhaps foldr could be modified so the foldr version above will optimze nicely. Are the benchmarks in http://darcs.haskell.org/bytestring/ good for avoiding performance regressions? That repository has recent changes, but the page Is http://www.cse.unsw.edu.au/~dons/fps.html which is supposedly the bytestring homepage seems a little out of date. Brandon Code for the unsafe map follows: module BytestringMaps (mapMS_IO, mapMBS_IO, mapMS_ST, mapMBS_ST) where import qualified Data.ByteString.Lazy as L import Data.ByteString as S import Data.ByteString.Unsafe as BU import Data.Word import Control.Monad import Data.Array.Storable import Foreign.Storable import Foreign.Ptr import Control.Monad.ST for l u m = go l where go ix | ix >= u = return () | otherwise = m ix >> go (ix+1) {-# INLINE mapMS_IO #-} mapMS_IO :: (Word8 -> IO ()) -> S.ByteString -> IO () mapMS_IO fun chunk = unsafeUseAsCStringLen chunk (\(ptr,len) -> let ptr' = castPtr ptr :: Ptr Word8 in for 0 len (\ix -> do c <- peekElemOff ptr' ix fun c)) {-# INLINE mapMBS_IO #-} mapMBS_IO :: (Word8 -> IO ()) -> L.ByteString -> IO () mapMBS_IO fun str = mapM_ (mapMS_IO fun) (L.toChunks str) {-# INLINE mapMS_ST #-} mapMS_ST :: (Word8 -> ST s ()) -> S.ByteString -> ST s () mapMS_ST fun chunk = unsafeIOToST $ unsafeUseAsCStringLen chunk (\(ptr,len) -> let ptr' = castPtr ptr :: Ptr Word8 in for 0 len (\ix -> do c <- peekElemOff ptr' ix unsafeSTToIO (fun c))) {-# INLINE mapMBS_ST #-} mapMBS_ST :: (Word8 -> ST s ()) -> L.ByteString -> ST s () mapMBS_ST fun str = mapM_ (mapMS_ST fun) (L.toChunks str)

2 2

Proposal: Add newTimeoutKey and insertTimeout to System.Event
by Bas van Dijk 22 Mar '11

22 Mar '11

Hello, I would like to propose adding and exporting the following functions from System.Event.Manager and also export them from System.Event: -- | Returns a unique 'TimeoutKey' that can be used by 'insertTimeout'. newTimeoutKey :: EventManager -> IO TimeoutKey newTimeoutKey = fmap TK . newUnique . emUniqueSource -- | Like 'registerTimeout' but registers the timeout in the given number of -- microseconds /at the specified key/ in the event manager. If the key was -- already present the associated timeout is replaced with the given timeout. -- Unique keys can be created using 'newTimeoutKey'. insertTimeout :: EventManager -> TimeoutKey -> Int -> TimeoutCallback -> IO () insertTimeout mgr (TK key) us cb = do expTime <- fromNow us -- We intentionally do not evaluate the modified map to WHNF here. -- Instead, we leave a thunk inside the IORef and defer its -- evaluation until mkTimeout in the event loop. This is a -- workaround for a nasty IORef contention problem that causes the -- thread-delay benchmark to take 20 seconds instead of 0.2. atomicModifyIORef (emTimeouts mgr) $ \f -> let f' = (Q.insert key expTime cb) . f in (f', ()) wakeManager mgr 'fromNow' is an internal utility function defined as: -- | @fromNow us@ returns the time in seconds @us@ microseconds from now. fromNow :: Int -> IO Double fromNow us = do now <- getCurrentTime return $ fromIntegral us / 1000000.0 + now The existing registerTimeout can be rewritten in terms of these: registerTimeout :: EventManager -> Int -> TimeoutCallback -> IO TimeoutKey registerTimeout mgr us cb = do !tk <- newTimeoutKey mgr if us <= 0 then cb else insertTimeout mgr tk us cb return tk The reason I would like to have these is that with them I can write more efficient resettable timeouts. A resettable timeout API looks something like this: data Key register :: EventManager -> Int -> TimeoutCallback -> IO Key pause :: Key -> IO () reset :: Key -> IO () cancel :: Key -> IO () 'register mgr us cb' registers a callback 'cb' with the event manager 'mgr' to fire after 'us' microseconds. It returns a key which can be used to control the timeout. When 'pause' is called on a key, belonging to a timeout which hasn't fired yet, the timeout is suspended indefinitely until it is reset or canceled. When 'reset' is called on a key, belonging to a timeout which hasn't fired yet, the timeout period will be extended with at least the original period. 'cancel' removes the timeout from the event manager. The Warp web-server contains one implementation of resettable timeouts: https://github.com/snoyberg/warp/blob/master/Timeout.hs Note that their API is a bit more restricted but the idea is the same. The implementation uses one thread which runs a loop which delays for the timeout period then processes all the registered timeouts. Registered timeouts are put in a list and stored in an IORef. With the proposed additional functions for System.Event I can write a simpler (and hopefully slightly more efficient) implementation of resettable timeouts which don't need to forkIO and don't need to store timeouts in a list: https://github.com/basvandijk/resettable-timeouts/blob/master/System/Timeou… I also wrote a CPS-like version: https://github.com/basvandijk/resettable-timeouts/blob/master/System/Timeou… Discussion deadline: 2 weeks. A patch for base is attached. Regards, Bas

3 5

protocol-buffers updated
by Chris Kuklewicz 22 Mar '11

22 Mar '11

Hi, Thanks for the help and patches for Haskell protocol-buffers/hprotoc. I have updated this to version 1.8.3 on hackage and the darcs repository may lag a few days. The program is working for me with ghc-7.0.2 on Haskell Platform (64-bit!) for OS X. Generated files now include LANGUAGE headers that I hope have the all the needed flags. The generated files have an internal change where the Prelude and protocol-buffer libraries are now imported under different qualified names. I have tested this but I may have missed something. Package protocol-buffers-descriptor has been built against the descriptor.proto from google's version 2.4.0 but the supported features are still on par with google version 2.3.0. In particular I have not tried to add syntax support for the new way of specifying default options of message type. Does anyone need this? Cheers, Dr. Chris Kuklewicz

1 0

seq/parametricity properties/free theorems and a proposal/question
by Tyson Whitehead 21 Mar '11

21 Mar '11

The haskell (2010) report says: "The function seq is defined by the equations: seq _|_ b = _|_ seq a b = b, if a /= _|_ seq is usually introduced to improve performance by avoiding unneeded laziness. Strict datatypes (see Section 4.2.1) are defined in terms of the $! operator. However, the provision of seq has important semantic consequences, because it is available at every type. As a consequence, _|_ is not the same as \x -> _|_ since seq can be used to distinguish them. For the same reason, the existence of seq weakens Haskell’s parametricity properties." As has been noted in the literature (and presumably the mailing lists), this has important consequences for free theorems. For example, the property map f . map g = map (f . g) should be derivable from the type of map "(a -> b) -> [a] -> [b]" (i.e., as map works on all a's and b's, it can't actually do anything other than move the a's around, wrap them with the given function to get the b's, or pass them along to other functions which should be similarly constrained). However, this last bit about passing them to similarly constrained functions is not true thanks seq. There is no guarantee map, or some other polymorphic function it invokes has not used seq to look inside the universally quantified types and potentially expose _|_. For example, consider map' f [] = [] map' f (x:xs) = x `seq` f x : map f xs Now "map' f . map' g = map' (f . g)" is not true for all arguments. map' (const 0) . map' (const undefined :: Int -> Int) $ [1..10] = [undefined] map' (const 0 . undefined :: Int -> Int) $ [1..10] = [0,0,0,0,0,0,0,0,0,0] My proposal (although I'm sure someone must have brought this up before, so it's more of a question) is why not take the magic away from seq by making it a class function like deepSeq class Seq a where seq :: a -> b -> b It is easily implemented in haskell by simply forces the constructor for the underlying data type (something also easily derivable by the compiler) instance Seq Int where seq' 0 y = y seq' _ y = y Now, unless I'm missing something, we have restore the strength of Haskell's parametricity properties map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs map' :: Seq a => (a -> b) -> [a] -> [b] map' f [] = [] map' f (x:xs) = x `seq'` f x : map f xs as the full range of operations that can be performed on universally quantified types (in addition to moving them around) is reflected in any explicitly and implicitly (through the dictionaries) passed functions over those types. Thanks! -Tyson

8 11

ANN: unix-bytestring: Unix/Posix-specific functions for ByteStrings.
by wren ng thornton 20 Mar '11

20 Mar '11

-------------------------------------------- -- unix-bytestring 0.3.2 -------------------------------------------- The unix-bytestring package offers a full selection of Unix/Posix-specific functions for reading and writing ByteStrings to Fds. -------------------------------------------- -- The Story Behind It All -------------------------------------------- A while back I needed a ByteString-based version of the System.Posix.IO String-based API. I coded up the new versions and submitted a patch to the unix package for adding them in[1]. But apparently, noone's much pleased with the System.Posix.IO API! In the ensuing discussion folks brought up their specific complaints and offered suggestions. So now, the couple of functions have become enough to release as its own package--- with the hope that one day it'll be rolled into the unix package. That's where you come in. The current API is more than good enough for anything I've needed, so I need your feedback on what you want from a ByteString-based Unix/Posix I/O library. I've looked through Roel van Dijk's reverse dependency analysis[2] to find the folks currently using the unix package. The maintainers of the following packages may be particularly interested in unix-bytestring: * HFuse * iteratee * iteratee-mtl * liboleg HFuse has complained about the lack of bindings for pread(2) and pwrite(2), which are included in unix-bytestring. The only standing complaint I haven't addressed is one expressed in the iteratee, iteratee-mtl, and liboleg packages which would prefer a return type of (Either Errno _) instead of throwing exceptions. [1] http://article.gmane.org/gmane.comp.lang.haskell.libraries/15390 [2] http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/package/unix -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unix-bytestring Darcs: http://community.haskell.org/~wren/unix-bytestring Haddock (Darcs version): http://community.haskell.org/~wren/unix-bytestring/dist/doc/html/unix-bytes… -- Live well, ~wren

1 0

cabal removeLink denied on Mac
by Ulrich Vollert 20 Mar '11

20 Mar '11

Hi, I installed the Haskell-Platform 2011.2.0.0 on my Mac with Mac OS X 10.6.6...and I am happy with it ;-) After some problems with directories and files under /private/var/folders, I get an error message whenever I try to use Cabal to install new packages. For instance: ................................................ cabal install sqlite Warning: The package list for 'hackage.haskell.org' is 28 days old. Run 'cabal update' to get the latest list of available packages. Resolving dependencies... Configuring sqlite-0.5.2... Warning: 'include-dirs: include' directory does not exist. Warning: 'hs-source-dirs: .' directory does not exist. cabal: Missing dependency on a foreign library: * Missing header file: sqlite3-local.h * Missing C library: sqlite3 This problem can usually be solved by installing the system package that provides this library (you may need the "-dev" version). If the library is already installed but in a non-standard location then you can use the flags --extra-include-dirs= and --extra-lib-dirs= to specify where it is. cabal: Error: some packages failed to install: sqlite-0.5.2 failed while unpacking the package. The exception was: /var/folders/Ks/Ks-bTCXtGXaCQnMtMuXr4k+++TI/-Tmp-/sqlite-0.5.23531/sqlite-0.5.2: removeLink: permission denied (Operation not permitted) ................................................ "cabal update" works without an error message but generates the warning that the package list is old....? I assume that there is a permission problem with /private/var/folders but I dont know how to fix it. Regards Ulrich

1 0

Proposal: making inits and tails less strict
by Bas van Dijk 18 Mar '11

18 Mar '11

Hello, I would like to propose making inits and tails less strict: inits :: [a] -> [[a]] -inits [] = [[]] -inits (x:xs) = [[]] ++ map (x:) (inits xs) +inits xs = [] : case xs of + [] -> [] + x:xs -> map (x:) (inits xs) tails :: [a] -> [[a]] -tails [] = [[]] -tails xxs@(_:xs) = xxs : tails xs +tails xxs = xxs : case xxs of + [] -> [] + _:xs -> tails xs Having a lazier inits allows the elegant: nats = map length (inits nats) which loops for the current definition. This definition was due to John Tromp: http://www.mail-archive.com/haskell@haskell.org/msg21044.html Discussion deadline: 2 weeks. Regards, Bas

7 9

cabal install cabal-install with the latest HP on Mac OS X
by Yitzchak Gale 15 Mar '11

15 Mar '11

I installed the 64-bit version of the recent Haskell Platform release on Mac OS X 10.6.6. $ cabal --version cabal-install version 0.10.2 using version 1.10.1.0 of the Cabal library As always in the past, and as cabal install itself has often suggested, the first thing I did was to run 'cabal install cabal-install' to make sure I have the latest version. To my surprise, cabal install began installing an *older* version of itself, together with older versions of dependent libraries to support that. I didn't really mind, because I could always just remove the symlink to the older-versioned cabal executable when it finished, so I let it run its course to avoid leaving a mess by aborting. However, after a while, the installation process failed with the message: Downloading time-1.1.4... <command line>: cannot satisfy -package Cabal-1.10.1.0: Cabal-1.10.1.0-6289829715de7a109def1f0c286a5dc4 is unusable due to missing or recursive dependencies: process-1.0.1.5-3e412eee765d141be15796c32f22f7a3 Note that process-1.0.1.5 and Cabal-1.10.1.0 are already installed globally as part of the platform. Another copy of process-1.0.1.5 had been installed in userland during this problematic run. Cabal-1.8.0.6 was also installed in userland. Why did cabal try to downgrade itself to an older version, and why did it get so confused while trying to do so? Thanks, Yitz

3 3

FFI with ABI instead of C declaration
by Maurício CA 14 Mar '11

14 Mar '11

Hi, all, I wonder: why, in Haskell and also in other languages like ML, FFI is done with C type and code as references? Since, ultimately, compiled code goes to, say, ELF files or (in Windows) DLLs, shouldn't foreign interfaces be consistent with those? I believe this could simplify writing foreign interfaces. Say, we could write something like this: foreign haskell_name1 binary_name1 :: T1 -> T2 -> IO T1 foreign haskell_name2 binary_name2 :: T1 -> T3 -> IO T4 Our FFI tool would take a set of binary libraries where to look for binary_name[i], and match haskell_name[i] with those. T[i] would be made synonyms of types which would offer all capabilities consistent with the corresponding types in those libraries ABIs. Inconsistency, of course, would be an error (like if, in the example above, the first parameter of both functions would not be the same). Thanks for your thoughts, Maurício

2 2