Haskell – 109 – functors, funtors applicativi e monoids – 8

Continuo da qui, copio qui.

Monoidi
Type classes in Haskell are used to present an interface for types that have some behavior in common. We started out with simple type classes like Eq, which is for types whose values can be equated, and Ord, which is for things that can be put in an order and then moved on to more interesting ones, like Functor and Applicative.

When we make a type, we think about which behaviors it supports, i.e. what it can act like and then based on that we decide which type classes to make it an instance of. If it makes sense for values of our type to be equated, we make it an instance of the Eq type class. If we see that our type is some kind of functor, we make it an instance of Functor, and so on.

Now consider the following: * is a function that takes two numbers and multiplies them. If we multiply some number with a 1, the result is always equal to that number. It doesn’t matter if we do 1 * x or x * 1, the result is always x. Similarly, ++ is also a function which takes two things and returns a third. Only instead of multiplying numbers, it takes two lists and concatenates them. And much like *, it also has a certain value which doesn’t change the other one when used with ++. That value is the empty list: [].

Prelude> 4 * 1
4
Prelude> 1 * 9
9
Prelude> [1,2,3] ++ []
[1,2,3]
Prelude> [] ++ [0.5, 2.5]
[0.5,2.5]

It seems that both * together with 1 and ++ along with [] share some common properties:

  • The function takes two parameters.
  • The parameters and the returned value have the same type.
  • There exists such a value that doesn’t change other values when used with the binary function.

There’s another thing that these two operations have in common that may not be as obvious as our previous observations: when we have three or more values and we want to use the binary function to reduce them to a single result, the order in which we apply the binary function to the values doesn’t matter. It doesn’t matter if we do (3 * 4) * 5 or 3 * (4 * 5). Either way, the result is 60. The same goes for ++:

Prelude> (3 * 2) * (8 * 5)
240
Prelude> 3 * (2 * (8 * 5))
240
Prelude> "la" ++ ("di" ++ "da")
"ladida"
Prelude> ("la" ++ "di") ++ "da"
"ladida"

We call this property associativity. * is associative, and so is ++, but -, for example, is not. The expressions (5 - 3) - 4 and 5 - (3 - 4) result in different numbers.

By noticing and writing down these properties, we have chanced upon monoids! A monoid is when you have an associative binary function and a value which acts as an identity with respect to that function. When something acts as an identity with respect to a function, it means that when called with that function and some other value, the result is always equal to that other value. 1 is the identity with respect to * and [] is the identity with respect to ++. There are a lot of other monoids to be found in the world of Haskell, which is why the Monoid type class exists. It’s for types which can act like monoids. Let’s see how the type class is defined:

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

The Monoid type class is defined in import Data.Monoid. Let’s take some time and get properly acquainted with it.

First of all, we see that only concrete types can be made instances of Monoid, because the m in the type class definition doesn’t take any type parameters. This is different from Functor and Applicative, which require their instances to be type constructors which take one parameter.

The first function is mempty. It’s not really a function, since it doesn’t take parameters, so it’s a polymorphic constant, kind of like minBound from Bounded. mempty represents the identity value for a particular monoid.

Next up, we have mappend, which, as you’ve probably guessed, is the binary function. It takes two values of the same type and returns a value of that type as well. It’s worth noting that the decision to name mappend as it’s named was kind of unfortunate, because it implies that we’re appending two things in some way. While ++ does take two lists and append one to the other, * doesn’t really do any appending, it just multiplies two numbers together. When we meet other instances of Monoid, we’ll see that most of them don’t append values either, so avoid thinking in terms of appending and just think in terms of mappend being a binary function that takes two monoid values and returns a third.

The last function in this type class definition is mconcat. It takes a list of monoid values and reduces them to a single value by doing mappend between the list’s elements. It has a default implementation, which just takes mempty as a starting value and folds the list from the right with mappend. Because the default implementation is fine for most instances, we won’t concern ourselves with mconcat too much from now on. When making a type an instance of Monoid, it suffices to just implement mempty and mappend. The reason mconcat is there at all is because for some instances, there might be a more efficient way to implement mconcat, but for most instances the default implementation is just fine.

Before moving on to specific instances of Monoid, let’s take a brief look at the monoid laws. We mentioned that there has to be a value that acts as the identity with respect to the binary function and that the binary function has to be associative. It’s possible to make instances of Monoid that don’t follow these rules, but such instances are of no use to anyone because when using the Monoid type class, we rely on its instances acting like monoids. Otherwise, what’s the point? That’s why when making instances, we have to make sure they follow these laws:

  • mempty `mappend` x = x
  • x `mappend` mempty = x
  • (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

The first two state that mempty has to act as the identity with respect to mappend and the third says that mappend has to be associative i.e. that it the order in which we use mappend to reduce several monoid values into one doesn’t matter. Haskell doesn’t enforce these laws, so we as the programmer have to be careful that our instances do indeed obey them.

Le liste sono monoidi
Yes, lists are monoids! Like we’ve seen, the ++ function and the empty list [] form a monoid. The instance is very simple:

instance Monoid [a] where
  mempty = []
  mappend = (++)

Lists are an instance of the Monoid type class regardless of the type of the elements they hold. Notice that we wrote instance Monoid [a] and not instance Monoid [], because Monoid requires a concrete type for an instance.

Giving this a test run, we encounter no surprises:

Prelude> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
Prelude> ("one" `mappend` "two") `mappend` "tree"
"onetwotree"
Prelude> "one" `mappend` ("two" `mappend` "tree")
"onetwotree"
Prelude> "one" `mappend` "two" `mappend` "tree"
"onetwotree"
Prelude> "pang" `mappend` mempty
"pang"
Prelude> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
Prelude> mempty :: [a]
[]

Notice that in the last line, we had to write an explicit type annotation, because if we just did mempty, GHCi wouldn’t know which instance to use, so we had to say we want the list instance. We were able to use the general type of [a] (as opposed to specifying [Int] or [String]) because the empty list can act as if it contains any type.

Because mconcat has a default implementation, we get it for free when we make something an instance of Monoid. In the case of the list, mconcat turns out to be just concat. It takes a list of lists and flattens it, because that’s the equivalent of doing ++ between all the adjecent lists in a list.

The monoid laws do indeed hold for the list instance. When we have several lists and we mappend (or ++) them together, it doesn’t matter which ones we do first, because they’re just joined at the ends anyway. Also, the empty list acts as the identity so all is well. Notice that monoids don’t require that a `mappend` b be equal to b `mappend` a. In the case of the list, they clearly aren’t:

Prelude> "one" `mappend` "two"
"onetwo"
Prelude> "two" `mappend` "one"
"twoone"

And that’s okay. The fact that for multiplication 3 * 5 and 5 * 3 are the same is just a property of multiplication, but it doesn’t hold for all (and indeed, most) monoids.

Pausa; ci sono ancora tante cose sui monoidi, prossimamente…

🤩

Annunci
Post a comment or leave a trackback: Trackback URL.

Trackbacks

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: