Skip to content

Draft: Add Control.Applicative.foldA

Chris Martin requested to merge chris-martin/ghc:foldA into master

I propose this small addition to base because I think it gets at something essential about the relationship between Foldable and Alternative, makes the Alternative class a bit more convenient to work with, and makes it a bit easier to understand.

(Alternative f, Foldable t) => t a -> f a

This is a utility we can observe in several libraries:

  1. In Agda
-- | Branch over a 'Foldable' collection of values.
foldA :: (Alternative f, Foldable t) => t a -> f a
foldA = foldMapA pure
  1. In fused-effects
-- | Nondeterministically choose an element from a 'Foldable' collection.
-- This can be used to emulate the style of nondeterminism associated with
-- programming in the list monad:
--
-- @
--   pythagoreanTriples = do
--     a <- oneOf [1..10]
--     b <- oneOf [1..10]
--     c <- oneOf [1..10]
--     guard (a^2 + b^2 == c^2)
--     pure (a, b, c)
-- @
oneOf :: (Foldable t, Alternative m) => t a -> m a
oneOf = foldMapA pure
  1. In list-transformer
{-| Convert any collection that implements `Foldable` to another collection that
    implements `Alternative`

    For this library, the most common specialized type for `select` will be:

> select :: [a] -> ListT IO a
-}
select :: (Foldable f, Alternative m) => f a -> m a
select = Data.Foldable.foldr cons empty
  where
    cons x xs = pure x <|> xs
  1. In list-t; here it is specialized to ListT and uses MonadPlus rathen than Alternative, but it is still essentially the same as the rest because the Alternative and MonadPlus instances are the same for the ListT type.
fromFoldable :: (Monad m, Foldable f) => f a -> ListT m a
fromFoldable = 
  foldr cons mzero

The haddock comment in the PR here is pieced together from the documentation from the above examples.

I suggest adopting the name foldA mostly because, of the choices above, it conflicts with the least with names in other packages.

Edited by Andreas Klebinger

Merge request reports