June 2019 - Libraries

Deprecating fromIntegral
by Niklas Hambüchen 12 Aug '20

12 Aug '20

This is not a joke. I just found a bug in base (https://ghc.haskell.org/trac/ghc/ticket/14262) import System.IO hWaitForInput stdin 4294968296 This code should wait for 49.something days, but it waits for 1 second. It is caused by a quick use of `fromIntegral` to "convert" `Int -> CInt` (where CInt = Int32), causing an overflow. I argue that `fromIntegral` causes unnoticed data corruption without any warning, and thus are worse than partial functions. In this case, this data corruption occurs in the most fundamental code that we all use and have to rely upon (`base`). So I propose that we add a deprecation pragma to `fromIntegral` (however, keeping it forever, like Java does, as there's no benefit to removing it, we just want that people use safer functions over time), and instead provide a `safeFromIntegral` that can only widen ranges, and one or more `unsafeFromIntegral` or appropriately named functions that can error, wrap, return Maybe, or have whatever desired behaviour when the input value doesn't fit into the output type. For some inspiration, `foundation` provides ideas in that direction: http://hackage.haskell.org/package/basement-0.0.2/docs/Basement-From.html http://hackage.haskell.org/package/basement-0.0.2/docs/Basement-IntegralCon… It is a bit funny how we argue that Haskell is good for high assurance programming, and we build all sorts of fancy constructs to eliminate more run-time errors, when in fact we do worse than C in detecting errors in the most basic types a computer can use, such as converting between 64-bit and 32-bit integers. Let's fix that. It avoids real problems in real production systems that are difficult to debug when they happen (who writes a unit test checking that a timeout of 50 days still works? This is the kind of stuff where you have to rely on -- very basic -- types). I'd like to probe support for such a change before doing any work on it. Niklas

18 58

Deprecate First and Last in Data.Monoid
by Andrew Martin 13 Jun '20

13 Jun '20

I propose that the data types First and Last, provided by Data.Monoid, be marked deprecated in GHC 8.6 and removed in GHC 8.10. The Semigroup-Monoid Proposal (SMP) brought about changes that, I will argue, make these data types (1) unneeded and (2) confusing. Why are they no longer needed? Data.Semigroup provides two identically named data types (First and Last). These have Semigroup instances matches what their names suggest. Additionally, SMP corrects the Monoid instance for Maybe so that it now lifts Semigroup instances instead of Monoid instances. What this means is that, assuming the following imports: import qualified Data.Monoid as M import qualified Data.Semigroup as S We have the following equivalences: M.First a === Maybe (M.First a) M.Last a === Maybe (M.Last a) When I say "equivalence", I mean that their Monoid instances have the same behavior. Their Show/Read instances are certainly different, and I’m not sure about their Ord instances. Getting back to the second reason, removing these data types would eliminate confusion. It’s strange that Semigroup is a superclass of Monoid, yet they have Data types with conflicting names defined in their respective modules. When you see the data type First, you cannot tell what someone is talking additional context. In general, base strives to avoid duplicate identifiers. The only other exception to this rule I can think of is that Bifunctor and Arrow both use the identifiers first and second. But, the situation with Data.Semigroup and Data.Monoid is higher impact since people are more likely to import these modules unqualified together. (As an aside, and the confusion I’m talking about here isn’t entirely hypothetical. I got tripped up by this when I first started using the semigroups library. I had to train myself to stop importing Data.Monoid unqualified, because it kept stealing these identifiers) Again, the two reasons are that these are no longer necessary and that they cause confusion. I would appreciate any feedback, including simple nods of agreement or disagreement. Thanks. -- -Andrew Thaddeus Martin

7 8

Incremental Regex Parsing with Fixed Strings
by Andrew Martin 12 Sep '19

12 Sep '19

Greetings, In Dan Piponi's blog post Fast Incremental Regular Expression Matching with Monoids [1], he outlines a way to take advantage of fingertrees to perform increment regex matching. In his article, the regular expression (more accurately, its equivalent DFA) is fixed, and the strings we are matching on are modified incrementally. What I'm interested in is the opposite: What if the regular expression is modified incrementally and the string we are testing is static? Thinking about this, it seems to run into problems immediately. Typically, to evaluate a regular expression, I would convert it to a NFA (and then maybe to a DFA). But there is no way to do incremental graph modification on the resulting graphs. (Or is there?). And even if there were a way, it seems unclear how one would go about exploiting its incremental nature. To provide an example, consider the following regex and sample string: Regex: Lost (dog|cat) loo for home Sample: Lost dog looking for home In the regex, I'm currently in the middle of typing "looking", so it doesn't match the sample string. But large parts of it do. So when I update the regex by typing "k", I'd like to be able to not redo this work. Maybe there's a certain subset of regex that's amenable to this kind of incremental evaluation. Maybe not. If anyone has any additional insights or can point me to any research, I would appreciate it greatly. Thanks. [1] http://blog.sigfpe.com/2009/01/fast-incremental-regular-expression.html -- -Andrew Thaddeus Martin

5 6

Cayenne Source Code
by Andrew Martin 09 Jul '19

09 Jul '19

I just read through Lennart's paper on Cayenne, which was written in Haskell. It would be informative for me to look at the source code for a simple dependently typed language like this. (The paper claims the typechecker is only around 5000 LoC.) However, I cannot find the source code anywhere. Has it been devoured by the cruel jaws of the ephemeral web, or does someone out there still have a copy of it? -- -Andrew Thaddeus Martin

3 3

Proposal: add HasCallStack for all partial functions in base
by LuoChen 08 Jul '19

08 Jul '19

Motivation Partial functions in base (especially Prelude) often cause runtime errors and is hard to locate. (here <https://gist.github.com/luochen1990/6fcbb0fa4c0c7caa1b242188eb586d1f> is a document about the concept of totality and partial function, ignore this if you are familiar with them) For example, consider the following piece of code: import GHC.Stack foo :: HasCallStack => [Int] -> Int foo xs = last xs + 1 xs :: [Int] xs = [] main :: IO () main = do print $ foo xs In this case, the error message will tell nothing about foo, and the HasCallStack constraint is totally helpless, because the call stack is cut off by the call to last which without HasCallStack constraint. My current workaround is define my own wrapper functions with HasCallStack constraint for some mostly used partial functions to make them traceable, and use the wrapper (the traceable version) whenever I need them. e.g. last' :: HasCallStack => [a] -> a last' xs = case xs of [] -> error "abuse last"; _ -> last xs So, IMHO, if our goal is to make errors in haskell traceable, then *only providing HasCallStack mechanism is not enough, we have to provide traceable base package and prelude at the same time*. Further more, all untraceable partial functions are considered to be harmful, and should not be exported by any package. Because an improper call to an untraceable partial function will cut off the call stack, and here is a demonstration about that <https://gist.github.com/luochen1990/94179a2492ff7d1ca45153645f1bb449>. On the other hand, is it ever necessary for us to add HasCallStack for a total function? Or we can ask, is it possible that a call to a total function cause runtime error? Maybe it’s a NO, since a total function will also crash when the machine is Out Of Memory, but that is also the only situation I can find out. So I suggest that we add HasCallStack constraint only for partial functions, and IMHO this could be a good balance for better debugging experience and less runtime overhead. Proposal 1. add HasCallStack constraint for all partial functions in base package 2. suggest all programmers to add HasCallStack constraint for their exported partial functions when they release a package 3. provide a compiler option -fignore-hascallstack to toggle off the effect of HasCallStack constraint in case somebody need best performance Other Considerations How to get a full list of partial functions provided by the base package? I wanted to provide a full list of partial functions exported by the base package in this post, but I find it is hard, since Haskell have no totality checking mechanism like Idris have, and there are no consistent keyword like “total” or “partial” in document, so it takes a lot of work to list all the partial functions of a package by check every item manually. Maybe we can work on this list later — when it’s turned out to be worth after some discussion. Here <https://gist.github.com/luochen1990/5b7a0844701413486da595b9b997f3c2> is part of the list that I have tidied for several modules of the base package. How to encourage all package contributors to obey the rule (see proposal #2)? I don’t know, but I think there may be some other rules to obey when contributing packages. Maybe we can just add this into the list. Obviously, the final perfect solution should be let the compiler to check the totality of functions, and automatically add HasCallStack for the ones which the compiler cannot confirm it’s totality. But this seems too far away from us, since we still doesn’t have dependent type haskell yet. How to deal with recursive partial functions? Since the HasCallStack constraint affects the performance (not only because of the runtime overhead, but also it’s influence on optimization strategy), It is best not to add HasCallStack on recursive functions. In most of the cases, we can just check the input shallowly before everything start, just like how we deal with the non-recursive ones. But in some other cases, we need to go deep to recognize the invalidity of the input. A trivial solution is just perform a deep check before everything start, but the checking phase seems expensive. The best solution, IMHO, is to make the recursive part a total function, wrap the return value into Maybe or some similar things, and the partial version is just the total version combined fromJust. In this way, we avoid the single input checking phase and left the error awareing logic where it was before this translation.

9 18

Making Int{Map,Set} polymorphic over the key type
by Georg Rudoy 29 Jun '19

29 Jun '19

Hi folks, What do you think about making IntMap and IntSet polymorphic over the keys as long as the key type k is Coercible to Int? The motivation is that oftentimes one needs to have a collection of newtype wrappers around Int, and then they have to either unpack/repack it around the relevant containers (which is not nice), or just use HashMap/HashSet (which is perhaps suboptimal). If this is a direction the community might deem reasonable, I'd be happy to work on this and make a PR to the containers repo (perhaps after discussing the specific details about naming, etc). -- Georg Rudoy

4 7

Fwd: lazier writer monad
by Tristan Wibberley 26 Jun '19

26 Jun '19

Dear Haskell Libraries mailing list members, I've submitted a merge request for an increase in the laziness of the writer monad: https://gitlab.haskell.org/ghc/ghc/merge_requests/1262 and it requires discussion via this mailing list. The link above includes an example of the motivation for this change and I hope you can all extrapolate to see the importance of this change, sufficient to not only accept this but to be moved to add a language flag, available within the content of a module's source file, to match unique constructors lazily throughout a module that uses it, lifting _|_ to the next least-defined value. The core problem is that for the most handy and practical library interfaces, we need function results to be as well-defined as possible before a strict pattern match is required to choose between two constructors/values. There are several parts to providing that but one important part is that elements of patterns that cannot be unmatched should be lazily matched so the function's definition can be used without evaluating the function's arguments first. This avoids having to train users to always avoid patterns except after a let binding which would otherwise be necessary to establish a standard habit to lazily pattern match so the user base encourages each other to make their functions maximally useful. -- Tristan

3 2

transformers mirroring to GitHub
by chessai . 25 Jun '19

25 Jun '19

Could we mirror transformers from darcshub to GitHub? This would make browsing the current source easier for those of us who do not frequent darcshub. It would also help with the uniformity of having core libs on GitHub. Of course this would just be a mirror, and users would be advised to not open PRs there. Not sure how easy mirroring from DarcsHub to GitHub is. Thoughts? Thanks

2 2

Re: Data.Graph transitive closure
by Johannes Waldmann 24 Jun '19

24 Jun '19

> ... reasonably efficient transitive closure for Data.Graph ... well, since we have type Graph = Array Vertex [Vertex] efficiency is already questionable? We cannot quickly check whether an edge is present, we cannot quickly get all predecessors of a vertex. But perhaps we don't need to. The underlying assumptions (cost of elementary operations) of http://www.cs.hut.fi/~enu/thesis.html are not immediately clear. The cited Agda library has newtype Graph n e = Graph (Map n (Map n e)) Another option is to store back edges as well, as in https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Int… FGL fuses these two maps type GraphRep a b = IntMap (Context' a b) type Context' a b = (IntMap [b], a, IntMap [b]) https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inducti… this saves some look-ups (if you need successors and predecessors of the very same node) but this can't be used for relations, where start and end of an edge have different types. But for transitive closure, these types would agree anyway. What to make of this? Perhaps Data.Graph should be moved out of containers. The design space is just too large to single out one specific point? If we keep it, it would be very nice to document the complexity of algorithms. Section 7 of the King/Launchbury paper (cited in the API docs) claims "DFS in O(V+E)", backed up by experiments. This seems to be the main motivation for this library (DFS, with application: SCC). It's not clear whether the underlying design should be recommended for a general graph library. - Johannes

6 12

Re: Data.Graph transitive closure
by Johannes Waldmann 22 Jun '19

22 Jun '19

> .. I would use it. what is your use case? Can you extract test cases that could be used to validate correctness and complexity of an implementation? Specific question: assume the implementation gives you S = transitive-closure-of(R). Then what do you do with S (in your application)? Does Data.Graph (i.e., array of lists of successors) have the right structure? E.g., it is inefficient to test for membership in these lists. But lists are fine if you need to handle all successors anyway. Evaluation of (recursive) Datalog queries is another application area of transitive closure algorithms. (e.g., https://doi.org/10.1007/BF01264013 ) - J.

1 0