February 2012 - Libraries

Proposal: Use time rather than old-time in directory
by Ian Lynagh 16 Sep '14

16 Sep '14

Hi all, This proposal is to change directory to use the time package rather than the old-time package. This will hopefully be a significant step towards actually making the transition in general. I'm not sure if POSIXTime or UTCTime is the better type to use. Does anyone know? I started off with UTCTime, then switched to POSIXTime as UTCTime didn't have a Show instance. I've since found that actually UTCTime has both Show and Read instances, but they are orphaned. So actually, if UTCTime is the better type then switching back to UTCTime would allow us to fix this comment in hpc: -- We would rather use ClockTime in Mix, but ClockTime has no Read instance and simplify the code slightly. Attached are patches for directory, hpc and ghc. Suggested discussion period: Until 5th Nov 2011. Thanks Ian

14 35

Changes to Typeable
by Simon Peyton-Jones 26 Nov '12

26 Nov '12

Friends (Ian pointed out that I should have sent this to the libraries list): The page describes an improved implementation of the Typeable class, making use of polymorphic kinds. Technically it is straightforward, but it represents a non-backward-compatible change to a widely used library, so we need to make a plan for the transition. http://hackage.haskell.org/trac/ghc/wiki/GhcKinds/PolyTypeable Comments? You can fix typos or add issues directly in the wiki page, or discuss by email Simon

25 54

Proposal: Add newUniqueSTM to Data.Unique
by Edward Kmett 27 Apr '12

27 Apr '12

Data.Unique's newUnique uses atomically internally to update a TVar. Consequently attempting to "unsafeIOToSTM newUnique" to allocate a Unique within an STM transaction blows you sky high. The proposal is to split the definition of newUnique into: newUnique = atomically newUniqueSTM and expose newUniqueSTM. Alternately, since bug #3838 has been resolved, we could revert to using an IORef, which would avoid the wart of having us have an overtly IO action detonate because of an internal implementation detail of using STM. Since, there are two paths forward, I haven't put forward a patch, but wanted to open a discussion. Discussion Period: 2 weeks. -Edward Kmett

6 12

documentation patch for process
by Evan Laforge 16 Apr '12

16 Apr '12

I recently burned some time because I didn't realize that System.Process.createProcess doesn't report when the binary isn't found. I guess I was used to that behaviour from python's subprocess module, which goes to some effort to report the error from the fork()ed child when exec() fails. After a failed solution, I did some poking around in the source to see exactly what haskell's process does. In the interests of saving someone else that time, I submit a patch to process to add some documentation. I'm not sure how to do a 'darcs send' with git, but here's the patch: % git log | head commit 5a46937961b3400fa58ccffc785d0de8c1c01d94 Author: Evan Laforge <qdunkan(a)gmail.com> Date: Wed Feb 8 13:25:16 2012 -0800 More detailed haddock for createProcess: document what happens if the binary is not found commit c8b30a6f1d493ab724f2da05dbc49496b119a051 Author: Simon Marlow <marlowsd(a)gmail.com> Date: Mon Jan 16 16:25:34 2012 +0000 % git diff HEAD\^ diff --git a/System/Process.hs b/System/Process.hs index f3a8f9b..a372228 100644 --- a/System/Process.hs +++ b/System/Process.hs @@ -234,9 +234,18 @@ To create a pipe from which to read the output of @ls@: To also set the directory in which to run @ls@: > (_, Just hout, _, _) <- -> createProcess (proc "ls" []){ cwd = Just "\home\bob", +> createProcess (proc "ls" []){ cwd = Just "/home/bob", > std_out = CreatePipe } +Note that this does /not/ throw an error if the binary is not found, +or not executable. Instead, the process will fail with the exit code 127. +But you can't rely on it failing quickly, because it may e.g. hang up +searching the PATH on a slow NFS mount. Since there's no way to tell when +the exec() has succeeded, the only way to reliably know if the createProcess +failed is to 'waitForProcess'. + +If the CreateProcess record's 'cwd' directory doesn't exist, the exit code +will be 126. -} createProcess :: CreateProcess diff --git a/System/Process/Internals.hs b/System/Process/Internals.hs index 11de1f4..2a6c047 100644 --- a/System/Process/Internals.hs +++ b/System/Process/Internals.hs @@ -199,7 +199,8 @@ data CmdSpec = ShellCommand String -- ^ a command line to execute using the shell | RawCommand FilePath [String] - -- ^ the filename of an executable with a list of arguments + -- ^ The filename of an executable with a list of arguments. + -- The PATH is searched for the executable. data StdStream = Inherit -- ^ Inherit Handle from parent

