# Semigroup, Monoid, Foldable and Traversable — Haskell

Source: https://www.geekswithgeeks.com/en/haskell/e-classes

> Combine values generically and work with any container.

## Reusable structure

**`Semigroup`** describes types with an associative combining operation **`<>`**: strings and lists concatenate, `Max` and `Min` keep extremes, `Map`s 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.

```haskell
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`.

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

- [ ] Skips that element
- [ ] Throws an exception
- [x] Returns that Left for the whole result
- [ ] Returns Right with an empty list

*Answer:* Returns that Left for the whole result. traverse sequences the Either effects, short-circuiting on the first Left.