032 - Composition in FP


#1

Abstract

Composition is a fundamental aspect of Functional Programming. We will explore how we compose things using monoids, applicatives, and monads; we will look at the differences between these abstractions, but also try to find the common patterns.

Slides


#2

Ionuț a întrebat aseară de ce avem nevoie de o instanță de Alternative f când, în schimb, am putea defini o instanță de Monoid (f a). (Cred că asta a fost întrebarea, dacă nu, corectează-mă @igstan).

Mi-am dat seama că pentru Maybe a putem într-adevăr defini o instanță de Monoid pentru care mappend și mempty se comportă la fel ca <|> și empty (din Alternative):

import Prelude hiding (Maybe, Nothing, Just)               

data Maybe a = Nothing       
             | Just a        
    deriving (Show, Eq)      

instance Monoid (Maybe a) where                            
    mempty = Nothing         
    (Just a) `mappend` _ = Just a                          
    _        `mappend` b = b 

(Definiția aceasta de Monoid corespunde tipului First din Data.Monoid, care este un wrapper peste Maybe.)

De asemenea, pentru liste cele două instanțe, de Alternative și Monoid, implementează aceleași operații, și anume, mappend = (<|>) = (++) și mempty = empty = []:

Prelude Control.Applicative> [1,2,3] `mappend` [4,5,6] `mappend` mempty                                                 
[1,2,3,4,5,6]                
Prelude Control.Applicative> [1,2,3] <|> [4,5,6] <|> empty                                                
[1,2,3,4,5,6]                

Cred că principala diferență dintre Monoid și Alternative e că Alternative are mai multă structură, e Functor și Applicative, și are legi care ne spun cum interacționează diferitele operații (<|>, empty, <*>, pure) – legi care totuși nu par foarte bine stabilite conform Typeclassopedia:

This, then, is the situation: we have a lot of instances of Alternative, with each instance satisfying some subset of these laws. Moreover, it’s not always the same subset, so there is no obvious “default” set of laws to choose. For now at least, we just have to live with the situation.

@cvlad În prezentare tu ai menționat două legi pentru Applicativeleft zero și left distribution; eram curios cum le-ai ales.


#3

Este corect ca implementare acel Monoid, desi in Prelude el arata asa:

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

Cat despre liste, List a este monoidul liber (Free Monoid) pentru a (pentru ca nu trebuie sa stim cum sa combinam doi a, este suficient sa ii punem inr-o lista pentru “mai tarziu”). Poate de asta se aliniaza foarte bine implementarile in cazul asta?

Legile le-am luat din clasa de PureScript: https://pursuit.purescript.org/packages/purescript-control/4.1.0/docs/Control.Alternative#t:Alternative


#4

Ai dreptate @cvlad, dar din câte înțeleg implementarea din Prelude este, până la un punct, o decizie subiectivă, care are criticii săi – de la Conor McBride citire:

The current monoid instance for Maybe is, in my view, unfortunate.

Types are about semantic purpose, not just data representation. Many purposes can be represented in the same way. We should identify the purpose of a type (or type constructor), then define instances consistent with that purpose. And better, we acquire by instance inference compound instances consistent with that purpose! (A similar view is often articulated well by Conal Elliott. But perhaps it’s just a “Con” thing.)

The purpose of Maybe, it seems to me, is to model failure and prioritized choice, after the manner of exceptions. It’s clear what the failure-and-prioritized-choice monoid is.

It so happens that the same data representation can be used to make a semigroup into a monoid by attaching an identity element. That’s a different semantic purpose, which deserves a different type.

This really bites. I really like being able to write things like

newtype P a x = P ([a] -> Maybe (x, [a])) deriving Monoid

and then make MonadPlus/Alternative instances just by copying the monoid that results, but it doesn’t work!

[…]

Maybe I’m an extremist, but I’d prefer it if every Alternative instance was constructed by duplicating a polymorphic Monoid instance.


#5

Nu mai țin minte exact care a fost întrebarea mea (am o memorie foarte proastă în ultima vreme), dar ce voiam să zic e că eu nu văd o diferență fundamentală între Monoid și Alternative. M-am uitat acum ceva vreme la câteva răspunsuri pe StackOverflow și nu m-au lămurit. Iar exemplul cu Data.Monoid.First e revelator, poți avea un Monoid pentru Maybe care face fix ce face instanța de Alternative. (În Scala, instanța de Monoid pe care-o pomeneam, e echivalenta celei din Prelude, nu din First.)

Și, da, ok, înțeleg că Monoid este definit pentru kind *, iar Alternative pentru kind * -> *, dar nu văd implicațiile, iar prin implicații mă refer la exemple clare care să reliefeze când un tip T :: * -> * care are o instanță de Alternative, nu poate avea și o instanță de Monoid care să facă fix același lucru.


#6

Am găsit pe Reddit pe cineva care pare să demonstreze că nu există o diferență fundamentală între Monoid și Alternative: https://www.reddit.com/r/haskell/comments/8oahjt/is_there_any_difference_between_monoid/e01yl9x/

Am încercat adineauri o implementare kind-polimorfică de Monoid folosind -XPolyKinds, dar se pare că mi-au cam ruginit capabilitățile de a scrie Haskell.