- Libraries - Haskell.org

Proposal: more general unionWith for Data.Map
by Christian Sattler 26 Jan '12

26 Jan '12

2012/1/24 Johan Tibell <johan.tibell(a)gmail.com> > > On Tue, Jan 24, 2012 at 9:35 AM, Christian Sattler > <sattler.christian(a)gmail.com> wrote: > > There are some high-level operations on maps which take two tree traversals > > only because the interface fails to expose sufficiently general functions. > > This proposal is concerned with an analogue of unionWithKey of type Ord k => > > (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a, with the intended > > semantics that if a key is present in both maps and the operation applied to > > the key and corresponding values returns Nothing, the key is deleted from > > the result. > > Is union really an appropriate name here? I expect the following to hold: > > forall k ∊ (keys m1) ∪ (keys m2) => k ∊ (m1 ∪ m2) > > This means that keys must not be deleted by the union operator. > Perhaps 'merge' is a better name. > > Cheers, > Johan I don't care much about the naming, but note that the analogous property already fails for the generalized intersectionWithKey in the development version.

5 11

Proposal: more general unionWith for Data.Map
by Christian Sattler 25 Jan '12

25 Jan '12

Hi all, There are some high-level operations on maps which take two tree traversals only because the interface fails to expose sufficiently general functions. This proposal is concerned with an analogue of unionWithKey of type Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a, with the intended semantics that if a key is present in both maps and the operation applied to the key and corresponding values returns Nothing, the key is deleted from the result. Example use: sparse vectors are represented as maps from indices to non-zero coordinates. Often, a highly sparse vector u needs to be a added to a rather dense sparse vector v, i.e. we have m << n where m and n are the counts of non-zero elements in u and v, respectively. I need this operation to be O(m + n) as well as O(m * log(n)), and it should be as efficient as reasonable possible. This seems like a straightforward use case for unionWith since its hedge-union algorithm guarantees O(m * log(n)). The only problem occurs when u[i] = x and v[i] = -x for some index i and non-zero x, resulting in a zero entry I would rather have deleted from the result (this is a common case when dealing with matrices with small integer entries). The same problems occurs for coordinate-wise vector multiplication over non-integral domains, this time with intersectionWith. Remarks: - It would align the types of unionWith and intersectionWith with differenceWith. - The concept of allowing operations with return type Maybe a to avoid an additional high-level operation is already expressed in functions like alter or mapMaybeWithKey. - It would enable an efficient implementation of symmetricDifference = unionMaybeWithKey (const Nothing). - This concerns Data.Map, Data.IntMap, Data.Set, Data.IntSet and the With[Key] versions of union/intersection/difference - At least for Data.Map.unionWithKey, modifying the existing implementation seems trivial, requiring a merge instead of a join in the new case. I apologize if some of these points have been brought up before. Christian

6 13

Broken Packages (and Maintainers) for poppler, hsc2hs
by Thomas DuBuisson 24 Jan '12

24 Jan '12

All, Sorry if I'm a bit bitter - just ran into breakage of poppler, hsc2hs, and zlib in a 20 minute stretch. If the maintainers are here: 1) Please set a proper e-mail address (one that isn't a protected ML). 2) Please at least make sure the installation works (or the file at least parses!) via cabal-install. Cheers, Thomas

2 1

Template Haskell: 'foo in patterns?
by Conal Elliott 24 Jan '12

24 Jan '12

If I understand correctly, 'foo, of type Name, is a constant value in any given context. And yet it doesn't appear to be allowed in patterns, thus leading to awkwardly explicit use of variables and equality guards in otherwise pattern-matching code. Are there reasons not to allow 'foo in patterns? -- Conal

2 1

Applicative instance for template haskell's Q
by Conal Elliott 23 Jan '12

23 Jan '12

Any reason not to add an Applicative instance for template haskell's Q (quoting) monad? - Conal

5 4

Proposal: add 'state' to the MonadState class
by Twan van Laarhoven 21 Jan '12

21 Jan '12

