August 2020 - Libraries

Improving the instances of Data.Functor.{Product,Sum}
by chessai . 26 Jan '21

26 Jan '21

Consider the Eq instance for these types. Currently we rely on: (Eq1 f, Eq1 g, Eq a) But some potential improvements include changing to: (Eq (f (g a))) (FlexibleContexts) or (forall x. Eq x => Eq (f x), forall x. Eq x => Eq (g x), Eq a) (QuantifiedConstraints) There was a discussion sometime last year about the same thing regarding Semigroup/Monoid instances for `Compose` [1]. Additionally, the question has been raised again for Data.Functor.{Product,Sum} on Gitlab [2, 3]. There has been no consensus in either case, but that's not too worrying as both discussions have been brief. I'm currently not happy with the {Eq,Ord,Show}{1,2} family of classes, and would hope to work toward their removal, or at least the shrinking of their presence in base. Even though the linked proposals are about a single type, I think it's important that we come up with a decision and stick with it. Having different APIs for different types here would be pretty confusing, and some could even say sloppy. Please let me know your thoughts. [1]: https://mail.haskell.org/pipermail/libraries/2019-July/029771.html [2]: https://gitlab.haskell.org/ghc/ghc/issues/17015 [3]: https://gitlab.haskell.org/ghc/ghc/merge_requests/1704

10 22

clamp function in base
by Sandy Maguire 12 Sep '20

12 Sep '20

Hi all, It seems to me that base is missing the very standard function `clamp :: Ord a => a -> a -> a -> a`: ```haskell clamp :: Ord a => a -> a -> a -> a clamp low high = min high .max low ``` I propose it be added to Data.Ord. It's useful, generic, and non-trivial to get right (the "big" number goes with "min" -- causes me cognitive dissonance every time.) Thanks, Sandy

11 20

Operator precedence help
by David Feuer 04 Sep '20

04 Sep '20

I'm trying to work out appropriate precedences for operators and pattern synonyms in my brand-new compact-sequences package. I currently have stacks and queues, but I will soon have deques, so let's pretend. For consistency, operators will match pattern synonyms. (<|), pattern (:<) :: a -> Deque a -> Deque a (|>), pattern (:>) :: Deque a -> a -> Deque a :< and :> need to have different precedence to allow things like a :< b :< xs :> c :> d to work nicely, but what numbers should I pick? I also have cons and snoc functions. Should I give their backticked spellings fixity declarations? If so, with what precedences?

9 21

Fwd: The Char Kind: proposal
by Daniel Rogozin 01 Sep '20

01 Sep '20