2 3

Proposal: System.Environment.getEnv should return Maybe
by Evan Laforge 14 Mar '12

14 Mar '12

It's awkward and surprising how getEnv throws an exception when an env var is not set, since it's very common for env vars to be optional, and it's not convenient to catch exceptions in haskell (I have to look up Control.Exception every time, and then add LANGUAGE ScopedTypeVariables). I wind up using 'fmap lookup k Environment.getEnvironment' instead. So I propose a function: lookupEnv :: String -> IO (Maybe String) Then getEnv can be deprecated and eventually removed. Or maybe not if people want to argue the current getEnv is useful and deprecation warnings would be too annoying. Yeah, it's a trivial thing, but it's nice to sand off some of these rough edges. Discussion: 2 weeks, March 7

16 20

Re: Proposal: System.Environment.getEnv should return Maybe
by John Lato 13 Mar '12

13 Mar '12

> From: Jon Fairbairn <jon.fairbairn(a)cl.cam.ac.uk> > > Brandon Allbery <allbery.b(a)gmail.com> writes: > >> On Wed, Feb 22, 2012 at 18:51, John Meacham <john(a)repetae.net> wrote: >> >>> On Wed, Feb 22, 2012 at 3:05 PM, Evan Laforge <qdunkan(a)gmail.com> wrote: >>> > It's awkward and surprising how getEnv throws an exception when an env >>> > var is not set, since it's very common for env vars to be optional, >>> > and it's not convenient to catch exceptions in haskell (I have to look >>> >>> For true IO exceptions, you should be using the Prelude.catch mechanism. >>> >> >> This still assumes that it's an exceptional condition that is being >> modeled. It is not; it is correctly modeled as a Maybe. > > +1. And it?s always irritated me that read at EOF raises an > exception. Files having ends is not exceptional! (This is partly > addressed by iteratees, I imagine, but I haven?t found time to > get my head round those yet.) This irritates me too; I don't think that Haskell exceptions should be used for much of anything, exceptional condition or not. +1 for the proposal. Also, the unix-bytestring package (http://hackage.haskell.org/package/unix-bytestring) exposes IO functions that don't raise exceptions at EOF. John L.

5 8

Proposal: add 'findLess' and variants to containers
by Twan van Laarhoven 04 Mar '12

04 Mar '12

Hello all, == Overview == I have several times needed functions to find items less than a given key in a container. So I propose we add these to the containers library: -- | /O(log n)/. -- Find the largest element in the set that is @<@ the query. findLess :: Ord a => a -> Set a -> Maybe a -- | /O(log n)/. -- Find the largest element in the set that is @<=@ the query. findLessEqual :: Ord a => a -> Set a -> Maybe a -- | /O(log n)/. -- Find the smallest element in the set that is @>@ the query. findGreater :: Ord a => a -> Set a -> Maybe a -- | /O(log n)/. -- Find the smallest element in the set that is @>=@ the query. findGreaterEqual :: Ord a => a -> Set a -> Maybe a And for Maps: findLess, findLessEqual, findGreater, findGreaterEqual :: Ord a => a -> Map a b -> Maybe (a,b) As well as the equivalent functions for IntSet and IntMap. == Previous proposal and related functions == There was a previous proposal to add such functions about two years ago [1]. That proposal died due to concerns over adding related 'delete' and 'update' functions, and that the API would become too large. I think the 'find' functions should be added regardless of whether we also add 'update' and 'delete' variants. On the other hand, for consitency it would be better to also add 'deleteLess', etc. We should perhaps mimic the findMin/findMax functions. The only issue with that idea is that findMin does not return a Maybe, but rather fails for an empty container. I think that not returning its result in a Maybe would make the findLess useless in practice, since there is no such easy precondition for findLess. As for the API size: This proposal would add a lot of functions to Data.Map and Data.Set (especially when we also include 'update' and 'delete' variants). However, the mental burden of these new functions is not so large. Library users already know what 'find', 'update' and 'delete' mean. Moreover, there is a nice symmetry between the 4 different conditions, which means that you can almost think of them as one thing. == Bikeshedding / naming == There are several possible names for these functions: 1. findLess / findLessEqual / findGreater / findGreaterEqual 2. findMaxLT / findMaxLE / findMinGT / findMinGE 3. findLower / findFloor / findHigher / findCeiling I personally prefer either 1 or 2. To me option 3 (which Java uses) is very confusing. == Implementation == These functions can be implemented in terms of split, but it is a pain (and error prone) to do so: findLess a m = findMax' (fst (split a m)) findLessEqual a m = case splitLookup a s of (_,Just b,_) -> Just (a,b) (m',Nothing,_) -> findMax' m' findGreater a m = findMin' (snd (split a m)) findGreaterEqual a m = case splitLookup a m of (_,Just b,_) -> Just (a,b) (_,Nothing,m') -> findMin' m' where findMin' = fmap fst . minViewWithKey findMax' = fmap fst . maxViewWithKey This is really something that shouldn't have to be done by users of the library. And we might also be able to come up with a more efficient implementation. == Discussion period == Discussion deadline: 2 weeks from now; Sunday, 26 February 2012. Twan [1] http://www.haskell.org/pipermail/libraries/2010-February/013060.html continued here: http://www.haskell.org/pipermail/libraries/2010-March/013062.html

