August 2014 - Libraries

Proposal: merge either into transformers
by Roman Cheplyaka 03 Jan '17

03 Jan '17

I propose to add the sole module of the 'either' package[1], Control.Monad.Trans.Either, to the transformers package. It provides EitherT, a very basic and fundamental data type. The difference between EitherT and ErrorT is that the latter has an Error constraint, which is used to imlement 'fail'. Note that 'either' depends on the 'semigroupoids' and 'semigroup' packages to provide appropriate instances. The proposal is not to add those instances to 'transformers' to avoid additional dependencies. The instances can then be left in the 'either' package or moved to the 'semigroupoids' and 'semigroup' packages respectively. ('semigroupoids' already depends on 'transformers', while 'semigroups' does not). Compared to the 'either' package, Show, Read, Eq and Ord instances will be dropped to keep the code Haskell2010 (those instances require FlexibleInstances, FlexibleContexts, and UndecidableInstances). The patch is attached. [*] [*] against transformers-0.3.0.0, because the darcs version is not buildable (Control/Monad/Signatures.hs is not in the repository). Roman

22 72

[containers] Proposal: Change to the Data.Map Monoid
by Nick Partridge 11 Oct '15

11 Oct '15

Hi, Currently the Monoid instance for Data.Map is implemented using union/unions, which are left biased. On key collision, it discards values from the right hand side of `mappend` - https://github.com/ghc/packages-containers/blob/bae098fb0a3994bc2b0ec331300… If you compare this with the Monoid for Maybe, it's like we're defaulting to First as the monoid instance for maps. A more useful instance, however very much a breaking change, would be to make the instance depend on a Monoid (or better yet, a Semigroup) for the values in the map: instance Monoid v => Monoid (Map k v) where mappend = unionWith mappend This lets us build up maps with values in a useful Monoid, and mappend them with gusto. Thoughts? - Nick Partridge Discussion period: 2 weeks.

15 22

Proposal: improve the Data.Tree API
by João Cristóvão 01 Jan '15

01 Jan '15

Hello, The Data.Tree API seems rather poor. Some research on hackage shows some additional functions being defined in very unrelated packages: http://hackage.haskell.org/package/debian-3.81/docs/Debian-Apt-Dependencies… http://hackage.haskell.org/package/hledger-lib-0.22.1/docs/Hledger-Utils.ht… I propose the addition of the following functions, that seem rather straigh forward to me: -- | get the sub-tree rooted at the first (left-most, depth-first) occurrence -- of the specified node value lookupTree :: Eq a => a -> Tree a -> Maybe (Tree a) -- | get the sub-tree rooted at the first (left-most, depth-first) value that -- matches the provided condition findTree :: (a -> Bool) -> Tree a -> Maybe (Tree a) -- | keep only the elements that match the provided condition filter :: (a -> Bool) -> Tree a -> Tree a The 'Tree' is appended in the name, to distinguish from the Foldable instances, that return the value, and not a sub-tree. Additionally, the following two functions might also be useful (even if the implementation is very simple in the second case): -- | get the sub-tree for the specified node value in the first tree in -- forest in which it occurs. lookupTreeInForest :: Eq a => a -> [Tree a] -> Maybe (Tree a) -- | Length of the tree length :: Tree a -> Int There are probably more useful functions to add, so suggestions are welcomed. Previous discussion: https://github.com/haskell/containers/issues/39#issuecomment-35799628 Discussion period: 2 weeks Cheers, João

12 35

Proposal: Add a strictly accumulating scanl' to Data.List
by David Feuer 28 Oct '14

28 Oct '14

Joachim Breitner wrote, in https://ghc.haskell.org/trac/ghc/ticket/9345#comment:6, a strictly accumulating version of scanl, to be named scanl'. I was initially concerned about its safety for fusion, but am now convinced of its correctness and believe it should be added to Data.List. scanl' :: (b -> a -> b) -> b -> [a] -> [b] scanl' f a bs = build $ \c n -> a `seq` a `c` foldr (\b g x -> (let b' = f x b in b' `seq` (b' `c` g b'))) (\b -> b `seq` n) bs a

3 3

Proposal: end lazy IO results with errors/exceptions
by David Feuer 10 Oct '14

10 Oct '14

Currently, withFile "foo" hGetContents >>= putStrLn prints out an empty line, the better to confuse newbies. I propose modifying the lazyRead function in GHC.IO.Handle.Text that currently reads lazyRead :: Handle -> IO String lazyRead handle = unsafeInterleaveIO $ withHandle "hGetContents" handle $ \ handle_ -> do case haType handle_ of ClosedHandle -> return (handle_, "") SemiClosedHandle -> lazyReadBuffered handle handle_ _ -> ioException (IOError (Just handle) IllegalOperation "hGetContents" "illegal handle type" Nothing Nothing) to something like lazyRead :: Handle -> IO String lazyRead handle = unsafeInterleaveIO $ withHandle "hGetContents" handle $ \ handle_ -> do case haType handle_ of ClosedHandle -> return (handle_, error "Forcing the result of a lazy read led to an attempt to read from a closed handle.") SemiClosedHandle -> lazyReadBuffered handle handle_ _ -> ioException (IOError (Just handle) IllegalOperation "hGetContents" "illegal handle type" Nothing Nothing) Ideally that error should instead be something to throw an imprecise exception, but I don't know how to use those yet. I can't personally see a way for this to break sane, working code, but the folks on #ghc thought it should be discussed and debated on list. David Feuer

10 12

Removing MonadFail from Monad
by David Luposchainsky 03 Oct '14

03 Oct '14

Hey everyone, I feel like there are a couple of elephants in the room that are sort of important but nobody really addresses them directly. One of them was what became the AMP, and `fail` is another one. I resurrected and refurbished this proposal from a 6 month old Gist because there seemed to be some interest/talk going on in the form of side remarks in other discussions here. The sun shines, let's make some hay! The proposal text can be found at the end of this text (for the mailman archives), or in pretty HTML here: https://github.com/quchen/articles/blob/master/monad_fail.md Although this will technically a language-level change, the impact will mainly be a library and fail-safety detail. For this reason I think this mailing list is more suitable than other more specialized lists. Greetings, David/quchen PS: I would have chosen Fail Removal Proposal so we have a new buzzword, but unfortunately it does not abbreviate well. Call it the "fail of Haskell issue"? ;-) Removing `fail` from `Monad` ============================ The problem ----------- Currently, the `<-` symbol is desugared as follows: ```haskell do pat <- computation >>> let f pat = more more >>> f _ = fail "..." >>> in computation >>= f ``` The problem with this is that `fail` cannot be sensibly implemented for many monads, for example `State`, `IO`, `Reader`. In those cases it defaults to `error`, i.e. the monad has a built-in crash. `MonadFail` class ----------------- To fix this, introduce a new typeclass: ```haskell class Monad m => MonadFail m where fail :: String -> m a ``` Desugaring is then changed to the following: ```haskell -- Explicitly irrefutable pattern: do not add MonadFail constraint do ~pat <- computation >>> let f pat = more more >>> in computation >>= f -- Only one data constructor: do not add MonadFail constraint do (Only x) <- computation >>> let f (Only x) = more more >>> in computation >>= f -- Otherwise: add MonadFail constraint do pat <- computation >>> let f pat = more more >>> f _ = fail "..." >>> in computation >>= f ``` Discussion ---------- - Although for many `MonadPlus` `fail _ = mzero`, a separate `MonadFail` class should be created. A parser might fail with an error message involving positional information, and for STM failure is undefined although it is `MonadPlus`. - The case of one data constructor should emit a warning if the data type is defined via `data`: adding another data constructor can make patterns in unrelated modules refutable. - Some monads use the pattern matching to force evaluation of the binding, for example lazy/strict `StateT`. I'm not sure what exactly the consequences of the above are here; I suspect a strictness annotation or `(>>=)` instead of `do` notation might be sufficient. - Getting the change to work should be boring but painless: all Monad instance declarations involving `fail` will break because the function is removed, and many monadic computations have to be annotated using `~` because they were written under the assumption that `fail` is never called. In both these cases compilation errors/warnings carry sufficient information to fix the source code easily. - Backwards compatibility with many old modules will be broken; I don't see a way around this. Other things to consider ------------------------ - Rename `fail`? It's quite a generic name that would be nice to have in APIs. `failM`? `mfail`? - Remove the `String` argument? (May hurt error reporting on pattern mismatch ..?) - How sensitive would existing code be to subtle changes in the strictness behaviour of `do` notation pattern matching? Applying the change ------------------- Like the AMP, 1. Implement ad-hoc warnings that code will receive a `MonadFail` constraint in a future version. "Either make the patterns irrefutable, or keep in mind that the next compiler version will require a `MonadFail` instance". Since `MonadFail` does not clash with an existing name, it could be introduced to `Control.Monad` right away. 2. Do the switch.

9 11

Proposal: (breaking change to avoid fragile breakage) change the definition of foldr2, zip, and zipWith
by David Feuer 01 Oct '14

01 Oct '14

