Re: Proposal: Add 'Foldable1' to base

Seems reasonable to me! I definitely agree that we ought to add a strict foldMap1 to the version found in semigroupoids. On Wed, Dec 9, 2020 at 11:08 PM David Feuer wrote:

That seems rather large to me, and some of those methods don't have much if any historical usage. I'd recommend starting with a slightly smaller class. It's always easier to add more later than to remove. My suggestion:

foldMap1 :: Semigroup m => (a -> m) -> t a -> m

foldMap1' :: Semigroup m => (a -> m) -> t a -> m

toNonEmpty :: t a -> NonEmpty a

The rest can be exported as functions, rather than methods, to begin with.

On Thu, Dec 10, 2020, 1:38 AM Reed Mullanix wrote:

...

With the recent discussion around the addition of 'intersection' to containers, I think it might be a good time to re-open the discussion surrounding adding 'Foldable1' to base.

For context, 'Foldable1' would be a subclass of 'Foldable' that abstracts folds over non-empty containers. Alternatively, it can be seen as a method of combining together the elements of a container using a semigroup. The contents of this class have been discussed previously (See [1,2]), and the version presented in this proposal is taken from [1].

class Foldable t => Foldable1 t where {-# MINIMAL foldMap1 | foldr1map #-}

fold1 :: Semigroup m => t m -> m

-- the defining member, like foldMap but only asking for Semigroup foldMap1 :: Semigroup m => (a -> m) -> t a -> m

-- strict foldMap1, cf foldMap' foldMap1' :: Semigroup m => (a -> m) -> t a -> m

-- analogue of toList toNonEmpty :: t a -> NonEmpty a

-- left&right, strict&non-strict folds foldr1 :: (a -> a -> a) -> t a -> a foldr1' :: (a -> a -> a) -> t a -> a foldl1 :: (a -> a -> a) -> t a -> a foldl1' :: (a -> a -> a) -> t a -> a

-- these can have efficient implementation for NonEmptySet maximum1 :: Ord a => t a -> a minimum1 :: Ord a => t a -> a

-- head1 have efficient implementation for NonEmpty and Tree -- last1 for symmetry head1 :: t a -> a last1 :: t a -> a

-- fold variants with premap. -- Without this map, we cannot implement foldl using foldr etc. foldrMap1 :: (a -> b) -> (b -> b -> b) -> t a -> b foldlMap1' :: (a -> b) -> (b -> b -> b) -> t a -> b foldlMap1 :: (a -> b) -> (b -> b -> b) -> t a -> b foldrMap1' :: (a -> b) -> (b -> b -> b) -> t a -> b

This has a couple of benefits. On the practical side, we can provide total alternatives to existing partial functions (IE: 'foldr1' and friends). It also enables us to fold over containers using a semigroup instance, which comes up suprisingly often.

Naming: -------------------------------------------------------------------------------- Historically, the biggest source of controversy with this proposal has been over the name. The class currently exists in semigroupoids [3] under the name 'Foldable1', though there was some discussion around renaming it to 'SemiFoldable' [4]. However, if we keep the name unchanged, it makes the migration path nice and straightforward, and the possible name conflict with Data.Functor.Classes seems unlikely.

Migration: -------------------------------------------------------------------------------- If we decide to go with 'Foldable1' as the name, we should be able to perform this change with 0 breakage.

References: [1] https://mail.haskell.org/pipermail/libraries/2019-November/030059.html [2] https://gitlab.haskell.org/ghc/ghc/-/issues/13573 [3] https://hackage.haskell.org/package/semigroupoids-5.3.4/docs/Data-Semigroup-... [4] https://github.com/ekmett/semigroupoids/issues/26 _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries