October 2014 - Libraries

Re: Proposal: Make a very slight change to the semantics of Data.List.isSuffixOf
by David Feuer 14 Oct '14

14 Oct '14

On Oct 14, 2014 9:05 AM, "Kim-Ee Yeoh" <ky3(a)atamo.com> wrote: > > David, > > To paraphrase Kernighan, ascertaining correctness is twice as hard as writing a program in the first place. So if you're as clever as possible with your code, how will you know it's even correct? I think we have different senses of what is easy to understand. We're all working on modifications of Andreas Abel's "naive" approach. I don't think the Reid Barton/Kim-Ee Yeoh modification is easier to understand than the David Feuer/Milan Straka one. In particular, your approach makes the weird long needle/short haystack case implicit, dumping it into the equality test. I also think the principle of least (bad) surprise applies: I wouldn't *expect* an overly long needle to be traversed in full and then the elements compared. > Case in point: the infinite lists wrinkle that you started the thread with. /At a glance/ what do the general recursion versions (yours and Milan's) evaluate to on infinite lists? I can't undo my understanding and say what I would have thought. But it's certainly a whole lot easier to understand than, say, the `permutations` or `sort` functions, and I could easily add two or three lines of explanation that would guide anyone to a correct interpretation. > What are the benchmarks on the time it takes for a haskell programmer to figure them out? Would they not jump at the greater affordance of reasoning with Andreas's compositions? Let me know when the benchmarks and experimental results are in. Don't forget to get IRB approval for human trials. > Meaning and reasonableness have always been the hallmarks of core libs. I think we have an honest disagreement hear about what is "reasonable". I think it's unreasonable for [undefined, undefined] `isSuffixOf` [undefined] to be undefined, but you see it differently. > Least of all, since it's so losering to benchmark the wrong thing, see below on how Andreas-dropl no.1 beats out David-Milan by the tiniest sliver in short-needle-long-haystack. Like checking file extensions in pathnames that we saw in Andreas's Agda code. The "long haystack" benchmark I used is actually much, much longer than a path name. My "short needle, short haystack" example is the one designed to test the pathname extension performance. > Here a concrete app brings real meaning to the timings as opposed to optimizing for vaporware. Watch them Agdaists fall off their chairs when they hit the speed boost. ;)

1 0

Discussion: Add safeWithFile function
by David Feuer 13 Oct '14

13 Oct '14

Some care is required to use withFile properly with lazy IO, and people sometimes get it wrong. In some cases, readFile is a suitable replacement. In other cases, however, it may be necessary to ensure the file gets closed in a timely manner, and it may not be necessary to read the whole file. The following seems to do the trick: safeWithFile :: (NFData a) => String -> IOMode -> (Handle -> IO a) -> IO a safeWithFile name mode f = withFile name mode $ f >=> (return $!!) Sample use: *SafeWithFile> safeWithFile "SafeWithFile.hs" ReadMode hGetContents >>= putStr module SafeWithFile (safeWithFile) where import Control.DeepSeq import System.IO import Control.Monad safeWithFile :: (NFData a) => String -> IOMode -> (Handle -> IO a) -> IO a safeWithFile name mode f = withFile name mode $ f >=> (return $!!)

6 10

Optimizing isSuffixOf (was Re: Proposal: Make a very slight change to the semantics of Data.List.isSuffixOf)
by Kim-Ee Yeoh 11 Oct '14

11 Oct '14

On Fri, Oct 10, 2014 at 4:18 PM, Jon Fairbairn <jon.fairbairn(a)cl.cam.ac.uk> wrote: > That seems rather wordy to me. Can we get anywhere starting with > > a `isSuffixOf` b = a `elem` tails b > > and transforming? Is it only about wordiness & syntax? With the original a `isSuffixOf` b = reverse a `isPrefixOf` reverse b and with Jon's a `isSuffixOf` b = a `elem` tails b I'm completely convinced of the correctness, modulo that of the referenced functions. Moreover, the conviction was obtained cheaply. My finite neurons are saved for the greater task at hand. The proposal on the table snatches away that providence. I have to take it on the authority of others that it's correct. Rust recently exposed a bug in their string matching function. It's their version of Data.List.isInfixOf. See http://www.wabbo.org/blog/2014/22aug_on_bananas.html These days I point all my colleagues and friends to this article as a classic case of premature optimization. But I understand that some folks prefer their computations always rapid, if sometimes wrong. David, is there an application underlying the need for isSuffixOf speed? You might want to look into the ByteString libraries for your optimization efforts. Over there, performance is several notches up in priority. -- Kim-Ee

