January 2016 - Libraries

Proposal: make minimumBy/maximumBy go through foldl', not foldr1
by Roman Cheplyaka 11 Feb '16

11 Feb '16

I just realized (thanks to this reddit thread[1]) that minimumBy is now implemented through foldr1. Previously (before FTP), minimumBy from Data.List used foldl1, while minimumBy from Data.Foldable used foldr1. I think that the way these were merged was a mistake. Let's admit that the absolute majority of use cases for minimumBy are numbers, for which the comparison functions are strict in both arguments. Even for something like Bool, where comparison could potentially be in one of the arguments, the standard compare method is derived and is strict. Now, for Foldable, there isn't necesarily a connection between the direction and the way fold is performed. For example, for Data.Map.Map both folds are tail-recursive. Yet foldr is non-tail-recursive at least for: - good old lists - anything that uses the same convention for foldl/foldr as lists - anything that defines its foldable instance through conversion to lists - anything that uses the default implementation of foldr/foldr1 I also put a simple microbenchmark[2] to show the difference in performance; on it, the proposed implementation is more than 20x faster than the current one. [1]: https://www.reddit.com/r/haskell/comments/3qpefo/a_very_unfortunate_error_m… [2]: http://lpaste.net/714261956202070016

8 12

Bug tracker for cpphs
by Andrés Sicard-Ramírez 01 Feb '16

01 Feb '16

Hi Malcolm, (I'm resending my old question to the libraries mailing list) Is there a bug tracker for cpphs? Best, -- Andrés

4 6

Fwd: Bug tracker for cpphs
by Theodore Lief Gannon 30 Jan '16

30 Jan '16

Chiming in to agree: don't be afraid of Github, it's very ergonomic. In particular, it's safe to only look at the bits relevant to your immediate needs; you don't have to know the whole system before doing anything. On Sat, Jan 30, 2016 at 12:17 PM, Andrés Sicard-Ramírez <asr(a)eafit.edu.co> wrote: > Hi Malcolm, > > On 30 January 2016 at 06:49, Malcolm Wallace <malcolm.wallace(a)me.com> > wrote: > > If someone with more experience of setting up trackers were to do the > work of creating one for cpphs (maybe on github? is that where everyone > hangs out these days?), I might be persuaded to use it. :-) > > To you set up a bug tracker in GitHub for cpphs requires only two steps: > > 1. Create a GitHub account (you already have one) > 2. Create the cpphs repository with the issues enabled. > > Best, > > -- > Andrés > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

2 1

Proposal: Data.Bool.implies
by Niklas Hambüchen 26 Jan '16

26 Jan '16

