Learn You a Haskell for Great Good! - Miran Lipovaca [156]
data Coin = Heads | Tails deriving (Show, Eq)
coin :: Prob Coin
coin = Prob [(Heads,1%2),(Tails,1%2)]
loadedCoin :: Prob Coin
loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]
And finally, the coin-throwing action:
import Data.List (all)
flipThree :: Prob Bool
flipThree = do
a <- coin
b <- coin
c <- loadedCoin
return (all (==Tails) [a,b,c])
Giving it a go, we see that the odds of all three landing tails are not that good, despite cheating with our loaded coin:
ghci> getProb flipThree
[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),
(False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]
All three of them will land tails 9 times out of 40, which is less than 25 percent. We see that our monad doesn’t know how to join all of the False outcomes where all coins don’t land tails into one outcome. That’s not a big problem, since writing a function to put all the same outcomes into one outcome is pretty easy (and left as an exercise to you, the reader).
In this section, we went from having a question (what if lists also carried information about probability?) to making a type, recognizing a monad, and finally making an instance and doing something with it. I think that’s quite fetching! By now, you should have a pretty good grasp of monads and what they’re about.
Chapter 15. Zippers
While Haskell’s purity comes with a whole bunch of benefits, it makes us tackle some problems differently than we would in impure languages.
Because of referential transparency, one value is as good as another in Haskell if it represents the same thing. So, if we have a tree full of fives (high fives, maybe?), and we want to change one of them into a six, we must have some way of knowing exactly which five in our tree we want to change. We need to know where it is in our tree. In impure languages, we could just note where the five is located in memory and change that. But in Haskell, one five is as good as another, so we can’t discriminate based on their location in memory.
We also can’t really change anything. When we say that we “change a tree,” we actually mean that we take a tree and return a new one that’s similar to the original, but slightly different.
One thing we can do is remember a path from the root of the tree to the element that we want to change. We could say, “Take this tree, go left, go right and then left again, and change the element that’s there.” While this works, it can be inefficient. If we want to later change an element that’s near the element that we previously changed, we need to walk all the way from the root of the tree to our element again!
In this chapter, you’ll see how to take some data structure and equip it with something called a zipper to focus on a part of the data structure in a way that makes changing its elements easy and walking around it efficient. Nice!
Taking a Walk
As you learned in biology class, there are many different kinds of trees, so let’s pick a seed that we will use to plant ours. Here it is:
data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
Our tree is either empty or it’s a node that has an element and two subtrees. Here’s a fine example of such a tree, which I give to you, the reader, for free!
freeTree :: Tree Char freeTree =
Node 'P'
(Node 'O'
(Node 'L'
(Node 'N' Empty Empty)
(Node 'T' Empty Empty)
)
(Node 'Y'
(Node 'S' Empty Empty)
(Node 'A' Empty Empty)
)
)
(Node 'L'
(Node 'W'
(Node 'C' Empty Empty)
(Node 'R' Empty Empty)
)
(Node 'A'
(Node 'A' Empty Empty)
(Node 'C' Empty Empty)
)
)
And here's this tree represented graphically:
Notice that W in the tree there? Say we want to change it into a P. How would we go about doing that? Well, one way would be to pattern match on our tree until we find the element, by first