Folding Cheat Sheet #8

Folding with Monoids.

keywords: associativity, cats, combine, combineall, fold, folding, foldmap, fp, functional programming, haskell, monoid, scala, semigroup, unit

1. Folding #8 ∶ / \ 𝒂𝟎 ∶ / \ 𝒂𝟏 ∶ / \ 𝒂𝟐 ∶ / \ 𝒂𝟑 𝒇 / \ 𝒂𝟎 𝒇 / \ 𝒂𝟏 𝒇 / \ 𝒂𝟐 𝒇 / \ 𝒂𝟑 𝒆 @philip_schwarz slides by https://fpilluminated.com/
2. 𝑓𝑜𝑙𝑑𝑟 ∷ 𝛼 → 𝛽 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓 𝑥 𝑓𝑜𝑙𝑑𝑟 𝑓 𝑏 𝑥𝑠 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑏 𝑥 𝑥𝑠 𝑓𝑜𝑙𝑑 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛼 ⇒ 𝛼 → 𝛼 𝑓𝑜𝑙𝑑 = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑 𝑥: 𝑥𝑠 = 𝑥 ′𝑚𝑎𝑝𝑝𝑒𝑛𝑑′ 𝑓𝑜𝑙𝑑 𝑥𝑠 𝑚𝑒𝑚𝑝𝑡𝑦 ∷ 𝛼 𝑚𝑎𝑝𝑝𝑒𝑛𝑑 ∷ 𝛼 → 𝛼 → 𝛼 First Duality Theorem of Fold (for all finite lists 𝑥𝑠) 𝑓𝑜𝑙𝑑𝑟 ⊕ 𝑒 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 ⊕ 𝑒 𝑥𝑠 𝑒 ∷ 𝛼 (⊕) ∷ 𝛼 → 𝛼 → 𝛼 𝑓𝑜𝑙𝑑𝑟′ ∷ 𝛼 → 𝛼 𝑓𝑜𝑙𝑑𝑟′ = 𝑒 𝑓𝑜𝑙𝑑𝑟′ 𝑥: 𝑥𝑠 = 𝑥 ⊕ 𝑓𝑜𝑙𝑑𝑟′ 𝑥𝑠 𝑓𝑜𝑙𝑑𝑙′ ∷ 𝛼 → 𝛼 → 𝛼 𝑓𝑜𝑙𝑑𝑙′ 𝑎 = 𝑎 𝑓𝑜𝑙𝑑𝑙′ 𝑎 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙′ 𝑎 ⊕ 𝑥 𝑥𝑠 when the pair (⊕, 𝒆) is a 𝑀𝑜𝑛𝑜𝑖𝑑, i.e. for all 𝑥, 𝑦, and 𝑧 we have 𝑥 ⊕ 𝑦 ⊕ 𝑧 = 𝑥 ⊕ 𝑦 ⊕ 𝑧 𝒆 ⊕ 𝑥 = 𝑥 and 𝑥 ⊕ 𝒆 = 𝑥 in other words, ⊕ is associative with unit 𝒆. 1𝐴 ∶ A ⊕ ∷ A × A → A
3. 𝑓𝑜𝑙𝑑 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛼 ⇒ 𝛼 → 𝛼 𝑓𝑜𝑙𝑑 = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑 𝑥: 𝑥𝑠 = 𝑥 ′𝑚𝑎𝑝𝑝𝑒𝑛𝑑′ 𝑓𝑜𝑙𝑑 𝑥𝑠 𝑚𝑒𝑚𝑝𝑡𝑦 ∷ 𝛼 𝑚𝑎𝑝𝑝𝑒𝑛𝑑 ∷ 𝛼 → 𝛼 → 𝛼 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛽 ⇒ (𝛼 → 𝛽) → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 _ = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥: 𝑥𝑠 = 𝑓 𝑥 ′𝑚𝑎𝑝𝑝𝑒𝑛𝑑′ 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥𝑠 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 generalises 𝑓𝑜𝑙𝑑 by taking function 𝑓 ∷ (𝛼 → 𝛽) as an additional argument, which is applied to each list element prior to combining the resulting values using the 𝑚𝑒𝑚𝑝𝑡𝑦 and 𝑚𝑎𝑝𝑝𝑒𝑛𝑑 functions of 𝑀𝑜𝑛𝑜𝑖𝑑 𝛽.
4. 𝑓𝑜𝑙𝑑 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛼 ⇒ 𝛼 → 𝛼 𝑓𝑜𝑙𝑑 = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑 𝑥: 𝑥𝑠 = 𝑥 ′𝑚𝑎𝑝𝑝𝑒𝑛𝑑′ 𝑓𝑜𝑙𝑑 𝑥𝑠 𝑚𝑒𝑚𝑝𝑡𝑦 ∷ 𝛼 𝑚𝑎𝑝𝑝𝑒𝑛𝑑 ∷ 𝛼 → 𝛼 → 𝛼 𝑓𝑜𝑙𝑑 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛼 ⇒ 𝛼 → 𝛼 𝑓𝑜𝑙𝑑 = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑 𝑥: 𝑥𝑠 = 𝑥 <> 𝑓𝑜𝑙𝑑 𝑥𝑠 𝑚𝑒𝑚𝑝𝑡𝑦 ∷ 𝛼 (<>) ∷ 𝛼 → 𝛼 → 𝛼 𝑚𝑎𝑝𝑝𝑒𝑛𝑑 is a synonym for (<>) 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛽 ⇒ (𝛼 → 𝛽) → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 _ = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥: 𝑥𝑠 = 𝑓 𝑥 <> 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥𝑠 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 ∷ 𝑀𝑜𝑛𝑜𝑖𝑑 𝛽 ⇒ (𝛼 → 𝛽) → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 _ = 𝑚𝑒𝑚𝑝𝑡𝑦 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥: 𝑥𝑠 = 𝑓 𝑥 ′𝑚𝑎𝑝𝑝𝑒𝑛𝑑′ 𝑓𝑜𝑙𝑑𝑀𝑎𝑝 𝑓 𝑥𝑠
5. mempty mappend <> fold foldMap empty combine |+| combineAll foldMap Cats
7. > mempty::String "" > "foo" <> mempty "foo" > mempty <> "bar" "bar" > "foo" <> "bar" "foobar" > mempty <> mempty::String "" > fold ([]::[String]) "" > fold ["foo", "bar", "baz"] "foobarbaz” > foldMap (\s -> fmap toUpper s) ["foo", "bar", "baz"] "FOOBARBAZ" > val empty = Monoid[String].empty val empty: String = "" > "foo" |+| empty val res1: String = foo > empty |+| "bar" val res2: String = bar > "foo" |+| "bar" val res3: String = foobar > empty |+| empty val res4: String = "" > List.empty[String].combineAll val res5: String = "" > List("foo", "bar", "baz").combineAll val res6: String = foobarbaz > List("foo", "bar", "baz").foldMap(_.toUpperCase) val res7: String = FOOBARBAZ > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
9. > getSum (mempty::Sum Int) 0 > getSum (Sum 2 <> mempty) 2 > getSum (mempty <> Sum 3) 3 > getSum (Sum 2 <> Sum 3) 5 > getSum (mempty <> mempty::Sum Int) 0 > getSum (fold ([]::[Sum Int])) 0 > getSum (fold (fmap Sum [1, 2, 3, 4])) 10 > getSum (foldMap Sum [1, 2, 3, 4]) 10 newtype Sum a = Sum {getSum :: a} > val empty = Monoid[Int].empty val empty: Int = 0 > 2 |+| empty val res1: Int = 2 > empty |+| 3 val res2: Int = 3 > 2 |+| 3 val res3: Int = 5 > empty |+| empty val res4: Int = 0 > List.empty[Int].combineAll val res5: Int = 0 > List(1, 2, 3, 4).combineAll val res6: Int = 10 > List(1, 2, 3, 4).foldMap(_ + 10) val res7: Int = 50 > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
11. > getProduct (mempty::Product Int) 1 > getProduct (Product 2 <> mempty) 2 > getProduct (mempty <> Product 3) 3 > getProduct (Product 2 <> Product 3) 6 > getProduct (mempty <> mempty::Product Int) 1 > getProduct (fold ([]::[Product Int])) 1 > getProduct (fold (fmap Product [1, 2, 3, 4])) 24 > getProduct (foldMap Product [1, 2, 3, 4]) 24 newtype Product a = Product {getProduct :: a} > given Monoid[Int] = Monoid.instance(emptyValue = 1, cmb = _ * _) > val empty = Monoid[Int].empty val empty: Int = 1 > 2 |+| empty val res1: Int = 2 > empty |+| 3 val res2: Int = 3 > 2 |+| 3 val res3: Int = 6 > empty |+| empty val res4: Int = 1 > List.empty[Int].combineAll val res5: Int = 1 > List(1, 2, 3, 4).combineAll val res6: Int = 24 > List(1, 2, 3, 4).foldMap(_ + 10) val res7: Int = 24024 > import cats.implicits.catsSyntaxSemigroup > import cats.syntax.foldable.* > import cats.Monoid
13. > getAll (mempty::All) True > getAll (All True <> mempty) True > getAll (All False <> mempty) False > getAll (mempty <> All True) True > getAll (mempty <> All False) False > getAll (mempty <> mempty::All) True > getAll (All False <> All False) False newtype All = All {getAll :: Bool} > given Monoid[Boolean] = Monoid.instance(emptyValue = true, cmb = _ && _) > val empty = Monoid[Boolean].empty val empty: Boolean = true > true |+| empty val res1: Boolean = true > false |+| empty val res2: Boolean = false > empty |+| true val res3: Boolean = true > empty |+| false val res4: Boolean = false > empty |+| empty val res5: Boolean = true > false |+| false val res6: Boolean = false > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
14. > getAll (fold ([]::[All])) True > getAll (fold (fmap All [True, True, True])) True > getAll (fold (fmap All [True, False, True])) False > getAll (foldMap All [True, True, True]) True > getAll (foldMap All [True, True, False]) False > List.empty[Boolean].combineAll val res7: Boolean = true > List(true, true, true).combineAll val res8: Boolean = true > List(true, false, true).combineAll val res9: Boolean = false > List(false, false, false).foldMap(!_) val res10: Boolean = true > List(false, true, false).foldMap(!_) val res11: Boolean = false
16. > getAny (mempty::Any) False > getAny (Any True <> mempty) True > getAny (Any False <> mempty) False > getAny (mempty <> Any True) True > getAny (mempty <> Any False) False > getAny (mempty <> mempty:: Any) False > getAny (Any True <> Any True) True newtype Any = Any {getAny :: Bool} > given Monoid[Boolean] = Monoid.instance(emptyValue = false, cmb = _ || _) > val empty = Monoid[Boolean].empty val empty: Boolean = false > true |+| empty val res1: Boolean = true > false |+| empty val res2: Boolean = false > empty |+| true val res3: Boolean = true > empty |+| false val res4: Boolean = false > empty |+| empty val res5: Boolean = false > true |+| true val res6: Boolean = true > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
17. > getAny (fold ([]::[Any])) False > getAny (fold (fmap Any [False, True, False])) True > getAny (fold (fmap Any [False, False, False])) False > getAny (foldMap Any [False, True, False]) True > getAny (foldMap Any [False, False, False]) False > List.empty[Boolean].combineAll val res7: Boolean = false > List(false, true, false).combineAll val res8: Boolean = true > List(false, false, false).combineAll val res9: Boolean = false > List(true, false, true).foldMap(!_) val res10: Boolean = true > List(true, true, true).foldMap(!_) val res11: Boolean = false
19. > mempty::[Int] [] > [1,2] <> mempty [1,2] > mempty <> [3,4] [3,4] > [1,2] <> [3,4] [1,2,3,4] > mempty <> mempty::[Int] [] > fold (mempty::[[Int]]) [] > fold [[1,2],[3,4,5],[6]] [1,2,3,4,5,6] > foldMap tail [[1,2],[3,4,5],[6]] [2,4,5] > val empty = Monoid[List[Int]].empty val empty: List[Int] = List() > List(1,2) |+| empty val res1: List[Int] = List(1, 2) > empty |+| List(3,4) val res2: List[Int] = List(3, 4) > List(1,2) |+| List(3,4) val res3: List[Int] = List(1, 2, 3, 4) > empty |+| empty val res4: List[Int] = List() > List.empty[List[Int]].combineAll val res5: List[Int] = List() > List(List(1,2),List(3,4,5),List(6)).combineAll val res6: List[Int] = List (1, 2, 3, 4, 5, 6) > List(List(1,2),List(3,4,5),List(6)).foldMap(_.tail) val res7: List[Int] = List(2, 4, 5) > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
20. instance Semigroup a => Semigroup (Maybe a) where Nothing <> b = b a <> Nothing = a Just a <> Just b = Just (a <> b) instance Semigroup a => Monoid (Maybe a) where mempty = Nothing class OptionMonoid[A] (implicit A: Semigroup[A]) extends Monoid[Option[A]] { def empty: Option[A] = None def combine(x: Option[A], y: Option[A]): Option[A] = x match { case None => y case Some(a) => y match { case None => x case Some(b) => Some(A.combine(a, b)) } } }
21. > mempty :: Maybe (Sum Int) Nothing > Just (Sum 2) <> Just (Sum 3) Just (Sum {getSum = 5}) > Just (Sum 2) <> mempty Just (Sum {getSum = 2}) > mempty <> Just (Sum 3) Just (Sum {getSum = 3}) >(mempty :: Maybe (Sum Int)) <> mempty Nothing > fold ([]::[Maybe (Sum Int)]) Nothing > fold [Just (Sum 1), Nothing, Just (Sum 2), Nothing, Just (Sum 3), Just (Sum 4)] Just (Sum {getSum = 10}) > fold (fmap (\x -> fmap Sum x) [Just 1, Nothing, Just 2, Nothing, Just 3, Just 4]) Just (Sum {getSum = 10}) > foldMap (\x -> fmap Sum x) [Just 1, Nothing, Just 2, Nothing, Just 3, Just 4] Just (Sum {getSum = 10})
22. > val empty = Monoid[Option[Int]].empty val empty: Option[Int] = None > 2.some |+| 3.some val res1: Option[Int] = Some(5) > 2.some |+| empty val res2: Option[Int] = Some(2) > empty |+| 3.some val res3: Option[Int] = Some(3) > empty |+| empty val res4: Option[Int] = None > List.empty[Option[Int]].combineAll val res5: Option[Int] = None > List(1.some, none, 2.some, none, 3.some, 4.some).combineAll val res6: Option[Int] = Some(10) > List(1.some, none, 2.some, none, 3.some, 4.some).foldMap(_.map(_ * 10)) val res7: Option[Int] = Some(100) > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
24. > mempty :: Maybe [Int] Nothing > Just [1,2] <> Just [3,4] Just [1,2,3,4] > Just [1,2] <> mempty Just [1,2] > mempty <> Just [3,4] Just [3,4] >(mempty :: Maybe [Int]) <> mempty Nothing > fold ([]::[Maybe [Int]]) Nothing > fold [Just [1,2], Nothing, Just [3,4,5], Nothing, Just [6]] Just [1,2,3,4,5,6] > foldMap (\x -> fmap tail x) [Just [1,2], Nothing, Just [3,4,5], Nothing, Just [6]] Just [2,4,5]
25. > val empty = Monoid[Option[List[Int]]].empty val empty: Option[List[Int]] = None > List(1,2).some |+| List(3,4).some val res1: Option[List[Int]] = Some(List(1,2,3,4)) > List(1,2).some |+| empty val res2: Option[List[Int]] = Some(List(1,2)) > empty |+| List(3,4).some val res3: Option[List[Int]] = Some(List(3,4)) > empty |+| empty val res4: Option[List[Int]] = None > List.empty[Option[List[Int]]].combineAll val res5: Option[List[Int]] = None > List(List(1,2).some , none, List(3,4,5).some, none, List(6).some).combineAll val res6: Option[List[Int]] = Some(List(1,2,3,4,5,6)) > List(List(1,2).some , none, List(3,4,5).some, none, List(6).some).foldMap(_.map(_.tail)) val res7: Option[List[Int]] = Some(List(2,4,5)) > import cats.implicits.* > import cats.syntax.* > import cats.Monoid
27. … import qualified Data.HashMap.Strict as M import Data.Hashable (Hashable) … -- | A 'HashMap' with monoidal accumulation newtype MonoidalHashMap k a = MonoidalHashMap { getMonoidalHashMap :: M.HashMap k a } deriving ( Show, Read, Functor, Eq, …) … instance (Eq k, Hashable k, Semigroup a) => Semigroup (MonoidalHashMap k a) where MonoidalHashMap a <> MonoidalHashMap b = MonoidalHashMap $ M.unionWith (<>) a b … instance (Eq k, Hashable k, Semigroup a) => Monoid (MonoidalHashMap k a) where mempty = MonoidalHashMap mempty … mappend (MonoidalHashMap a) (MonoidalHashMap b) = MonoidalHashMap $ M.unionWith (<>) a b … Data.HashMap.Monoidal newtype MonoidalHashMap k a https://hackage.haskell.org/package/monoidal-containers-0.6.5.0/docs/Data-HashMap-Monoidal.html This module provides a HashMap variant which uses the value’s Monoid instance to accumulate conflicting entries when merging Maps.
28. > {-# LANGUAGE DeriveGeneric #-} > import Data.HashMap.Monoidal (MonoidalHashMap) > import qualified Data.HashMap.Monoidal as MonoidalHashMap > data Currency = EUR | USD | GBP deriving (Eq, Ord, Enum, Show, Generic) > type Money = Int > instance Hashable Currency > type Account = MonoidalHashMap Currency Money > account1 = MonoidalHashMap.fromList [(USD, 10), (GBP, 5), (EUR, 1)] > account2 = MonoidalHashMap.fromList [(GBP, 2)] > account3 = MonoidalHashMap.fromList [(USD, 3), (EUR, 5)] > mempty :: MonoidalHashMap Currency (Sum Money) MonoidalHashMap {getMonoidalHashMap = fromList []} > fmap getSum ((fmap Sum account1) <> mempty) MonoidalHashMap {getMonoidalHashMap = fromList [(EUR,1),(GBP,5),(USD,10)]} > fmap getSum ((fmap Sum account1) <> (fmap Sum account2)) MonoidalHashMap {getMonoidalHashMap = fromList [(EUR,1),(GBP,7),(USD,10)]} > (fmap getSum (fold (fmap (fmap Sum) [account1, account2, account3]))) MonoidalHashMap {getMonoidalHashMap = fromList [(EUR,6),(GBP,7),(USD,13)]} > (fmap getSum (foldMap (fmap Sum) [account1, account2, account3])) MonoidalHashMap {getMonoidalHashMap = fromList [(EUR,6),(GBP,7),(USD,13)]}
30. class MapMonoid[K, V](implicit V: Semigroup[V]) extends Monoid[Map[K, V]] { def empty: Map[K, V] = Map.empty def combine(xs: Map[K, V], ys: Map[K, V]): Map[K, V] = if (xs.size <= ys.size) { xs.foldLeft(ys) { case (my, (k, x)) => my.updated(k, Semigroup.maybeCombine(x, my.get(k))) } } else { ys.foldLeft(xs) { case (mx, (k, y)) => mx.updated(k, Semigroup.maybeCombine(mx.get(k), y)) } } override def combineAll(xss: IterableOnce[Map[K, V]]): Map[K, V] = … … abstract class SemigroupFunctions[S[T] <: Semigroup[T]] { … def maybeCombine[@sp(Int, Long, Float, Double) A](ox: Option[A], y: A)(implicit ev: S[A]): A = ox match { case Some(x) => ev.combine(x, y) case None => y } def maybeCombine[@sp(Int, Long, Float, Double) A](x: A, oy: Option[A])(implicit ev: S[A]): A = oy match { case Some(y) => ev.combine(x, y) case None => x } … Cats https://typelevel.org/cats/api/cats/kernel/instances/MapMonoid.html
31. > enum Currency { case EUR, USD, GBP } > type Money = Int > type Account = Map[Currency, Money] > object Account { def apply(amounts: (Currency, Money)*): Account = amounts.toMap } > val empty = Monoid[Account].empty val empty: Account = Map() > val account1 = Account(USD -> 10, GBP -> 5, EUR -> 1) val account1: Account = Map(USD -> 10, GBP -> 5, EUR -> 1) > val account2 = Account(GBP -> 2) val account2: Account = Map(GBP -> 2) > val account3 = Account(USD -> 3, EUR -> 5) val account3: Account = Map(USD -> 3, EUR -> 5) > account1 |+| empty val res1: Account = Map(USD -> 10, GBP -> 5, EUR -> 1) > account1 |+| account2 val res2: Account = Map(USD -> 10, GBP -> 7, EUR -> 1) > List(account1, account2, account3).combineAll val res3: Map[Currency, Money] = Map(GBP -> 7, USD -> 13, EUR -> 6) > List(account1, account2, account3).foldMap(_.transform{ case (k,v) => v * 10 }) val res4: Map[Currency, Int] = Map(GBP -> 70, USD -> 130, EUR -> 60)
33. > val empty = Monoid[Endo[Int]].empty val empty: cats.Endo[Int] = … > def increment(n: Int): Int = n + 1 > def twice(n: Int): Int = 2 * n > def square(n: Int): Int = n * n > empty(33) val res0: Int = 0 > (increment |+| empty)(5) val res1: Int = 6 > (empty |+| twice)(5) val res2: Int = 10 > (increment |+| twice)(5) val res3: Int = 16 > (empty |+| empty)(5) val res4: Int = 0 > List.empty[Endo[Int]].combineAll.apply(5) val res5: Int = 0 > List(increment,twice,square).combineAll.apply(5) val res6: Int = 41 > increment n = n + 1 > twice n = 2 * n > square n = n * n > getSum ((mempty :: Int -> Sum Int) 33) 0 > getSum ((increment <> mempty) 5) 6 > getSum ((mempty <> twice) 5) 10 > getSum ((increment <> twice) 5) 16 > getSum ((mempty <> (mempty::Int -> Sum Int)) 5) 0 > getSum (fold ([]::[Int -> Sum Int]) 5) 0 > getSum (fold [increment, twice, square ] 5) 41 newtype Sum a = Sum {getSum :: a} > import cats.implicits.* > import cats.syntax.* > import cats.Monoid instance Num a => Monoid (Sum a) instance Monoid b => Monoid (a -> b) type Endo[A] = A => A > import cats.Endo
35. > given endoMonoid: Monoid[Int => Int] = MonoidK[Endo].algebra[Int] > def increment(n: Int): Int = n + 1 > def twice(n: Int): Int = 2 * n > def square(n: Int): Int = n * n > empty(33) val res0: Int = 33 > (increment |+| twice)(5) val res1: Int = 11 > (endoMonoid.empty |+| twice)(5) val res2: Int = 10 > (increment |+| endoMonoid.empty)(5) val res3: Int = 6 > (endoMonoid.empty |+| endoMonoid.empty)(5) val res4: Int = 5 > List.empty[Int => Int].combineAll.apply(5) val res5: Int = 5 > List(increment,twice,square).combineAll.apply(5) val res6: Int = 51 > increment n = n + 1 > twice n = 2 * n > square n = n * n > appEndo (mempty::Endo Int) 33 33 > appEndo ((Endo increment) <> (Endo twice)) 5 11 > appEndo (mempty <> (Endo twice)) 5 10 > appEndo (Endo increment <> mempty) 5 6 > appEndo (mempty <> (mempty::Endo Int)) 5 5 > appEndo (fold (fmap Endo [increment,twice,square]))5 51 > appEndo (foldMap Endo [increment,twice,square]) 5 51 import cats.implicits.catsSyntaxSemigroup import cats.syntax.foldable.* import cats.{Monoid,MonoidK} type Endo :: * -> * newtype Endo a = Endo {appEndo :: a -> a} … instance Monoid (Endo a) instance Semigroup (Endo a) type Endo[A] = A=>A import cats.Endo
37. import Graphics.Gloss main :: IO () main = display window white rgbcmyRectangle squareImage = rectangleSolid (fromIntegral 100) (fromIntegral 100) [redSquare, greenSquare, blueSquare, cyanSquare, magentaSquare, yellowSquare] = fmap (\(colour, index) -> translate (-100 * (2-index) - 50) 0 (color colour squareImage)) (zip [red, green, blue, cyan, magenta, yellow] [0..]) rgbRectangle = redSquare <> greenSquare <> blueSquare rgbcmyRectangle = fold [rgbRectangle, cyanSquare, magentaSquare, yellowSquare] window = InWindow "RGBCMY Squares" (600, 100) (0,0)
38. import cats.Monoid import cats.effect.unsafe.implicits.global import cats.implicits.* import doodle.core.* import doodle.image.* import doodle.image.syntax.* import doodle.image.syntax.all.* import doodle.image.syntax.core.* import doodle.java2d.* @main def main(): Unit = val squareImage = Image.square(100) val List(redSquare, greenSquare, blueSquare, cyanSquare, magentaSquare, yellowSquare) = List(Color.red, Color.green, Color.blue, Color.cyan, Color.magenta, Color.yellow) .zipWithIndex.map((color, index) => squareImage.at(index * 100, 0).fillColor(color)) given Monoid[Image] = Monoid.instance[Image](Image.empty, _ on _) val rgbRectangle: Image = redSquare |+| greenSquare |+| blueSquare val rgbcmyRectangle: Image = List(rgbRectangle, cyanSquare, magentaSquare, yellowSquare).combineAll rgbcmyRectangle.drawWithFrame(Frame.default.withTitle("RGBCMY Squares"))
39. https://fpilluminated.com/ If you liked this deck, you may also be interested in one or more of the following @philip_schwarz