May 2019 - Libraries - Haskell.org

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

Memory Barriers with STM and MVar
by Andrew Martin 03 Jun '19

03 Jun '19

I've been poking around in old threads and in the GHC source, and I cannot find this documented anywhere. What are the guarantees that GHC provides around load/store reordering when it comes to using MVar or TVar+retry+atomically. For example: import Data.Primitive import Control.Concurrent.MVar ... foo :: IO () foo = do ... writeByteArray myArr 13 (42 :: Word) putMVar myMVar () If there is another thread that calls takeMVar followed by `readByteArray myArr 13`, is it guaranteed by GHC to see the 42 that's been written to the array. Same question applies for situations using STM facilities to accomplish blocking behavior that MVar gives us. Any documentation or pointers to places in GHC source where these barriers are guaranteed would be appreciated. -- -Andrew Thaddeus Martin

3 8

Add LiftA4 and LiftA5
by Dannyu NDos 28 May '19

28 May '19

It just feels so uncomforable that we have LiftM4 and LiftM5, but not Applicative versions of them.

4 4

Proposal: add isEmpty to Monoid
by Dr.Koster 25 May '19

25 May '19

It's often useful to have a generalized null/unit test, e.g. to check if a monadic stream `m a` reaches EOF. A workaround is to use `Eq a, Monoid a` constraint and use `== mempty` test. But this is no only inefficient for some type, but also impossible for some monoids, such as Builders. I propose add this test `isEmpty :: a -> Bool` to `Monoid`, to provide the ability to check if a value is the unit value. Cheers Han Dong~

3 3

request: a Nat ordering constraint that is not an equality constraint
by Nicolas Frisby 22 May '19

22 May '19