9 17

Functor instance for Set?
by Daniel Gorín 01 Mar '12

01 Mar '12

Hi I was always under the impression that the fact that Data.Set.Set can not be made an instance of Functor was a sort of unavoidable limitation. But if we look at the definition of Data.Set.map: map :: (Ord a, Ord b) => (a->b) -> Set a -> Set b map f = fromList . List.map f . toList we see that 1) "Ord a" is not really used and 2) "Ord b" is only needed for the final fromList. Since every interesting function in Data.Set requires an Ord dictionary anyway, one could implement fmap using only the "List.map f . toList" part and leave the "fromList" to the successive function calls. It appears to me, then, that if "Set a" were implemented as the sum of a list of a and a BST, it could be made an instance of Functor, Applicative and even Monad without affecting asymptotic complexity (proof of concept below). Am I right here? Would the overhead be significant? The one downside I can think of is that one would have to sacrifice the Foldable instance. Thanks, Daniel import qualified Data.Set as Internal import Data.Monoid import Control.Applicative data Set a = This (Internal.Set a) | List [a] toInternal :: Ord a => Set a -> Internal.Set a toInternal (This s) = s toInternal (List s) = Internal.fromList s toAscList :: Ord a => Set a -> [a] toAscList (This s) = Internal.toAscList s toAscList (List s) = Internal.toAscList $ Internal.fromAscList s toList :: Set a -> [a] toList (This s) = Internal.toList s toList (List s) = s -- Here we break the API by requiring (Ord a). -- We could require (Eq a) instead, but this would force us to use -- nub in certain cases, which is horribly inefficient. instance Ord a => Eq (Set a) where l == r = toInternal l == toInternal r instance Ord a => Ord (Set a) where compare l r = compare (toInternal l) (toInternal r) instance Functor Set where fmap f = List . map f . toList instance Applicative Set where pure = singleton f <*> x = List $ toList f <*> toList x instance Monad Set where return = pure s >>= f = List $ toList s >>= (toList . f) empty :: Set a empty = This Internal.empty singleton :: a -> Set a singleton = This . Internal.singleton insert :: Ord a => a -> Set a -> Set a insert a = This . Internal.insert a . toInternal delete :: Ord a => a -> Set a -> Set a delete a = This . Internal.delete a . toInternal instance Ord a => Monoid (Set a) where mempty = This mempty mappend (This l) (This r) = This (mappend l r) mappend l r = This . Internal.fromAscList $ mergeAsc (toAscList l) (toAscList r) where mergeAsc :: Ord a => [a] -> [a] -> [a] mergeAsc [] ys = ys mergeAsc xs [] = xs mergeAsc ls@(x:xs) rs@(y:ys) = case compare x y of EQ -> x : mergeAsc xs ys LT -> x : mergeAsc xs rs GT -> y : mergeAsc rs ys

4 7

ReadP and choice
by Ian Lynagh 26 Feb '12

26 Feb '12

