- Libraries - Haskell.org

GC-Managed ByteArray Slicing
by Andrew Martin 08 Sep '18

08 Sep '18

In GHC Haskell, there are two common options for working with bytes in memory: data ByteArray = ByteArray ByteArray# data ByteSlice = ByteSlice ByteArray# Int# Int# The second one, ByteSlice, is roughly what the bytestring library does (but with a ForeignPtr instead of a ByteArray# inside of it). What's unfortunate is that it's difficult to know which of these two types is going to provide better performance for a given application. These heuristics are helpful for guiding the process: 1. The longer the data is going to be around, the better the unsliced variant will be. This point is about space efficiency. The sliced variant needs two extra machine words to hold those indices, plus it holds on to extra bytes from the array that it is slicing into. 2. The shorter the data is going to be around, the better the sliced variant is. This point is about speed of execution. The cost of the unsliced variant is typically a memcpy. If the data is getting GCed quickly anyway, the unsliced copy doesn't save you any space. 3. The shorter the data is, the better the unsliced variant is. 4. The more sharing of the data there is, the better the sliced variant is. But, users have to commit to which one they want to use in their data type definitions, and the data type may be used in different contexts where one or the other is preferable. For example, consider the following: data Student = Student { name :: {-# UNPACK #-} !BytesType , grade :: {-# UNPACK #-} !Int } Which of the two types should we use for BytesType? (For this example, ignore the incorrectness of using bytes to represent text. With either of the two bytes types, it's easy to put a newtype on top that communicates that what's inside is guaranteed to be UTF-8 encoded text). It depends on the usage. For example, consider that we are parsing students from this xml file: <students> <student> <name>Erica Chang</name> <grade>87</grade> </student> <student> <name>Lizbeth Cruz</name> <grade>91</grade> </student> ... </students> Let's say we've got about 1GB of this, and we run a parser on 64KB chunks as they are read from disk. There are two contasting scenarios to consider. If the file is parsed at startup and the resulting array of students is kept in memory for a long time afterward, then the unsliced variant is better. It allows us to throw away all of the bytes corresponding to the xml nodes, which are no longer relevant. The sliced variant, by constrast, would keep the entire contents of the original file in memory. However, if the file is parsed by a SAX-style streaming parser, the students being parsed, processed, and then discarded as they encountered, the sliced variant is better. Slicing wins here because the chunks from the file are discarded shortly after they are encountered. Read "shortly" as "before the next minor GC". In this example, Student was an application-specific data type, so the application author could figure out what they were actually doing with the data and define the data type accordingly. However, this isn't always a solution. What if they needed to use the same type differently in different contexts? What if the type was provided by a library and the library author doesn't know how it will be used? So far, this has just been an explanation of a problem that I've noticed. I understand the problem well, but now I'm going to propose a solution. There are a lot of holes in my understanding of GHC's runtime, so I don't understand if what I'm proposing is actually plausible. What if the GHC's runtime handled the copy decisions for us? What if we had these primitives: data Bytes# sliceBytes# :: Bytes# -> Int# -> Int# -> Bytes# lengthBytes# :: Bytes# -> Int# Slicing causes the runtime to track that there is an additional reference to the byte array but that the offset and length are different. I'm not sure where this information would be stored though. When GC runs, it would copy slices from bytes if the there were no longer any references to the entire array. So a single type could serve the both purposes discussed in the scenario above. I'm not sure what kind of impact this might have on GC time. -- -Andrew Thaddeus Martin

2 1

Proposal: Add mapAccumLM and mapAccumRM to Data.Traversable
by Reed Mullanix 03 Sep '18

03 Sep '18