I propose to add to Data.Bool: -- | Boolean implication. implies :: Bool -> Bool -> Bool implies True x = x implies False _ = True infix 4 `implies` -- same as (==) The request for this is quite old (see e.g. http://neilmitchell.blogspot.de/2007/02/logical-implication-in-haskell.html) I believe that by not trying to use an operator for it, and keeping it in Data.Bool, we can avoid doing anything wrong. A quick superficial search on Stackage Hoogle suggests that adding this function should create no breakage (4 packages define their own function called `implies`, none of them import Data.Bool). `infix` instead of `infixl` or `infixr` to force you to bracket it; for the same reason it has the same precedence as `==`.

17 29

Type class for sanity
by David Feuer 25 Jan '16

25 Jan '16

Since type families can be stuck, it's sometimes useful to restrict things to sane types. At present, the most convenient way I can see to do this in general is with Typeable: type family Foo x where Foo 'True = Int class Typeable (Foo x) => Bar x where blah :: proxy x -> Foo x This will prevent anyone from producing the bogus instance instance Bar 'False where blah _ = undefined Unfortunately, the Typeable constraint carries runtime overhead. One possible way around this, I think, is with a class that does just sanity checking and nothing more: class Sane (a :: k) instance Sane Int instance Sane Char instance Sane 'False instance Sane 'True instance Sane '[] instance Sane '(:) instance Sane (->) instance Sane 'Just instance Sane 'Nothing instance (Sane f, Sane x) => Sane (f x) To really do its job properly, Sane would need to have instances for all sane types and no more. An example of an insane instance of Sane would be instance Sane (a :: MyKind) which would include stuck types of kind MyKind. Would it be useful to add such an automatic-only class to GHC? David

5 9

Add traverseWithIndex to Data.Sequence
by David Feuer 20 Jan '16

20 Jan '16

Indexed traversals seem to be pretty popular these days, and sequences should be able to support them efficiently. At present, the best options are 1. Thread a counter through. This doesn't work well for weird things like lazy State. 2. Use zipWith first to add indices, then traverse. This adds a smaller, but still asymptotic, penalty to the same sorts of unusual functors, and also adds constant-factor overhead to strict ones that the counter threading wouldn't. I propose the following, modified mechanically from mapWithIndex. It should be about as efficient as possible in all cases. traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b) traverseWithIndex f' (Seq xs') = Seq <$> traverseWithIndexTree (\s (Elem a) -> Elem <$> f' s a) 0 xs' where traverseWithIndexTree :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> FingerTree a -> f (FingerTree b) traverseWithIndexTree _ s Empty = s `seq` pure Empty traverseWithIndexTree f s (Single xs) = Single <$> f s xs traverseWithIndexTree f s (Deep n pr m sf) = sPspr `seq` sPsprm `seq` Deep n <$> traverseWithIndexDigit f s pr <*> traverseWithIndexTree (traverseWithIndexNode f) sPspr m <*> traverseWithIndexDigit f sPsprm sf where sPspr = s + size pr sPsprm = s + n - size sf traverseWithIndexDigit :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Digit a -> f (Digit b) traverseWithIndexDigit f s (One a) = One <$> f s a traverseWithIndexDigit f s (Two a b) = sPsa `seq` Two <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexDigit f s (Three a b c) = sPsa `seq` sPsab `seq` Three <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b traverseWithIndexDigit f s (Four a b c d) = sPsa `seq` sPsab `seq` sPsabc `seq` Four <$> f s a <*> f sPsa b <*> f sPsab c <*> f sPsabc d where sPsa = s + size a sPsab = sPsa + size b sPsabc = sPsab + size c traverseWithIndexNode :: (Applicative f, Sized a) => (Int -> a -> f b) -> Int -> Node a -> f (Node b) traverseWithIndexNode f s (Node2 ns a b) = sPsa `seq` Node2 ns <$> f s a <*> f sPsa b where sPsa = s + size a traverseWithIndexNode f s (Node3 ns a b c) = sPsa `seq` sPsab `seq` Node3 ns <$> f s a <*> f sPsa b <*> f sPsab c where sPsa = s + size a sPsab = sPsa + size b

5 5

Re: Proposal: Add conspicuously missing Functor instances for tuples
by Ryan Scott 18 Jan '16

18 Jan '16

Edward Kmett outlines his reasons why he finds instances for (,) useful here: https://www.reddit.com/r/haskell/comments/3pfg7x/either_and_in_haskell_are_… Speaking for myself, I find the Traversable instance for (,) incredibly useful. It's quite nice to build up a list of results alongside a state (i.e, (state, [result]) ), and then traverse over each of the results such that the new results each have their own copy of the state (i.e., [(state, result)] ). That kind of patterns arises quite often in lensy code, and the Traversable instance for (,) is perfect for the job. Right now, if you want to have two different states, you have to employ a kludge (something like ((state1, state2), [result]) ) to get around the fact that there's no Traversable instance for (,,), (,,,), etc. Ryan S.

2 4

Re: Proposal: Add Semigroup and Monoid instances for (:~:)
by Ryan Scott 17 Jan '16

17 Jan '16

+1, with a one stipulation: I'd rather the Semigroup instance be: instance Semigroup (a :~: b) where Refl <> Refl = Refl and similarly for Monoid(mappend). It's a minor quibble, but the documentation [1] for (:~:) says that there's only a proof term for a ~ b if it's inhabited by a terminating value, so performing a strict pattern match seems like the best default here. Ryan S. ----- [1] http://hackage.haskell.org/package/base-4.8.1.0/docs/Data-Type-Equality.htm…:

2 2

Proposal: Add Peano numbers to base
by M Farkas-Dyck 14 Jan '16

14 Jan '16

I have seen these redefined many times now. Examples: https://hackage.haskell.org/package/numericpeano-0.2.0.0/docs/Numeric-Peano… https://hackage.haskell.org/package/numeric-prelude-0.4.2/docs/Number-Peano… https://hackage.haskell.org/package/type-fun-0.0.1/docs/TypeFun-Data-Peano.… https://hackage.haskell.org/package/number-0.1.1.0/docs/Data-Number-Peano.h… https://hackage.haskell.org/package/Peano-0.0.4/docs/Data-Peano.html#t:Peano I often see them used as DataKinds. Too, operations on them can be lazy, which is sometimes useful. I filed a ticket: https://ghc.haskell.org/trac/ghc/ticket/11402 Discussion period: 2 weeks

7 7

Proposal: Add Semigroup and Monoid instances for (:~:)
by David Feuer 14 Jan '16

14 Jan '16

These are not likely to be *useful*, but they fall easily into the general bucket of "exactly one sensible instance exists". instance Semigroup (a :~: b) where r <> _ = r instance a ~ b => Monoid (a :~: b) where mempty = Refl mappend r _ = r

3 3