- Libraries - Haskell.org

atomicModifyIORef' strictness
by David Feuer 13 Jul '18

13 Jul '18

In the process of replacing atomicModifyMutVar#, I noticed that atomicModifyIORef' is just a little bit lazy: atomicModifyIORef' ref (\x -> (x + 1, undefined)) will increment the reference and then throw an exception in the calling thread. We could sometimes avoid creating thunks by changing this, so the above would install undefined in the IORef as well. For example, suppose I write atomicModifyIORef' ref (\x -> (3, x + 5)) This will end up producing a thunk for the second component. That could be avoided using something like atomicModifyIORef' ref (\ !x -> (3, x + 5)) but it seems a little surprising to have to do that in a function that focuses on being strict. I don't really care too much one way or the other, but I figured I should point this out and see what you all think.

1 0

Re: Discussion: New atomic IORef functions
by David Feuer 12 Jul '18

12 Jul '18

On Wed, Jul 11, 2018, 11:32 PM winter <drkoster(a)qq.com> wrote: > OK then, here's some subtle things i want to shout out if you're going to > make the change ; ) > > 1. The proposed naming is just not great, how about these: > > atomicExchangeIORef :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) > atomicExchangeIORef' :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) > > atomicApplyIORef :: IORef a -> (a -> a) -> IO (a, a) > atomicApplyIORef :: IORef a -> (a -> a) -> IO (a, a) > > It may not that great but it's more informative IMO. > I agree that my names aren't great, but I think yours are worse. > 3. atomicExchangeIORef should not force the tuple, e.g. don't pattern > match on the tuple result, instead let users choose to force or not. (May > worth adding some document, I'd be happy to help) > I generally disagree. Being lazy in the tuple is pretty much an invitation to memory leaks. I think the lazy version should ideally also be available (it's what the new primop will provide, after all), but I don't think it should be the obvious thing for people to reach for. > 4. atomicExchangeIORef' will not only force the tuple, but also force both > `a` and `b` part to match atomicModifyIORef' 's semantics. > I don't see the need for this. Users can easily force exactly what they want using atomicModifyIORef2 (or if they really want, atomicModifyIORef2Lazy). > 5. atomicApplyIORef(and atomicApplyIORef') deserve its own primop, since > we can skip building selector thunks all together. > Yes, I've implemented that primop already, and it will be added. I'm still looking for an expert to help implement the simplest of the lot, atomicSwapMutVar#, as efficiently as possible.

2 1

Re: Discussion: New atomic IORef functions
by Dr.Koster 11 Jul '18

11 Jul '18