I propose adding a pair of functions to Data.Traversable: mapAccumLM and mapAccumRM with the type '(Traversable t, Monad m) => (a -> b -> m (a,c)) -> a -> t b -> m (a, t c)'. These would behave exactly the same as mapAccumL and mapAccumR, but would allow the addition of monadic effects. This would allow the traversal of structures with an accumulator, without resorting to using foldlM or foldrM, both of which require the extra boilerplate of reconstructing the structure after applying the action, which can be somewhat frustrating and error-prone. A possible implementation would be to add transformer counterparts to StateL/StateR in Data.Functor.Util: (gist: https://gist.github.com/TOTBWF/dc6020be28df7b00372ab8e507aa54b7) newtype StateLT s m a = StateLT { runStateLT :: s -> m (s,a) } instance (Functor m) => Functor (StateLT s m) where fmap f (StateLT k) = StateLT $ \s -> fmap (\(s',a) -> (s', f a)) $ k s instance Monad m => Applicative (StateLT s m) where pure a = StateLT $ \s -> return (s, a) StateLT kf <*> StateLT kv = StateLT $ \s -> do (s', f) <- kf s (s'', v) <- kv s' return (s'', f v) liftA2 f (StateLT kx) (StateLT ky) = StateLT $ \s -> do (s', x) <- kx s (s'', y) <- ky s' return (s'', f x y) mapAccumLM :: (Monad m, Traversable t) => (a -> b -> m (a,c)) -> a -> t b -> m (a, t c) mapAccumLM f s t = runStateLT (traverse (StateLT . flip f) t) s newtype StateRT s m a = StateRT { runStateRT :: s -> m (s,a) } type StateR s = StateRT s Identity instance (Functor m) => Functor (StateRT s m) where fmap f (StateRT k) = StateRT $ \s -> fmap (\(s',a) -> (s', f a)) $ k s instance Monad m => Applicative (StateRT s m) where pure a = StateRT $ \s -> return (s, a) StateRT kf <*> StateRT kv = StateRT $ \s -> do (s', v) <- kv s (s'', f) <- kf s' return (s'', f v) liftA2 f (StateRT kx) (StateRT ky) = StateRT $ \s -> do (s', y) <- ky s (s'', x) <- kx s' return (s'', f x y) mapAccumRM :: (Monad m, Traversable t) => (a -> b -> m (a,c)) -> a -> t b -> m (a, t c) mapAccumRM f s t = runStateRT (traverse (StateRT . flip f) t) s

2 1

Mark partial functions as such
by Richard Eisenberg 01 Sep '18

01 Sep '18

Proposal: Mark partial functions in `base` as partial Motivation: I'm about to teach Haskell to a classful of beginners. In my experience, they will soon reach for functions like `head` and `tail`, because pattern-matching is foreign to them. I would love just to be able to say "Don't use partial functions", but many students will not easily be able to tell partial functions from total ones. I do expect this problem to work itself out rather quickly, and then students will be able to identify partial functions, but loudly marking partial functions as partial seems like a small service to everyone and a bigger one to newbies. I don't see any downsides. Thoughts? Thanks, Richard

17 29

"Safer" implementation of Data.List.NonEmpty (and some other suggestions)
by 박신환 30 Aug '18

30 Aug '18

Those implementations using the nontotal `fromList`seem inefficient and potentially dangerous. To eliminate those, I wrote a modification of the original file, which is enclosed. Some other suggestions: `insertBy` for `NonEmpty`s `NonEmpty [a]` to `[NonEmpty a]` transposition Add fixity for (:|) as `infixl 4 :|`

1 0

Proposal: add two more Applicative and Monad adapters
by David Feuer 11 Aug '18

11 Aug '18

We currently offer liftA, liftM, liftM2, and ap to implement Functor and Applicative methods in terms of Applicative and Monad ones. But there are a couple other functions in that general vein that are missing. I propose that we should add at least replaceA, and perhaps also beforeM. -- (<$) = replaceA -- This may be better than the default if there is -- an optimized definition of *> (which may be -- based on an optimized >>). replaceA :: Applicative f => a -> f x -> f a replaceA a fa = fa *> pure a -- (<*) = beforeM -- This may be better than the default if there is -- an optimized definition of <$, or if <$ is defined as -- replaceA and *> is optimized. beforeM :: Monad f => f a -> f x -> f a beforeM fa fx = fa >>= \a -> a <$ fx Why a <$ fx and not fx >> pure a? Because <$ could be implemented specially, and is unlikely to be implemented by hand using <* if there isn't a custom <*.

1 1

Lost MonadFix instances
by 박신환 09 Aug '18

09 Aug '18

instance MonadFix Down where mfix f = Down (fix (\x -> let Down x' = f x in x' )) instance MonadFix Proxy where mfix _ = Proxy instance MonadFix U1 where mfix _ = U1 instance MonadFix Complex where mfix f = fix (realPart . f) :+ fix (imagPart . f)

1 0

GC’ing committee memberships
by Joachim Breitner 07 Aug '18

07 Aug '18

Dear Core Library Committee, I am about to switch jobs, and that is a good time to review my responsibilities. I noticed that the GHC Steering Committee is sucking in all my committee-work-time and -energy, leaving none for the CLC, where I have not done any work recently. I would therefore like to officially vacate my seat on the CLC. Cheers, and keep up the good work, Joachim -- Joachim Breitner mail(a)joachim-breitner.de http://www.joachim-breitner.de/

2 1

Extensions to the module name system in H2020
by Marco Zocca 31 Jul '18

31 Jul '18

Hi all, I was wondering if there are plans to extend/revisit/tidy up the module name system (https://wiki.haskell.org/Hierarchical_module_names) in view of Haskell 2020. I'm mostly concerned with scientific/numerical applications, where I find the current state of things to be a bit chaotic (see Numeric/Numerical/Optimisation/Optimization etc.). I would be glad to help out, and gather intelligence from the community as well via e.g. a poll. Best, Marco (github.com/ocramz)

6 12

Map-to-integer for ciphers?
by 박신환 29 Jul '18

29 Jul '18

For use of ciphers (SHA-256, RSA-2048, etc.), a type must be able to be injectively mapped to integers. It seems `Enum` is currently the closest thing that does this. But `Enum` is supposed to be for arithmetic sequences, so it seems better to define a new typeclass. (Here named `Cipherable`) There are some types that aren't members of `Enum`. For example, `Maybe`, `[]`, etc. They seem okay to be Cipherable. Hence: {-# LANGUAGE ScopedTypeVariables #-} instance Cipherable a => Cipherable (Maybe a) where toEnum 0 = Nothing toEnum n = Just (toEnum n) fromEnum Nothing = 0 fromEnum (Just x) = 1 + fromEnum x instance forall a. (Cipherable a, Bounded a) => Cipherable [a] where toEnum 0 = [] toEnum n = let (q,r) = (n-1) `quotRem` (1 + fromEnum (maxBound :: a)) in toEnum r : toEnum q fromEnum [] = 0 fromEnum (x:xs) = 1 + fromEnum x + (1 + fromEnum (maxBound :: a)) * fromEnum xs instance Cipherable Void where toEnum = errorWithoutStackTrace "Cipher.Cipherable.Void.toEnum" fromEnum = absurd (Besides, it is possible to re-write that of `[]` without ScopedTypeVariables? I see no way...)

2 3

atomicModifyIORef' strictness
by David Feuer 14 Jul '18

14 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