Greetings, I would like to propose and discuss several changes related to the character kind. Some of those changes were implemented jointly with Rinat Stryungis, my Serokell teammate. The purpose of this patch is to provide a possibility of analysing type-level strings (symbols) as term-level ones. This feature allows users to implement such programs as type-level parsers. One needs to have full-fledged support of type-level characters as well as we already have for strings and numbers. In addition to this functionality, it makes sense to introduce the set of type-families, counterparts of functions defined in the Data.Char module in order to work with type-level strings and chars as usual (more or less). For more convenience, it’s worth having some of the character-related type families as built-ins and generating the rest of ones as type synonyms. The patch fixes #11342, an issue opened by Alexander Vieth several years ago. In this patch, we introduced the Char Kind, a kind of type-level characters, with the additional type-families, type-level counterparts of functions from the `Data.Char` module. In contrast to Vieth’s approach, we use the same Char type and don’t introduce the different `Character` kind. We provide slightly more helpers to work with the Char kind, see below. You may take a look at this merge request with proposed updates: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/3598. First of all, we overview the additional type families implemented by us in this patch. type family CmpChar (a :: Char) (b :: Char) :: Ordering Comparison of type-level characters, as a type family. A type-level analogue of the function `compare` specified for characters. type family LeqChar (a :: Char) (b :: Char) :: Bool This is a type-level comparison of characters as well. `LeqChar` yields a Boolean value and corresponds to `(<=)`. type family ConsSymbol (a :: Char) (b :: Symbol) :: Symbol This extends a type-level symbol with a type-level character type family UnconsSymbol (a :: Symbol) :: Maybe (Char, Symbol) This type family yields type-level `Just` storing the first character of a symbol and its tail if it is nonempty and `Nothing` otherwise. Type-level counterparts of the functions `toUpper`, `toLower`, and `toTitle` from 'Data.Char'. type family ToUpper (a :: Char) :: Char type family ToLower (a :: Char) :: Char type family ToTitle (a :: Char) :: Char These type families are type-level analogues of the functions `ord` and `chr` from Data.Char respectively. type family CharToNat (a :: Char) :: Nat type family NatToChar (a :: Nat) :: Char A type-level analogue of the function `generalCategory` from `Data.Kind`. type family GeneralCharCategory (a :: Char) :: GeneralCategory The second group of type families consists of built-in unary predicates. All of them are based on their corresponding term-level analogues from `Data.Char`. The precise list is the following one: type family IsAlpha (a :: Char) :: Bool type family IsAlphaNum (a :: Char) :: Bool type family IsControl (a :: Char) :: Bool type family IsPrint (a :: Char) :: Bool type family IsUpper (a :: Char) :: Bool type family IsLower (a :: Char) :: Bool type family IsSpace (a :: Char) :: Bool type family IsDigit (a :: Char) :: Bool type family IsOctDigit (a :: Char) :: Bool type family IsHexDigit (a :: Char) :: Bool type family IsLetter (a :: Char) :: Bool We also provide several type-level predicates implemented via the `GeneralCharCategory` type family. type IsMark a = IsMarkCategory (GeneralCharCategory a) type IsNumber a = IsNumberCategory (GeneralCharCategory a) type IsPunctuation a = IsPunctuationCategory (GeneralCharCategory a) type IsSymbol a = IsSymbolCategory (GeneralCharCategory a) type IsSeparator a = IsSeparatorCategory (GeneralCharCategory a) Here is an example of an implementation: type IsMark a = IsMarkCategory (GeneralCharCategory a) type family IsMarkCategory (c :: GeneralCategory) :: Bool where IsMarkCategory 'NonSpacingMark = 'True IsMarkCategory 'SpacingCombiningMark = 'True IsMarkCategory 'EnclosingMark = 'True IsMarkCategory _ = 'False Built-in type families I described above are supported with the corresponding definitions and functions in `compiler/GHC/Builtin/Names.hs`, `compiler/GHC/Builtin/Types.hs`, and `compiler/GHC/Builtin/Types/Literals.hs`. In addition to type families, our patch contain the following updates: 1. parsing the 'x' syntax 2. type-checking 'x' :: Char 3. type-checking Refl :: 'x' :~: 'x' 4. Typeable / TypeRep support 5. template-haskell support 6. Haddock related updates 7. tests At the moment, the merge request has some minor imperfections for polishing and improvement, but we have a prototype of a possible implementation. The aim of my email is to receive your feedback on this patch. Kind regards, Danya Rogozin.

3 2

Consider adding `classify`.
by Ignat Insarov 24 Aug '20

24 Aug '20

Hello. There has been [a question on Stack Overflow][1] asking for a way to group a list by an equivalence relation. Several answers were proposed over time, and I too [have offered a variant][2]. [I also wrote a benchmark.][3] I propose that the function be added to the standard libraries. [1]: https://stackoverflow.com/q/8262179 [2]: https://stackoverflow.com/a/57761458 [3]: https://github.com/kindaro/classify-benchmark.git

4 4

Consider adding `converge` and friends.
by Ignat Insarov 24 Aug '20

24 Aug '20

Hello… This function first appeared _(to my knowledge)_ in [a Stack Overflow answer][1]. I found it useful several times, and eventually [I extended it to a family of 4 derived functions][2]: `converge`, `convergeBy`, `fixp` and `fixpBy`. * `convergeBy` is like `takeWhile` but with a binary predicate. * `converge` cuts a list at a point where it starts to repeat itself. * `fixp` takes the last element. These operations are useful in many practical cases. For example, the Newton-Raphson approximation method: λ r a = \x -> (x + a/x) / 2 λ fixp (r 2) 1 1.414213562373095 Or let us compute the alternating group A₄: λ import qualified Data.List as List λ xs */ ys = fmap (xs !!) ys λ generate1 gens elems = List.union elems [ elem */ gen | elem <- elems, gen <- gens ] λ ε = [0.. 3] λ rota3 = [1, 2, 0, 3] λ rota3' = [0, 2, 3, 1] λ length $ fixp (generate1 [rota3, rota3']) [ε] 12 I propose adding these functions to `Data.List`. [1]: https://stackoverflow.com/a/7443379 [2]: https://stackoverflow.com/q/48353457