This email proposes an extension and possible change to GHC.TypeLits module in the core `base` library. Is there support for this kind of extension/change to GHC.TypeLits? If so, I'll open a GHC GitLab Issue. (If not, I would be very appreciate if someone were able to suggest a nice workaround.) # The Proposed Extension Please add an alternative to <= that is not defined via ~. For example: ``` module GHC.TypeLits.Passive where class IsTrue (a :: Bool) instance IsTrue 'True instance TypeError ... => IsTrue 'False type (<=) x y = IsTrue (x <=? y) ``` as opposed to the existing definition: ``` module GHC.TypeLits where type (<=) x y = (x <=? y) ~ 'True ``` Its name should be an operator and should be somewhat obvious -- I can't think of one other than <=, so I hedged here by putting in a new module instead. There should be a means of *explicitly* converting back and forth between evidence of the two constraints; they are equi-satisfiable but affect type inference in their scope differently. # The Optional Change I anticipate most users would prefer Passive.<= to today's <=, so the optional library change in this proposal is to redefine <= and relegate its old definition to a new name. Perhaps: ``` module GHC.TypeLits where type (<=) x y = IsTrue (x <=? y) type (<=!) x y = (x <=? y) ~ 'True ``` # The Motivation I'll explain with an example for some concreteness. I wrote an interface for size-indexed vectors for my employer. It involves some code like this: ``` import GHC.TypeLits newtype Fin (n :: Nat) = Unsafe_MkFin{forgetFin :: Integer} mkFin :: (KnownNat i,i <= n) => proxy i -> Fin n mkFin = Unsafe_MkFin . natVal ``` Constraints like `(i <= n)` show up throughout the library's interface. The problem is that <= is an equality constraint. Therefore many uses of `mkFin` et al *require* that I introduce local equality constraints. And those sadly spoil lots of desired type inference by making outer tyvars untouchable. That's the problem: I have to choose between GHC's specialized solving of <= constraints and unspoiled type inference in their scope. # Additional Context It is important that today's <= be an equality constraint, because it participates in some constraint improvements that introduce equality constraints. For example (x <= y,y <= x) implies x ~ y (c.f. the scary https://gitlab.haskell.org/ghc/ghc/issues/16586) Because <= constraints have the potential to "become" an equality constraint, tyvars outside of a <= constraint must be untouchable in its scope from the get go. However, neither my library nor any of its uses relies on such constraint improvements enabled by <= constraints. In this context, I would much rather that <= could never "become" an equality constraint, so that it need not be an equality constraint, so that it would never render a tyvar untouchable. # An Alternative As a partial workaround, I could write ``` data Dict i n = (i <= n) => MkDict mkFinD :: (KnownNat i) => Dict i n -> proxy i -> Fin n mkFinD MkDict = mkFin ``` and then take pains to only introduce the <= constraints in the argument of `mkFinD`. By limiting the scope of the ~ constraints like that, I could prevent them from spoiling the desired type inference. But it's very cumbersome to manage their scopes manually. # Work Estimation I just thought of the `IsTrue`-based approach while writing this email, so that detail is somewhat half-baked. It has the right *indicative* semantics, but I doubt today's GHC solver would know what to do with a Given `IsTrue (3 <=? 5)` constraint -- so I'm guessing that exact approach at least would require some significant changes in TcTypeNats. Thank you for your time. -Nick P.S. - Some of the issue tracker links at https://wiki.haskell.org/Library_submissions#The_Libraries respond with 404. P.P.S. - Is there a standard place to find something like `IsTrue`? More generally: a test for type equality that does not drive unification? Thanks again.

3 7

Proposal: DerivingVia, MTL
by Reed Mullanix 19 May '19

19 May '19

As it stands, working with newtypes around transformers can be kind of a pain. For example, consider newtype FreshT m a = { unFreshT :: StateT Int m a } deriving (Functor, Applicative, Monad, MonadReader r, ...) Right now, we can't just GND the instance: instance (MonadState s m) => MonadState s (FreshT m) However, the instance we end up writing is completely formulaic. Fortunately, we can solve this by using the recently added -XDerivingVia newtype Inner (t :: (* -> *) -> * -> *) m a = Inner { getInner :: t m a } deriving (Functor, Applicative, Monad) instance (MonadState s m) => MonadState s (Inner (StateT s') m) where get = Inner $ lift get put = Inner . lift . put This lets us derive the instance that we were looking for newtype FreshT m a = FreshT { unFreshT :: StateT Int m a } deriving newtype (Functor, Applicative, Monad, MonadReader r) deriving (MonadState s) via Inner (StateT Int) m This can be extended to other transformers/classes very easily. It also works well when dealing with newtyped transformer stacks. newtype FooT s e m a = FooT { unFooT :: StateT s (WriterT String (ExceptT e m)) a } deriving newtype (Functor, Applicative, Monad, MonadError e) deriving (MonadWriter w) via (StateT s (Inner (WriterT String) (ExceptT e m))) deriving (MonadState s') via Inner (StateT s) (WriterT String (ExceptT e m)) Cheers, Reed Mullanix

2 2

Proposal: add foldMapA to Data.Foldable or Control.Applicative
by Vanessa McHale 11 May '19

11 May '19

It's relatively easy to define foldMapA, viz. foldMapA :: (Monoid b, Traversable t, Applicative f) => (a -> f b) -> t a -> f b foldMapA = (fmap fold .) . traverse I've used found it useful once so far: http://hackage.haskell.org/package/dir-traverse-0.2.0.0/docs/src/System.Dir… Cheers, Vanessa McHale

9 19

Arg has unlawful instances
by David Feuer 11 May '19

11 May '19

Foldable, Traversable, Bifoldable, and Bitraversable instances of Data.Semigroup.Arg don't respect ==. For example, Arg () 1 == Arg () 2 = True, but sum (Arg () 1) = 1 and sum (Arg () 2) = 2. I believe the best solution is to remove the Traversable and Bitraversable instances, and define foldMap _ _ = mempty bifoldMap f _ (Arg a _) = a There also needs to be some documentation about the fact that the Arg constructor allows inspection that does not respect Eq.

5 4