Hi all, The code below defines a ReadP parser which can parse either a keyword "wrapper" or an arbitrary identifier. I was hoping that it would give the output (CWrapper1,"") (CWrapper2,"") (CFunction "wrapper","") but it actually gives (CWrapper2,"") (CFunction "wrapper","") (CWrapper1,"") i.e. completed parses are returned before the parse that needs to "look" at the remaining input. I can see the logic behind the current behaviour, but in this case at least it's quite inconvenient. What do you think? Did I miss a better way to solve the problem? Should the behaviour be changed? If so, is changing it easy? import Data.Char import Control.Applicative ((<$>)) import Text.ParserCombinators.ReadP as ReadP main :: IO () main = mapM_ print test test :: [(CImportSpec, String)] test = readP_to_S parse "wrapper" where parse = do r <- choice [ token "wrapper" >> return CWrapper1, string "wrapper" >> return CWrapper2, CFunction <$> many1 (satisfy isAlpha) ] eof return r token str = do _ <- string str toks <- look case toks of c : _ | isAlpha c -> pfail _ -> return () data CImportSpec = CFunction String | CWrapper1 | CWrapper2 deriving Show Thanks Ian

2 1

Vector memory usage
by Ben Gamari 24 Feb '12

24 Feb '12

Recently I stumbled upon a rather non-obvious behavior in what seems like a fairly common use a vector[1]. It appears that, despite the claim of the documentation, dropWhile can result in copies, resulting in a 1MB vector ballooning to several gigabytes within a few seconds. This has been reproduced with ghc 7.4.1 and 7.0.3 with -O and -prof. My knowledge of the internals of vector is quite limited, so I'll leave potential explanations to those with better understanding; below I've attached some relevant discussion from #haskell. Let me know if there's anything at all I could do to help. Cheers, - Ben [1] http://hackage.haskell.org/trac/ghc/ticket/5893 Test case: import qualified Data.Vector.Unboxed as V type Time = Int spansPhotons :: V.Vector Time -> [(Time,Time)] -> [V.Vector Time] spansPhotons ts spans = map (\(start,_)->V.takeWhile (<start) ts) spans main = do let times = V.generate 1000000 (*100) spans = [(10000*i, 10000*i+5000) | i <- [1..10000]] let bursts = spansPhotons times spans print $ sum $ map V.length bursts print $ map (const 1) $ bursts 00:16 < rwbarton> there the problem is that the bursts aren't sharing the same memory 00:17 < rwbarton> like they would if you wrote a similar program with ByteString 00:17 < rwbarton> the thing is that the Vector implementation of dropWhile is good for the stream fusion situation where you have a pipeline of operations 00:17 < quintessence> Yeah, I don't think dropWhile can participate in stream fusion and not copy 00:18 < rwbarton> but not good when you want to dropWhile many different times on the same input 00:18 < rwbarton> right 00:18 < quintessence> because when you have dropWhile p . map f the thing you want to share with doesn't exist 00:18 < rwbarton> so I don't know what the resolution would be 00:18 < bgamari> ouch 00:18 < rwbarton> besides giving some more manual control over stream fusion perhaps 00:19 < bgamari> Yep 00:20 < bgamari> That is a tricky one 00:20 < dmwit> dropWhileFusable + dropWhileCopy 00:20 < dmwit> err... 00:21 < dmwit> dropWhileFusable + dropWhileDoesn'tCopy, I guess 00:21 < quintessence> Could you implement dropWhile the non-fusing way and then have a RULE for dropWhile p . unstream = unstream . S.dropWhile p? 00:21 < rwbarton> at the least you could implement dropWhile' the non-fusing way; maybe that already exists somewhere in Data.Vector 00:21 < tibbe> Isn't there a function to explicitly copy? Like ByteString's clone? 00:21 < rwbarton> there is 00:21 < rwbarton> but the goal here is to not copy 00:22 < tibbe> I'm joining this discussion late I'm afraid :) 00:22 < tibbe> it should be possible to write rules that only fire when fusion doesn't happen 00:22 < rwbarton> the issue is a program like http://hpaste.org/64262#a64263 ends up allocating a bunch of nonoverlapping vectors 00:22 < tibbe> they could do sharing, but the performance model might turn out to be confusing 00:22 < rwbarton> when it could share them (and the documentation would have you believe it does) 00:23 < tibbe> how would you document dropWhile? Might share the underlying vector? 00:23 < bgamari> tibbe: the performance model is already a bit confusing ;) 00:23 < tibbe> :) 00:24 < bgamari> I'm surprised I'm the first person to encounter this 00:25 < bgamari> The bug report is http://hackage.haskell.org/trac/ghc/ticket/5893#comment:1 00:29 < bgamari> rwbarton, Do you mind if I quote you in a message to libraries@?

2 1