1 0

Re: [core libraries] List of core libraries
by Neil Mitchell 10 Oct '14

10 Oct '14

> Btw, I'm a bit wondering, why do you think the testsuite's failure won't > mark the Travis-CI build as failed? :) It's a bit hard to know for sure, but my logic is: * https://github.com/haskell/filepath/blob/master/tests/AutoTest.hs#L38 means that the output of the QuickCheck test doesn't cause an exception (as it originally was), but just prints a message about failure * The travis doesn't look at https://github.com/haskell/filepath/blob/master/tests/filepath.stdout So Travis doesn't check the test won't be broken by GHC, and I think without that check it doesn't spot failures. (That's my chain of reasoning, but it's all a little subtle, so could quite easily be wrong!) > I'd suggest to simply add you to the maintainer-team for filepath on > https://github.com/haskell/filepath/ if that's ok for you (in fact, I've > just added you in just in case) Great. >> * What's the integration with GHC? Does the filepath module get pulled >> directly into GHC source trees? I see it's in the GHC test suite - is >> that considered a good idea? > > it's a submodule in ghc.git, and we have an automatic mirroring job > mirroring to git.haskell.org/packages/filepath.git > > And from time to time, we'd update the commit ghc.git points to inside > filepath.git; so you can freely push to master on > https://github.com/haskell/filepath w/o affecting GHC HEAD, only when we > update the filepath gitlink we'd see the effect of it in GHC HEAD. Perfect. I'm sure I'll do something incompatible with the GHC world at some point, but just shout at me when I do (or, if there happens to be a list of the most likely stupid things I might do, let me know). > I think this is mostly a historic artefact, as something Travis wasn't > around when filepath started being used by GHC. Cabal was barely around when filepath started being used by GHC... Cabal test was at least one incompatible iteration as well. > Do you have the means to test filepath on all GHC tier-1 > platforms/archs? (That's the only benefit I currently see with having > the tests as part of GHC's validation testsuite) No, that's valuable, and certainly makes it work keeping. Thanks, Neil

1 0

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

Re: [core libraries] List of core libraries
by Neil Mitchell 09 Oct '14

09 Oct '14

I did semi-hand the filepath library over to the Core libraries committee, it was just about 6 years before the committee formed so you probably don't have records of it, which is why libraries@ is listed as the author. I'm happy to take a more active role in maintaining it. In particular, I was intending to review/comment on https://github.com/haskell/filepath/pulls, and have the intention to add a bunch of patches (https://github.com/ndmitchell/shake/issues/174) Most of the patches are either obviously a good idea (fixing broken code) or improving the docs. The only one which could have any debate surrounding it is the introduction of a new operator -<.>. I don't want to debate that now, but it would be good to get clarification as to whether I should unilaterally add it, or should go through the libraries submission process, or ... Thanks, Neil On Tue, Sep 30, 2014 at 4:17 PM, Andrew Gill <andygill(a)ku.edu> wrote: > All, > > I’ve not touched hoc for quite a while. KU now has the resources to take > ownership, if needed. It’s pretty stable, from what I understand, but could > do with the an updated manual. > > Andy Gill > > On Sep 28, 2014, at 1:45 PM, Edward Kmett <ekmett(a)gmail.com> wrote: > > Herbert: > > Heretofore I'd been treating filepath as owned by Neil Mitchell, but that > statement does sound like he's handed it off to the libraries process, which > would make it a core-libraries issue if he doesn't want to deal with it. > > I'm copying him on this thread to get his opinion. > > I've also copied Andy Gill, to see if he has any opinions on the state of > who owns update responsibility for hpc itself. > > Andy, Neil: Thoughts? > > Thomas: Thanks for forcing this issue to attention. > > -Edward > > On Sun, Sep 28, 2014 at 2:14 PM, Herbert Valerio Riedel <hvriedel(a)gmail.com> > wrote: >> >> On 2014-09-28 at 19:40:25 +0200, Thomas Miedema wrote: >> >> [...] >> >> > Ok, final question: What about filepath and hpc? Their .cabal files list >> > libraries(a)haskell.org as maintainer, which usually means the Core >> > Libraries >> > Committee. Should filepath be added to that list, and the maintainer for >> > both filepath and hpc be set to the Core Libraries Committee? If not, >> > who >> > maintains filepath? >> >> This is supposed to be an answer, but rather additional data-points: >> >> As far as filepath is concerned: >> >> http://community.haskell.org/~ndm/filepath/ >> >> states >> >> | The library is now part of the core Haskell libraries, and since GHC >> | 6.6.1 has been shipped with all major compilers. While I am the >> | original author, changes are now made through the library submissions >> | process. >> >> as for Hpc, if you look at its changelog over at >> >> http://git.haskell.org/packages/hpc.git/shortlog >> >> it's been effectively maintained by GHC HQ for the last couple of >> years... > > >