But if you force the pair result, you have to evaluate modifying function isn't it? That's sometime unwanted when you have an very expensive f here, let's say a deep binary search which might not depend previous result. I think that is also why current atomicModifyIORef is designed this way, so I'd rather keep it the old way. 发自我的iPhone ------------------ Original ------------------ From: David Feuer <david.feuer(a)gmail.com> Date: Thu,Jul 12,2018 0:51 AM To: winter <drkoster(a)qq.com> Cc: Haskell Libraries <libraries(a)haskell.org> Subject: Re: Discussion: New atomic IORef functions All the fundamental functions I've defined can be usefully used in the base library. I think that's one good reason to put them there. Another is that while the basic array operations have traditionally been exposed through array, vector, and primitive, and the basic TVar operations have been exposed through stm, the basic IORef and MVar operations have been exposed through base (except, for some reason, casMutVar#). I see no reason to change that. I never proposed a function that forces the previous value unnecessarily, so I don't know why you're complaining about that. The extra laziness I don't like is in the pair result; none of the uses I've seen thus can far make intentional use of that. That's why I tend to think atomicModifyIORef (as it exists today) is almost never what people actually want. Squeezing into a second component leads to extra allocation in what may be a performance-critical function; that said, I'm willing to hold off on higher tuples for now. On Sun, Jul 8, 2018, 3:36 AM winter <drkoster(a)qq.com> wrote: I believe new variations should always be motivated by use-case if there're too many choices, the lazy behavior of old `atomicModifyIORef` is justified by some cases the modifying functions are lazy in its argument, thus a lazy version could win by not forcing previous thunks, we'd want to keep its behavior as how it's documented. As for tuples more than pairs, they're not really needed, user can always squeeze their product into `b` component. IMHO only the addition of `atomicModifyIORef_` is sensible in the context of base, other APIs may go to package like primitives. But if you have a motivated use case with `atomicModifyIORef2`, etc. Please tell me. On 2018年07月08日 03:09, David Feuer wrote: Whoops! I left out the proposal link: https://github.com/ghc-proposals/ghc-proposals/pull/149 Also, what I called atomicModifyIORef_ below should really be called something like atomicModifyIORef'_, since it forces a polymorphic value. Another thing to note: the underlying atomicModifyMutVar2# primop actually supports more than just pairs. It can handle triples, solos, and any other record types whose first components are lifted: atomicModifyIORefSoloLazy :: IORef a -> (a -> Solo a) -> IO (Solo a) atomicModifyIORefSolo :: IORef a -> (a -> Solo a) -> IO a atomicModifyIORef3, atomicModifyIORef3Lazy :: IORef a -> (a -> (a, b, c)) -> IO (a, b, c) etc. Should we add any such? On Sat, Jul 7, 2018, 2:35 PM David Feuer <david.feuer(a)gmail.com> wrote: I have proposed[1] the replacement of the atomicModifyMutVar# primop, and the addition of two cheaper but less capable ones. It seems likely that the proposal will succeed, but that the GHC steering committee will leave the question of user interface changes to the libraries list. I would like to open the discussion here. The new primops lead naturally to several thin wrappers: -- Atomically replace the IORef contents -- with the first component of the result of -- applying the function to the old contents. -- Return the old value and the result of -- applying the function, without forcing the latter. -- -- atomicModifyIORef ref f = do -- (_old, ~(_new, res)) <- atomicModifyIORef2Lazy ref f -- return res atomicModifyIORef2Lazy :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) -- Atomically replace the IORef contents -- with the result of applying the function -- to the old contents. Return the old and -- new contents without forcing the latter. atomicModifyIORefLazy_ :: IORef a -> (a -> a) -> IO (a, a) -- Atomically replace the IORef contents -- with the given value and return the old -- contents. -- -- atomicWriteIORef ref x = void (atomicSwapIORef ref x) atomicSwapIORef :: IORef a -> a -> IO a Based on the code I've read that uses atomicModifyIORef, I believe that the complete laziness of atomicModifyIORef2Lazy and atomicModifyIORefLazy_ is very rarely desirable. I therefore believe we should also (or perhaps instead?) offer stricter versions: atomicModifyIORef2 :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) atomicModifyIORef2 ref f = do r@(_old, (_new, _res)) <- atomicModifyIORef2Lazy ref f return r atomicModifyIORef_ :: IORef a -> (a -> a) -> IO (a, a) atomicModifyIORef_ ref f = do r@(_old, !_new) <- atomicModifyIORefLazy_ ref f return r The classic atomicModifyIORef also admits a less gratuitously lazy version: atomicModifyIORefNGL :: IORef a -> (a -> (a,b)) -> IO b atomicModifyIORefNGL ref f = do (_old, (_new, res)) <- atomicModifyIORef2 ref f return res Should we add that as well (with a better name)? Should we even consider *replacing* the current atomicModifyIORef with that version? That could theoretically break existing code, but I suspect it would do so very rarely. If we don't change the existing atomicModifyIORef now, I think we should consider deprecating it: it's very easy to accidentally use it too lazily. _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

3 2

Re: Discussion: New atomic IORef functions
by David Feuer 11 Jul '18

11 Jul '18

All the fundamental functions I've defined can be usefully used in the base library. I think that's one good reason to put them there. Another is that while the basic array operations have traditionally been exposed through array, vector, and primitive, and the basic TVar operations have been exposed through stm, the basic IORef and MVar operations have been exposed through base (except, for some reason, casMutVar#). I see no reason to change that. I never proposed a function that forces the previous value unnecessarily, so I don't know why you're complaining about that. The extra laziness I don't like is in the pair result; none of the uses I've seen thus can far make intentional use of that. That's why I tend to think atomicModifyIORef (as it exists today) is almost never what people actually want. Squeezing into a second component leads to extra allocation in what may be a performance-critical function; that said, I'm willing to hold off on higher tuples for now. On Sun, Jul 8, 2018, 3:36 AM winter <drkoster(a)qq.com> wrote: > I believe new variations should always be motivated by use-case if > there're too many choices, the lazy behavior of old `atomicModifyIORef` is > justified by some cases the modifying functions are lazy in its argument, > thus a lazy version could win by not forcing previous thunks, we'd want to > keep its behavior as how it's documented. > > As for tuples more than pairs, they're not really needed, user can always > squeeze their product into `b` component. > > IMHO only the addition of `atomicModifyIORef_` is sensible in the context > of base, other APIs may go to package like primitives. But if you have a > motivated use case with `atomicModifyIORef2`, etc. Please tell me. > > On 2018年07月08日 03:09, David Feuer wrote: > > Whoops! I left out the proposal link: > > https://github.com/ghc-proposals/ghc-proposals/pull/149 > > Also, what I called atomicModifyIORef_ below should really be called > something like atomicModifyIORef'_, since it forces a polymorphic value. > > Another thing to note: the underlying atomicModifyMutVar2# primop actually > supports more than just pairs. It can handle triples, solos, and any other > record types whose first components are lifted: > > atomicModifyIORefSoloLazy > :: IORef a -> (a -> Solo a) -> IO (Solo a) > > atomicModifyIORefSolo > :: IORef a -> (a -> Solo a) -> IO a > > atomicModifyIORef3, atomicModifyIORef3Lazy > :: IORef a -> (a -> (a, b, c)) -> IO (a, b, c) > > etc. > > Should we add any such? > > On Sat, Jul 7, 2018, 2:35 PM David Feuer <david.feuer(a)gmail.com> wrote: > >> I have proposed[1] the replacement of the atomicModifyMutVar# primop, and >> the addition of two cheaper but less capable ones. It seems likely that the >> proposal will succeed, but that the GHC steering committee will leave the >> question of user interface changes to the libraries list. I would like to >> open the discussion here. >> >> The new primops lead naturally to several thin wrappers: >> >> -- Atomically replace the IORef contents >> -- with the first component of the result of >> -- applying the function to the old contents. >> -- Return the old value and the result of >> -- applying the function, without forcing the latter. >> -- >> -- atomicModifyIORef ref f = do >> -- (_old, ~(_new, res)) <- atomicModifyIORef2Lazy ref f >> -- return res >> atomicModifyIORef2Lazy >> :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) >> >> -- Atomically replace the IORef contents >> -- with the result of applying the function >> -- to the old contents. Return the old and >> -- new contents without forcing the latter. >> atomicModifyIORefLazy_ >> :: IORef a -> (a -> a) -> IO (a, a) >> >> -- Atomically replace the IORef contents >> -- with the given value and return the old >> -- contents. >> -- >> -- atomicWriteIORef ref x = void (atomicSwapIORef ref x) >> atomicSwapIORef >> :: IORef a -> a -> IO a >> >> Based on the code I've read that uses atomicModifyIORef, I believe that >> the complete laziness of atomicModifyIORef2Lazy and >> atomicModifyIORefLazy_ is very rarely desirable. I therefore believe we >> should also (or perhaps instead?) offer stricter versions: >> >> atomicModifyIORef2 >> :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) >> atomicModifyIORef2 ref f = do >> r@(_old, (_new, _res)) <- atomicModifyIORef2Lazy ref f >> return r >> >> atomicModifyIORef_ >> :: IORef a -> (a -> a) -> IO (a, a) >> atomicModifyIORef_ ref f = do >> r@(_old, !_new) <- atomicModifyIORefLazy_ ref f >> return r >> >> The classic atomicModifyIORef also admits a less gratuitously lazy >> version: >> >> atomicModifyIORefNGL >> :: IORef a -> (a -> (a,b)) -> IO b >> atomicModifyIORefNGL ref f = do >> (_old, (_new, res)) <- atomicModifyIORef2 ref f >> return res >> >> Should we add that as well (with a better name)? Should we even consider >> *replacing* the current atomicModifyIORef with that version? That could >> theoretically break existing code, but I suspect it would do so very >> rarely. If we don't change the existing atomicModifyIORef now, I think we >> should consider deprecating it: it's very easy to accidentally use it too >> lazily. >> > > > _______________________________________________ > Libraries mailing listLibraries@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

1 0

Better casing functions (German ß, etc.)
by 박신환 11 Jul '18

11 Jul '18

Current Haskell has 'simple' `Char`-to-`Char` casing functions (as specified by Unicode), namely `toUpper`, `toLower` and `toTitle`. So to convert cases of a `String`, Haskell intends `fmap toUpper`, etc. But this has some bugs. Case 1. German ß (Eszett) 'ß' (U+00DF), Latin Small Letter Sharp S, is a lowercase letter itself, but Unicode doesn't specify its 'simple' uppercase counterpart. It's because its uppercase counterpart is not a single character, but two characters, "SS". Case 2. Turkish İ and ı Rather than the common 'I' and 'i' case pair, Turkish language has the 'İ' (U+0130) and 'i' pair and the 'I' and 'ı' (U+0131) pair. Those are, dotted I pair and dotless I pair, respectively. Case 3. Greek Σ (Sigma) Greek 'Σ' (U+03A3) must be lowercase mapped to 'ς' (U+03C2) if followed by a whitespace, rather than normal 'σ' (U+03C3). Case 4. Greek iota subscript (Ypogegrammeni) Greek 'Capital' letters with iota subscripts (for example, 'ᾈ' (U+1F88)), though they are the 'simple' uppercase counterpart of their lowercase counterpart, they themselves are actually treated as titlecase characters. For example, the actual uppercase counterpart of 'ᾀ' (U+1F80) is "ἈΙ" (U+1F08 U+0399). That is, an actual capital iota instead of the iota subscript. Case 5. Precomposed letters without upper/lowercase counterpart For example, ΐ (U+03B0) doesn't have precomposed uppercase counterpart. It must be effectively mapped to "Ϊ́" (U+03AA U+0301). In Summary, we need more elaborated casing functions which are `String`-to-`String`. Bibliography: The Unicode Standard Version 11.0 – Core Specification, Section 5.18.

4 3

fixST lost bottoms
by David Feuer 09 Jul '18

09 Jul '18

I filed a ticket[*] for this, but I think maybe the libraries list should weigh in on whether it is something that should be fixed. In general, fixST f is supposed to bottom out if f forces its argument. However, the lazy way GHC blackholes thunks under evaluation sometimes leads to the computation being run again. In certain contrived situations, this can allow the computation to succeed! The example I give in the ticket: import Control.Monad.ST.Strict import Control.Monad.Fix import Data.STRef foo :: ST s Int foo = do ref <- newSTRef True mfix $ \res -> do x <- readSTRef ref if x then do writeSTRef ref False return $! res + 5 -- force the final result else return 10 main = print $ runST foo Here, the computation writes to an STRef before forcing the final result. Forcing the final result causes the computation to run again, this time taking the other branch. The program prints 15. When compiled with -O -feager-blackholing, however, the expected <<loop>> exception occurs. As far as I know, this weirdness never changes the value produced by a non-bottoming computation, and never changes a non-bottoming computation into a bottoming one. The fix (defining fixST the way fixIO is currently defined) would have a slight performance impact. Is it worth it? [*] https://ghc.haskell.org/trac/ghc/ticket/15349

4 5

Discussion: New atomic IORef functions
by David Feuer 08 Jul '18

08 Jul '18

I have proposed[1] the replacement of the atomicModifyMutVar# primop, and the addition of two cheaper but less capable ones. It seems likely that the proposal will succeed, but that the GHC steering committee will leave the question of user interface changes to the libraries list. I would like to open the discussion here. The new primops lead naturally to several thin wrappers: -- Atomically replace the IORef contents -- with the first component of the result of -- applying the function to the old contents. -- Return the old value and the result of -- applying the function, without forcing the latter. -- -- atomicModifyIORef ref f = do -- (_old, ~(_new, res)) <- atomicModifyIORef2Lazy ref f -- return res atomicModifyIORef2Lazy :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) -- Atomically replace the IORef contents -- with the result of applying the function -- to the old contents. Return the old and -- new contents without forcing the latter. atomicModifyIORefLazy_ :: IORef a -> (a -> a) -> IO (a, a) -- Atomically replace the IORef contents -- with the given value and return the old -- contents. -- -- atomicWriteIORef ref x = void (atomicSwapIORef ref x) atomicSwapIORef :: IORef a -> a -> IO a Based on the code I've read that uses atomicModifyIORef, I believe that the complete laziness of atomicModifyIORef2Lazy and atomicModifyIORefLazy_ is very rarely desirable. I therefore believe we should also (or perhaps instead?) offer stricter versions: atomicModifyIORef2 :: IORef a -> (a -> (a, b)) -> IO (a, (a, b)) atomicModifyIORef2 ref f = do r@(_old, (_new, _res)) <- atomicModifyIORef2Lazy ref f return r atomicModifyIORef_ :: IORef a -> (a -> a) -> IO (a, a) atomicModifyIORef_ ref f = do r@(_old, !_new) <- atomicModifyIORefLazy_ ref f return r The classic atomicModifyIORef also admits a less gratuitously lazy version: atomicModifyIORefNGL :: IORef a -> (a -> (a,b)) -> IO b atomicModifyIORefNGL ref f = do (_old, (_new, res)) <- atomicModifyIORef2 ref f return res Should we add that as well (with a better name)? Should we even consider *replacing* the current atomicModifyIORef with that version? That could theoretically break existing code, but I suspect it would do so very rarely. If we don't change the existing atomicModifyIORef now, I think we should consider deprecating it: it's very easy to accidentally use it too lazily.

2 2

Re: Diagonally in Data.Bimap
by Joachim Breitner 05 Jul '18

05 Jul '18

Hi Am Donnerstag, den 05.07.2018, 15:36 +0200 schrieb Gabor Greif: > Hi! > > Just searched for a `bimap` variant that simultaneously transforms > both components with the same morphism: > > ``` haskell > diag :: Bifunctor p => (a -> b) -> p a a -> p b b > diag f = bimap f f > ``` > > I did not find any. Would it make sense to add it? possibly, I have wanted it too before. Bikeshedding: I’d have expected the name “both”. It also has precedence here: http://hackage.haskell.org/package/extra/docs/Data-Tuple-Extra.html#v:both http://hackage.haskell.org/package/concatenative/docs/Control-Concatenative… http://hackage.haskell.org/package/MissingK/docs/Control-Arrow-Extra.html#v… http://hackage.haskell.org/package/lens-family/docs/Lens-Family2-Stock.html… http://hackage.haskell.org/package/lens/docs/Control-Lens-Traversal.html#v:… Diagonally sounds more like something of type `a -> (a,a)` or similar. > PPS: I would have sent this to libraries(a)haskell.org but it seem to be > closed group. It should not. Maybe only open to subscribers? (A common crude anti- spam measurement.) Cheers, Joachim -- Joachim Breitner mail(a)joachim-breitner.de http://www.joachim-breitner.de/

3 2

Proposal: Strict variant of foldMap
by Andrew Martin 02 Jul '18

02 Jul '18

I propose adding another method to the Foldable typeclass: foldMap' This has the same behavior as foldMap except that it is strict in the accumulator. This can lead to considerable performance gains when the user knows that monoidal append is strict both arguments. Consider the following example (available as a gist at https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955) {-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-} import Gauge import Data.Foldable import qualified Data.Set as S foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty numbers :: [Int] numbers = [1..4000] intToSet :: Int -> S.Set Int intToSet i = S.singleton (mod i 10) main :: IO () main = defaultMain [ bench "lazy" $ whnf (foldMap intToSet) numbers , bench "strict" $ whnf (foldMap' intToSet) numbers ] Here are the results we get from running this: benchmarked lazy time 178.8 μs (176.1 μs .. 183.1 μs) 0.996 R² (0.993 R² .. 0.998 R²) mean 180.8 μs (179.1 μs .. 183.3 μs) std dev 7.242 μs (5.856 μs .. 9.304 μs) variance introduced by outliers: 20% (moderately inflated) benchmarked strict time 108.4 μs (106.1 μs .. 111.0 μs) 0.997 R² (0.996 R² .. 0.999 R²) mean 107.9 μs (107.0 μs .. 109.3 μs) std dev 3.672 μs (2.451 μs .. 6.220 μs) variance introduced by outliers: 15% (moderately inflated) These performance gains are considerable. It needs to be a method of Foldable and not just a function written using foldl' for the same reason that the lazy foldMap needs to be a method of Foldable. There are types for which the default implementation can be improved upon. This is a non-breaking change since there is a sensible default implementation. -- -Andrew Thaddeus Martin