Hello list, Currently the 'state' function is only defined for the State type (aka StateT Identity): state :: (s -> (a, s)) -> State s a state f = StateT (Identity . f) But this function makes sense for all MonadState instances. I therefore propose to either add it to the MonadState class: class MonadState s m | m -> s where ... state :: (s -> (a,s)) -> m a state f = do s <- get let (a,s') = f s set s' return a or as a stand alone function like modify. I personally prefer to add it to the class, since that allows for a more efficient implementation. In particular: instance Monad m => MonadState s (StateT s m) where .... state = StateT (return . f) Discussion period: 2 weeks (ends October 10th) Twan

6 10

Efficent lens operation for Data.Map et al.
by roconnor＠theorem.ca 18 Jan '12

18 Jan '12

Using the existing interface to Data.Map it is impossible to implement efficent lenses for the structures. Right now, the implementation of mapLens et al. in data-lens must traverse the entire structure of the map twice: once to do a lookup and another to do an alteration. mapLens :: Ord k => k -> Lens (Map k v) (Maybe v) mapLens k = Lens $ \m -> store (\mv -> case mv of Nothing -> Map.delete k m Just v' -> Map.insert k v' m ) (Map.lookup k m) A native lensing operation would improve the situtation much. Two operations come close already: (1) alter comes close but doesn't return the lookup. (2) updateLookupWithKey comes even closer, however there is no way to insert a new key-value pair if the key isn't already in the map. So I propose adding a lens operation to the Data.Map (et al.) interfaces. Or, if you guys like warm-fuzzy names, we could call it alterLookup. lens :: k -> Map k a -> (Maybe a -> Map k a, Maybe a) with the specification that snd (lens k m) = lookup k m fst (lens k m) v = update (const v) k m The relationship between lens and alter is alter f k m = let (u,v) = lens k m in u (f v) In fact, every other Map update operation should be derivable from the lens function. I'm slowly working on a patch; however I thought I'd bring it up here on the mailing list in case some enterprising person who is familiar with these libraries wants to go ahead and implement it in Data.Map, Data.IntMap, Data.Set and Data.IntSet. -- Russell O'Connor <http://r6.ca/> ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''

4 14

Proposal: Overloaded Quotes for Template Haskell
by Michael D. Adams 18 Jan '12

18 Jan '12

(This was originally posted to haskell-cafe, but I've since learned that haskell-libraries is a more appropriate venue. Apologies for the resulting cross-post.) == Description == I would like to propose a generalization of the types of quote forms (i.e. "[| ... |]") and nested splices (i.e. "[| ... $( ... ) ... |]"). Currently quote forms have type "Q Exp" and nested splices expect their contents to have type "Q Exp". I propose that quote forms have type "forall m. Quasi m => m Exp" and nested splices expect a body of type "m Exp" where the "m" of the nested splice is the same as the "m" of the quote form that it is inside of. Top-level splices (i.e. those not inside a "[| ... |]") continue to expect their body to have type "Q Exp", and do *not* have a generalized to the type. (Otherwise, the compiler wouldn't know how to evaluate the monad. Nested splices do not have this problem as it is the responsibility of the user code between the splice and its enclosing quote to determine how to evaluate the monad.) Note that generalizing the types of quotes in this way is very similar to the generization of the types of strings that happens with the "-XOverloadedStrings" flag. However, unlike with strings which require an extra class (i.e. "IsString"), I believe generalizing quotes does not require an extra class. The already existing "Quasi" class is sufficient. An implementation could treat each quote or nested splice as mere syntactic sugar for an equivalent do-block, then use the usual type inference. == Example Use Case == I discovered a need for this generalization when writing a Template Haskell program in which part of it operates in a "StateT S Q a" monad instead of the usual "Q a" monad. The "S" type stores the state of a memoization table which contains code fragments already generated. Without memoization, the program would loop infinitely when processing certain recursive structures. It is fairly easy to declare an instance of "Quasi" for "StateT S Q", so that is not a problem. In order to keep the code clean, I'd like to use quotations with splices in them (i.e. [| ... $( ... ) ... |] ) for expressing the generated code. However, as quotations and splices are tied to the "Q" monad, I have to manually write "LamE ... VarP ... VarE ... etc." instead of using the much nicer quotation syntax. Without access to the quote syntax, I've had a one-line quotes turn into a half-a-dozen-line do-blocks. In this particular program, I can simulate the state monad using an IORef and lifting IO operations into Q using runIO. However, this merely a workaround. == Open Questions == ~~ Flags ~~ Generalizing the type of quotes can either be an "always-on" feature or it could be enabled by a flag (e.g. "-XOverloadedQuotes"). Since "Q" is an instance of "Quasi", we would expect programs that are type correct without the generalization to also be type correct with the generalization. Thus "always-on" would seem to be a backwards compatible change. However, while I am not an expert on GHC's type system, I suspect there are pathological cases where generalizing the types of quotes would result in the inference system not being able to infer a type that it would be able to without the generalization. In addition, type incorrect programs may yield more confusing type errors. I don't have a particular position on this question so long as the generalization is available (even if only by a flag) to those who want it. I suspect that, in the interests of design conservatism, having it as a flag will be the preferred choice. ~~ Quasi-Quotes ~~ The type of quasi-quoters (i.e. "String -> Q Exp") can be generalized to "forall m. Quasi m => String -> m Exp". However, this poses a compatibility program for existing user-written quasi-quoters. I am uncertain about the best way to handle this. It may be best to leave quasi-quoters without a generalized type unless someone can come up with a good backwards compatibility story. == Deadline == I propose the usual two week deadline (January 13) for discussion. If the overall response is positive, I'll submit a GHC Track ticket.

3 9

Add voidM to Control.Monad
by Jurriën Stutterheim 16 Jan '12

16 Jan '12

Hi all, I would like to propose adding the following function to Control.Monad to complement the `void` function: voidM :: Monad m => m a -> m () voidM m = m >> return () This function would be used to prevent warnings like Warning: A do-notation statement discarded a result of type Int. Suppress this warning by saying "_ <- bar", or by using the flag -fno-warn-unused-do-bind The (rather contrived) code below was used to generate the warning above: foo :: IO () foo = do bar return () bar :: IO Int bar = return 1 Using `voidM`, we can rewrite `foo` as such: foo' :: IO () foo' = do voidM bar return () after which no warning will be generated by GHC. Jurriën

6 8

[process] Fixed asynchronous exception bugs in readProcess and readProcessWithExitCode
by Bas van Dijk 13 Jan '12

13 Jan '12

Hi, I fixed two asynchronous exception bugs in readProcess and readProcessWithExitCode: 1) If an asynchronous exception was thrown to the thread executing readProcess/readProcessWithExitCode somewhere after createProcess was executed, the standard handles would not be closed anymore resulting in a "handle leak" so to speak. This is fixed by catching exceptions in the IO processing code and closing the standard handles when an exception occurs. Additionally, I also terminate the process and wait for its termination. Does the latter make sense? 2) If an asynchronous exception was thrown to the stdout/stderr-read-thread it did not execute the putMVar anymore resulting in a dead-lock when takeMVar was executed. This is fixed by properly catching exception in the read-thread and propagating them to the parent thread which will then handle them as described above. Regards, Bas

2 3