Semigroup, Monoid, Foldable and Traversable

Reusable structure

Semigroup describes types with an associative combining operation <>: strings and lists concatenate, Max and Min keep extremes, Maps merge. Monoid adds an identity element mempty, so mconcat can combine any number of values, including zero. Newtype wrappers choose which monoid you mean for numbers: Sum, Product, Any, All, First and Last. Because combining is associative, monoidal summaries can be computed in parallel or incrementally. Foldable generalises folding to any container (lists, Maybe, Map, Set, trees): sum, length, elem, maximum, foldr and foldMap (map each element to a monoid and combine) work on all of them. Traversable generalises map with effects: traverse applies an effectful function to every element and collects the results inside the effect, so validating a list of inputs returns either all results or the first failure, and mapM_/traverse_ run effects for their side effects only. These classes let you write functions once for every container type.

Monoids and traversals

foldMap with newtype wrappers, traverse for validation.

import Data.Monoid (Sum (..), Any (..))
import Data.Semigroup (Max (..))
import Data.Foldable (traverse_)
import qualified Data.Map.Strict as Map
import Text.Read (readMaybe)

data Order = Order { city :: String, totalPaise :: Int, express :: Bool }

summary :: [Order] -> (Int, Int, Bool)
summary orders =
  let (Sum revenue, Max largest, Any anyExpress) =
        foldMap (\o -> (Sum (totalPaise o), Max (totalPaise o), Any (express o))) orders
  in (revenue, largest, anyExpress)

parseQty :: String -> Either String Int
parseQty s = maybe (Left ("not a number: " ++ s)) Right (readMaybe s)

main :: IO ()
main = do
  let orders = [Order "Pune" 120000 False, Order "Delhi" 30000 True, Order "Pune" 80000 False]
  print (summary orders)                                   -- (230000,120000,True)
  print (Map.fromListWith (<>) [(city o, Sum (totalPaise o)) | o <- orders])
  print (traverse parseQty ["1", "2", "3"])                -- Right [1,2,3]
  print (traverse parseQty ["1", "x", "y"])                -- Left "not a number: x"
  print (sum (Just 5), length (Just 'a'), maximum (Map.fromList [(1 :: Int, 'b'), (2, 'z')]))   -- (5,1,'z')
  traverse_ print [1, 2, 3 :: Int]

foldMap needs a Monoid

Max a is a Semigroup for any ordered type, but a Monoid only when a is also Bounded. summary works because Max Int has mempty = minBound, which is also what an empty order list returns. For unbounded types such as Integer, wrap values in Maybe or fold a NonEmpty list with sconcat.

Quick check: What does traverse do when the function returns Left for one element in Either?

• Skips that element
• Throws an exception
• Returns that Left for the whole result
• Returns Right with an empty list