• Choose a category
• All
• Classic-Fiction

By Root 470 0

to look at an example of how a type gets made, identified as a monad, and then given the appropriate Monad instance. We don’t usually set out to make a monad with the sole purpose of making a monad. Rather, we make a type whose purpose is to model an aspect of some problem, and then later on, if we see that the type represents a value with a context and can act like a monad, we give it a Monad instance.

As you’ve seen, lists are used to represent nondeterministic values. A list like [3,5,9] can be viewed as a single nondeterministic value that just can’t decide what it’s going to be. When we feed a list into a function with >>=, it just makes all the possible choices of taking an element from the list and applying the function to it and then presents those results in a list as well.

If we look at the list [3,5,9] as the numbers 3, 5, and 9 occurring at once, we might notice that there’s no information regarding the probability that each of those numbers occurs. What if we wanted to model a nondeterministic value like [3,5,9], but we wanted to express that 3 has a 50 percent chance of happening and 5 and 9 both have a 25 percent chance of happening? Let’s try to make this work!

Let’s say that every item in the list comes with another value: a probability of it happening. It might make sense to present that value like this:

[(3,0.5),(5,0.25),(9,0.25)]

In mathemathics, probabilities aren’t usually expressed in percentages, but rather in real numbers between a 0 and 1. A 0 means that there’s no chance in hell for something to happen, and a 1 means that it’s happening for sure. Floating-point numbers can get messy fast because they tend to lose precision, but Haskell offers a data type for rational numbers. It’s called Rational, and it lives in Data.Ratio. To make a Rational, we write it as if it were a fraction. The numerator and the denominator are separated by a %. Here are a few examples:

ghci> 1%4

1 % 4

ghci> 1%2 + 1%2

1 % 1

ghci> 1%3 + 5%4

19 % 12

The first line is just one-quarter. In the second line, we add two halves to get a whole. In the third line, we add one-third with five-quarters and get nineteen-twelfths. So, let’s throw out our floating points and use Rational for our probabilities:

ghci> [(3,1%2),(5,1%4),(9,1%4)]

[(3,1 % 2),(5,1 % 4),(9,1 % 4)]

Okay, so 3 has a one-out-of-two chance of happening, while 5 and 9 will happen one time out of four. Pretty neat.

We took lists and we added some extra context to them, so this represents values with contexts as well. Before we go any further, let’s wrap this into a newtype, because something tells me we’ll be making some instances.

import Data.Ratio

newtype Prob a = Prob { getProb :: [(a, Rational)] } deriving Show

Is this a functor? Well, the list is a functor, so this should probably be a functor, too, because we just added some stuff to the list. When we map a function over a list, we apply it to each element. Here, we’ll apply it to each element as well, but we’ll leave the probabilities as they are. Let’s make an instance:

instance Functor Prob where

fmap f (Prob xs) = Prob $ map (\(x, p) -> (f x, p)) xs

We unwrap it from the newtype with pattern matching, apply the function f to the values while keeping the probabilities as they are, and then wrap it back up. Let’s see if it works:

ghci> fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)])

Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}

Note that the probabilities should always add up to 1. If those are all the things that can happen, it doesn’t make sense for the sum of their probabilities to be anything other than 1. A coin that lands tails 75 percent of the time and heads 50 percent of the time seems like it could work only in some other strange universe.

Now the big question: Is this a monad? Given how the list is a monad, this looks like it should be a monad as well. First, let’s think about return. How does it work for lists? It takes a value and puts it in a singleton list. What about here? Well, since it’s supposed to be a default minimal context, it should also make a singleton