6 8

Interaction between Dependent Haskell quantifiers and instance contexts
by Andrew Martin 29 Jun '18

29 Jun '18

In Richard Eisenberg’s PhD thesis Dependent Types in Haskell: Theory and Practice, he presents outline of what dependent types in Haskell would look like. Such an extension to GHC Haskell would replace most uses of the singleton design pattern described by the Hasochism paper (McBride). But, there is one use of singletons (the design pattern, not the library) that Eisenberg’s thesis doesn’t touch on: using pi types in typeclass instances contexts. Consider the following types from Hasochism: data Nat data Natty :: Nat -> Type class NATTY (n :: Nat) The first type is peano numbers. The second type is a singleton type. The third is a class used to implicitly provide values of type Natty in instance contexts. The same paper puts this class to good use when defining an Applicative instance for length indexed vectors: data Vec :: Nat -> Type -> Type instance NATTY n => Applicative (Vec n) To handle this with dependent types, we would need to instead write: instance pi n. Applicative (Vec n) I haven’t seen or heard any talk about whether this will be admissible. I’d be interested in hearing thoughts from the cognoscenti about any fundamental barriers (either theoretical or GHC-specific) that would prevent something like this from being admitted. I have typeclass instances like this come up fairly often in code I work on, so it’s not just a theoretical question to me. Being able to do this really would help me cut down on boilerplate. Sent from my iPhone

2 2