January 2022 - Libraries

Faster `elem` "Hack" for Data.Set?
by Viktor Dukhovni 30 Jan '22

30 Jan '22

In a recent "Folding the unfoldable" "gist": https://oleg.fi/gists/posts/2022-01-25-folding-unfoldable.html Oleg describes a way to make unboxed Vectors Foldable: There is another way to make Foldable work, with a data Hack a b where Hack :: U.Vector a -> Hack a a This is a two type-parameter wrapper, but the types are always the same! (I wish that could be a newtype). The Foldable instance is simply: instance U.Unbox a => Foldable (Hack a) where foldr f z (Hack v) = U.foldr f z v foldl' f z (Hack v) = U.foldl' f z v In the associated Reddit thread https://www.reddit.com/r/haskell/comments/sd6gel/comment/hudmsis/?utm_sourc… it was observed that a similar approach can be used to give Data.Set a performant `elem` method (code copied below my signature). It is somewhat tempting to consider whether the "Hack" ought to be built-in directly into the real Data.Set: https://www.reddit.com/r/haskell/comments/sd6gel/comment/huil070/?utm_sourc… type Set a = SetImpl a a data SetImpl a b where Bin :: {-# UNPACK #-} !Size -> !a -> !(SetImpl a) -> !(SetImpl a) -> SetImpl a a Tip :: SetImpl a a type Size = Int instance Ord a => Foldable (SetImpl a) where ... elem _ Tip = False elem x (Bin _ y l r) = case compare x y of EQ -> True LT -> elem x l GT -> elem x r ... This representation does not seem to carry any obvious runtime overhead, and gives Set a performant `elem` method. The only change from the status quo would be that folds would not be available for empty or singleton sets with non-Ord elements (currently possible with Set). How much of a loss would it be to constrain the element type of empty and singleton sets used in folds? Are there other issue that make the above impractical? -- Viktor. type OSet a = OrdSet a a data OrdSet a b where OSet :: Set.Set a -> OrdSet a a instance Ord a => Foldable (OrdSet a) where fold (OSet xs) = fold xs foldMap f (OSet xs) = foldMap f xs foldMap' f (OSet xs) = foldMap' f xs foldr f z (OSet xs) = foldr f z xs foldr' f z (OSet xs) = foldr' f z xs foldl f z (OSet xs) = foldl f z xs foldl' f z (OSet xs) = foldl' f z xs foldr1 f (OSet xs) = foldr1 f xs foldl1 f (OSet xs) = foldl1 f xs toList (OSet xs) = toList xs null (OSet xs) = null xs length (OSet xs) = length xs -- The point of the exercise is `elem` elem e (OSet xs) = Set.member e xs maximum (OSet xs) = maximum xs minimum (OSet xs) = minimum xs sum (OSet xs) = sum xs product (OSet xs) = product xs instance Eq a => Eq (OSet a) where (OSet xs) == (OSet ys) = xs == ys instance (Eq a, Ord a) => Ord (OSet a) where compare (OSet xs) (OSet ys) = compare xs ys empty :: Ord a => OSet a empty = OSet Set.empty singleton :: Ord a => a -> OSet a singleton = OSet . Set.singleton fromList :: Ord a => [a] -> OSet a fromList = OSet . Set.fromList (\\) :: Ord a => OSet a -> OSet a -> OSet a (OSet xs) \\ (OSet ys) = OSet (xs Set.\\ ys) alterF :: (Ord a, Functor f) => (Bool -> f Bool) -> a -> OSet a -> f (OSet a) alterF f x (OSet xs) = fmap OSet $ Set.alterF f x xs ...

5 6

Adding a "Map k a -> Set (Arg k a)" function to containers
by Joseph C. Sible 27 Jan '22

27 Jan '22

I opened https://github.com/haskell/containers/issues/814 about adding this function to the containers package: import qualified Data.Map.Internal as Map import qualified Data.Set.Internal as Set import Data.Semigroup (Arg(..)) mapToArgSet :: Map.Map k a -> Set.Set (Arg k a) mapToArgSet Map.Tip = Set.Tip mapToArgSet (Map.Bin sz k v l r) = Set.Bin sz (Arg k v) (mapToArgSet l) (mapToArgSet r) Does anyone have any suggestions or improvements for this? In particular, I'm sure there's a less clunky name that I just can't think of. Thanks, Joseph C. Sible

2 2

whither is an MTL that supports transformers >= 0.6?
by Carter Schonwald 21 Jan '22

21 Jan '22

Hey All, I was looking around and noticed we still lack that ... anyone have decent visibility ? -Carter

2 2

Proposal: export liftA2 from Prelude
by Andreas Abel 14 Jan '22

14 Jan '22

Proposal: export liftA2 from Prelude. More information and discussion here: https://gitlab.haskell.org/ghc/ghc/-/issues/20945 Discussion period 2 weeks TL;DR - Fixes weird qualification in warning • No explicit implementation for either ‘<*>’ or ‘GHC.Base.liftA2’ • In the instance declaration for ‘Applicative <Foo>’ - Was considered for GHC 8.2 but never followed up

2 1

Takeover of cryptonite and memory
by Hécate 09 Jan '22

09 Jan '22

Hello Hackage admins, Several board members of the Haskell Foundation have tried for many months to contact Vincent Hanquez regarding his cryptography packages, that have become cornerstones of the ecosystem and of industrial Haskell products. Recently, I have received complaints and questions about those packages being major blockers for the adoption of newer GHC versions. I have thus made another home for those packages with the explicit aim of diversifying the ownership and maintenance so that we do not have such a high bus factor. I would like to start a Hackage takeover procedure for the following packages: * cryptonite * memory Their new home would be the haskell-cryptography GitHub organisation, and emails have been sent to past contributors, in order to maintain continuity in the development teams. My Hackage username is "hecate". Chris Dornan (in CC) is also involved, and his username is "ChrisDornan". Moreover, as a board member of the Haskell Foundation, I intend to provide resources to help coordination between the stakeholders of these packages, in the community and industry. We will be at your disposal for any question. Cheers. Hécate ✨ 🐦: @TechnoEmpress IRC: Hecate WWW: https://glitchbra.in RUN: BSD

1 0

Storable instance of () is broken
by Harendra Kumar 05 Jan '22

05 Jan '22

The Storable instance of () is defined in the "Foreign.Storable" module of the "base" package as follows: instance Storable () where sizeOf _ = 0 alignment _ = 1 peek _ = return () poke _ _ = return () The size of () is defined as 0. It sounds absurd for a Storable to have a size of 0? This means that we can read an infinite number of () type values out of nothing (no memory location required) or store an infinite number of () type values without even requiring a memory location to write to. This is causing a practical problem in our Storable array implementation. The array is constrained to a Storable type. Since () has a Storable instance, one can store () in the Storable array. But it causes a problem because we determine the array element size using sizeOf on the type. For () type it turns out to be 0. Essentially, the array of () would always be of size 0. Now, we cannot determine the length of the array from its byte length as you could store infinite such elements in an empty array. The Storable instance of () seems to be an oddity and makes us use a special case everywhere in the code to handle this, and this special casing makes it highly prone to errors when we change code. Can this be fixed? Is there a compelling argument to keep it like this? A possible fix could be to represent it by a single byte in memory which can be discarded when reading or writing. Another alternative is to not provide a Storable instance for it at all. Let the users write their own if they need it. If you think this does not have a problem, can you suggest how to elegantly handle the array implementation problem as I described above? Thanks, Harendra

12 24