BACKGROUND TRAC: #9495 GHC's definition of foldr2 violates the spec of the Haskell Report, making some programs less defined than they should be, and does so in a way that is quite fragile, dependent on a number of different factors—that is, it is likely hard to debug. Details: The current "baseline" definition of foldr2 (before rewrite rules) does what the Report requires: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] _ys = z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) There are two rewrite rules, foldr2/left and foldr2/right, designed to allow foldr2 to fuse with build appearing in either the first or second list argument. foldr2/left is perfectly safe (as long as the build argument is legitimate). foldr2/right is not, as comments in the source partially explain. The problem shows up if you have something shaped like zip [1,7,42,5] (1:8:4:11:undefined) but where the second list (ending in undefined) is actually produced using build, and GHC chooses to fuse foldr2 with it. The Report requires the above to produce [(1,1),(7,8),(42,4),(5,11)], but GHC will instead produce (1,1):(7,8):(42,4):(5,11):_|_ This issue can make a program that works with -O0 fail with -O, and can cause fragility depending on exactly what fuses. SCOPE One obvious question is what kinds of build forms can cause problems. Many, like map and fromEnumTo, don't have enough power to be likely to cause trouble. Joachim Breitner, however, realized that the current implementation of filter has enough power to break things. So here's a complete example of code that will break with -O but not with -O0: {-# NOINLINE don'tFuse #-} don'tFuse = id p x = 100 `mod` x < 20 main = print $ zip (don'tFuse [10,9..1]) (filter p [10,9,..]) Things will only get worse if I succeed in my plan to bring unfoldr into the framework. SOLUTIONS 1. One solution, of course, is to eliminate unfoldr2/right, bringing GHC into compliance with the Report. I really like this idea, but Joachim thinks it is not worth the potential performance impact on code written before or without regard for the change. We both agree that a reasonable alternative is 3. Modify the baseline definition of unfoldr2 as follows: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] ys = ys `seq` z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) This should, we believe, make the baseline definition fail where the one fused by foldr2/right would fail, giving consistent semantics. WHAT MIGHT BREAK Code that currently works but will break with this change has two properties: 1. It relies on the asymmetry in foldr, zipWith, or zip to avoid running into bottom. 2. foldr2/right does not fire, either because the second list is not a good producer or because GHC applies the foldr2/left rule instead. That is, most of the code that this change will break is fragile under the current scheme. DISCUSSION PERIOD Standard two weeks.

3 4

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

17 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

Re: Formal proposal: replace Data.List.inits
by David Feuer 07 Sep '14

07 Sep '14

Minor errors in copying/memory: initsHO = map ($[]) . scanl q id where q f x = f . (x :) On Sun, Jul 20, 2014 at 2:03 AM, David Feuer <david.feuer(a)gmail.com> wrote: > As previously discussed, Data.List.inits has terrible performance: > something as simple as > > print $ length $ inits [100000] > > will take an absurdly long time. The simplest decent improvement seems to be > > initsHO = map ($[]) . scanl q [] > where > q f x = f . (q :) > > A slight transformation of this by Andrew Seniuk (rasfar on #haskell) > gives the slightly faster > > initsR = map reverse . scanl (flip (:)) [] > > As Henning Thielemann and Edward Kmett pointed out, these perform > poorly when calculating things like `map head $ drop 100000 $ inits > [100050]` because the costs of the reverses or compositions are > monolithic and unshared. Edward Kmett pointed out that this could > probably be fixed by using a queue (although he isn't sure it's worth > doing so). As it turns out, it can, and with only a trivial penalty in > other cases. The following uses a stripped-down partial implementation > of Okasaki's banker's queue (see the attached file for a version with > explanatory comments as well as the benchmark code): > > import Data.Bits (popCount) > import Data.Word (Word) > > data Queue a = Queue {-# UNPACK #-} !Word [a] [a] > > queue :: Word -> [a] -> [a] -> Queue a > queue lp1 f r > | popCount lp1 /= 1 = Queue lp1 f r > | otherwise = Queue lp1 (f ++ reverse r) [] > > emptyQ :: Queue a > emptyQ = Queue 1 [] [] > > snocQ :: Queue a -> a -> Queue a > snocQ (Queue lp1 f r) x = queue (lp1 + 1) f (x:r) > > toListQ :: Queue a -> [a] > toListQ (Queue _ f r) = f ++ reverse r > > initsQ :: [a] -> [[a]] > initsQ = map toListQ . scanl snocQ emptyQ > > > This implementation appears to take care of the performance wrinkle in > initsR and initsHO, while being only very slightly slower in other > contexts. It's longer, certainly, but it's not long. > > I have attached the Criterion report produced by the attached program > comparing initsR to initsQ. Previous tests definitively showed that > initsHO is a small constant factor worse than initsR, and > Data.List.inits is incomparably worse, so I limited this round to > initsR and initsQ. > > I therefore propose that we should replace the current implementation > of inits with initsQ, the queue-based one, unless someone comes up > with something faster and/or simpler very soon.

4 10

Discussion: Why is inet_addr in IO?
by Edward Kmett 01 Sep '14

01 Sep '14

inet_addr doesn't do any lookups, it is basically a glorified parsing problem converting from a string to a host address. http://hackage.haskell.org/package/network-2.6.0.1/docs/src/Network-Socket.… Why, beyond the obvious implementation details, does it live in IO? Given that the current version lives in IO, should there be a version that is obviously made pure so that folks who want to use it directly can do so without having to bury it behind an unsafePerformIO? This isn't a concrete proposal at this time, but more an attempt to sound out if such a proposal should be formed. -Edward

9 10