4 3

Proposal: plug the space leak in transpose
by David Feuer 24 Aug '20

24 Aug '20

Data.List.transpose, unfortunately, can potentially leak space. The problem is that it walks a list of lists twice: once to get the heads and once to get the tails. Depending on the way the result is consumed, it's possible that heads or tails that are never used will be retained by the garbage collector. I have a fix[*] that probably makes the function slower in typical cases, but that plugs the leak. What do y'all say? * https://gitlab.haskell.org/ghc/ghc/-/merge_requests/3882

2 2

exception for invalid byte sequences
by Henning Thielemann 21 Aug '20

21 Aug '20

Documentation for hGetChar et.al. [1] does not mention the exception for invalid byte sequences in the current encoding. It seems it throws an exception called "invalid argument": IO> h <- IO.openFile "/tmp/invalid" IO.ReadMode IO> IO.hGetChar h *** Exception: /tmp/invalid: hGetChar: invalid argument (invalid byte sequence) https://hackage.haskell.org/package/base-4.14.0.0/docs/System-IO.html#v:hGe…

1 0

Module naming help
by David Feuer 20 Aug '20

20 Aug '20

I'm really close to making a second release of the compact-sequences package (now with deques!), but I'd like to get a bit of help with module naming/renaming now to try to avoid more painful name changes later, when my package will hopefully have actual users. Currently, I have three "base" implementations, Data.CompactSequence.Stack.Internal Data.CompactSequence.Queue.Internal Data.CompactSequence.Deque.Internal Each of these implements an abstract datatype representing a stack/queue/deque of fixed-size arrays. Additionally, I have "simple" implementations Data.CompactSequence.Stack.Simple Data.CompactSequence.Queue.Simple Data.CompactSequence.Deque.Simple that just use the base implementations with arrays of size 1. These are great as a proof of concept and for testing, but I expect their performance to be quite bad [1]. To solve the problem, I need to write separate datatypes to handle the top of the structure (the first k elements of a stack, or a prefix and suffix of a queue or deque). There are various different approaches to this, with various trade-offs and tuning factors. The first I'd like to implement, for stacks and queues, would look exactly like the base implementations but with elements instead of arrays in the first node. What might I call these? Another option would be to just use linked lists with various length bounds. Yet another would use stacks that look like data Stack6 a = One a | Two a a | ... | Six a a a a a a for various size bounds. But I have no idea how to name any of these things. A second issue: I may eventually want to add alternative base implementations to support O(log n) `length` and significantly more efficient (but still O(n)) splitting, appending, and indexing operations. How might *those* work into the name situation? Finally, I'll eventually want to offer support for unpacked data, probably via backpack. That will involve base implementations that work with ByteArray rather than SmallArray. Names, names, I hate names! 1. In the first node of the data structure, each sequence element is represented as a pointer to a SmallArray of one element. Yuck. The situation improves considerably further in, with the array size doubling in successive nodes. 2. For deques, where code size is already a matter of some concern, this approach seems likely to exacerbate the issue, but a simpler variant should work well enough.

1 0

Null Pointer Pattern
by Andrew Martin 19 Aug '20

19 Aug '20

Foreign.Ptr provides nullPtr. It would make some of my code more terse if this was additionally provided as a pattern synonym. The pattern synonym can be defined as: {-# language ViewPatterns #-} {-# language PatternSynonyms #-} module NullPointerPattern ( pattern Null ) where import Foreign.Ptr (Ptr,nullPtr) pattern Null :: Ptr a pattern Null <- ((\x -> x == nullPtr) -> True) where Null = nullPtr Any here is example of code that becomes more terse once this is available: foo :: IO (Either Error (Ptr Foo)) foo = do p <- initialize mySettings if p == nullPtr then pure (Left InitializeFailure) else pure (Right p) With the pattern synonym, we are able to take advantage of LambdaCase: foo :: IO (Either Error (Ptr Foo)) foo = initialize mySettings >>= \case Null -> pure (Left InitializeFailure) p -> pure (Right p) I'm curious what others think. -- -Andrew Thaddeus Martin

4 7