2 2

ANN: New version of graphmod (1.2.4)
by Iavor Diatchki 03 Oct '14

03 Oct '14

Hello, I am pleased to announce a new version of `graphmod`---a program that helps you visualize the import dependencies between the modules in your Haskell programs. The new feature in version 1.2.4 is support for pruning the dependency graph, which is enabled with the flag -p or --prune-edges. When this option is selected, `graphmod` will ignore imports to modules that are already imported by some of the dependencies of the module. For example, consider the following modules: module A where { import B; import C } module B where { import C } module C where { } When generated with `--prune-edges`, the resulting graph will be: A -> B -> C Note that there is no edge from `A` to `C`, because `C` is already imported by `B`. Happy hacking, -Iavor

1 0

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

Re: Proposal: Use uninterruptibleMask for cleanup actions in Control.Exception
by Eyal Lotem 02 Oct '14

02 Oct '14

Hey Simon, thanks for the reply! On Fri, Sep 5, 2014 at 6:39 PM, Simon Marlow <marlowsd(a)gmail.com> wrote: > Eyal, thanks for bringing up this issue. It's been at the back of my mind > for a while, but I've never really thought through the issues and > consequences of changes. So this is a good opportunity to do that. You > point out (in another email in the thread) that: > > A) Cases that were not interruptible will remain the same. > B) Cases that were interruptible were bugs and will be fixed. > > However, > > C) Some bugs will turn into deadlocks (unkillable threads) > > Being able to recover from bugs is an important property in large > long-running systems. So this is a serious problem. Hence why I always > treat uninterruptibleMask with the deepest suspicion. > Recovering from various kinds of failures makes a lot of sense. But how can you recover from arbitrary invariants of the program being broken? For example, if you use a bracket on some semaphore monitoring a global resource. How do you recover from a bug of leaking semaphore tokens? Recovering from crashes of whole processes whose internal state can be recovered to a fresh, usable state, is a great feature. Recovering from thread crashes that share arbitrary mutable state with other threads is not practical, I believe. > Let's consider the case where we have an interruptible operation in the > handler, and divide it into two (er three): > > 1. it blocks for a short bounded amount of time. > 2. It blocks for a long time > 3. It blocks indefinitely > > These are all buggy, but in different ways. Only (1) is fixed by adding > uninterruptibleMask. (2) is "fixed", but in exchange for an unresponsive > thread - also undesirable. (3) was a bug in the application code, and > turns into a deadlock with uninterruptibleMask, which is undesirable. > I think that (1) is by far the most common and is very prevalent. I think 0-time interruptible (that can block but almost never do) operations are the most common cleanup handlers. For (2) and (3), we need to choose the lesser evil: A) Deadlocks and/or unresponsiveness B) Arbitrary invariants being broken and leaks In my experience, A tends to manifest exactly where the bug is, and is therefore easy to debug and mostly a "performance bug" . B tends to manifest as difficult to explain behavior elsewhere from where the bug actually is, and is usually a "correctness bug", which is almost always worse. Therefore, I think A is a far far lesser evil than B, when (2) and (3) are involved. I'd like to reemphasize that this change will almost always fix the problem completely since the most common case is (1), and in rare cases, it will convert B to A, which is also, IMO, very desirable. > This is as far as I've got thinking through the issues so far. I wonder > to what extent the programmer can and should mitigate these cases, and how > much we can help them. I don't want unkillable threads, even when caused > by buggy code. > Cheers, > Simon > > > On 04/09/2014 16:46, Roman Cheplyaka wrote: > >> I find your arguments quite convincing. Count that as +1 from me. >> >> Roman >> >> >> >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org >> http://www.haskell.org/mailman/listinfo/libraries >> >> -- Eyal

3 3

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