Theseus enters the labyrinth (and escapes)
Here we examine what we can learn about life (and code) by considering the ancient Greek myth of the Minotaur. We will write a simple maze game to see it in action. This is based on https://learnyouahaskell.com/ and the chapters about Monads, just that I'm applying it here to a different narrative.
1. On the never ending risk of failure
When Theseus enters the labyrinth to find and slay the Minotaur, it's unlikely that he's thinking: "What if I can't find the beast, maybe I'll hit a dead end?". Well, sorry, Theseus, but welcome to reality, this is life and things can and do go wrong.
Let's say we have 3 possible routes, of which only 1 leads to our friend the Minotaur. Here we account for what Theseus might well have ignored.
In this example maze, the Minotaur, AKA Mr. M, is hanging out at the end of route B, and not at the end of routes A or routes C! Trace the letters individually, starting with A, with the top left corner being the entry point
ABC AB AB AB A C B C B C M C
Thinking of the maze as a numeric grid, we could say that at the end of route C is 21, at the end of route A is 5, and at the end of route B is yours truly, el Minotaur or 19.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
So there we have it, if Theseus steps on 21, or 5, he's messed up. However, if he manages to reach 19, he's picked the right route. How he actually kills the beast, your guess is as good as mine.
So let's look at how we can represent this risk in code. Haskell includes this nifty thing called Maybe which can represent messing up in the form of Nothing or getting it right in the form of Just.
isMember :: Int -> [Int] -> Bool isMember n [] = False isMember n (x:xs) | n == x = True | otherwise = isMember n xs type Step = Int badSteps = [5, 21] winningStep = 19 takeStep :: Step -> Maybe Step takeStep s | isMember s badSteps = Nothing | s == winningStep = Just s | otherwise = Just s
Pretty simple. And to use it we can navigate like this. 1 Note that both takeStep 5 and takeStep 21 are conceived as dead ends returning Nothing. And, Theseus might as well be dead as he still doesn't know how to retrace his steps; Ariadne's ball of string is nowhere to be seen, yet.
takeStep 1 -- Just 1 takeStep 2 -- Just 2 takeStep 5 -- Nothing takeStep 21 -- Nothing ... takeStep 19 -- Found Minotaur!
2. Why knowing how you get to where you are matters
There is the rub. You see we found the Minotaur, but Theseus has no way of getting out of the Labrynth. He doesn't have a record of the steps he took, that piece of string that was so important for him when it came to getting out again.
Let's first see how we can track the steps that he takes. We add type stepsTaken = [Int], and we modify our takeStep function to update that list on each call.
isMember :: Int -> [Int] -> Bool isMember n [] = False isMember n (x:xs) | n == x = True | otherwise = isMember n xs type Step = Int type StepsTaken = [Int] badSteps = [5, 21] winningStep = 19 takeStep :: Step -> StepsTaken -> Maybe StepsTaken takeStep s xs | isMember s badSteps = Nothing | s == winningStep = Just (s : xs) | otherwise = Just (s : xs)
And now we can chain the steps together: takeStep 2 (takeStep 1 [ ]), and at each step we build up a current state in an array of steps.
But, there is an issue. For the second call we will get a Maybe value, or rather the code hasn't compiled. What can we do now?
You can see that in this example:
ghci> takeStep 1 []
Just [1]
ghci> takeStep 2 (takeStep 1 [])
<interactive>:2:13: error:
• Couldn't match type: Maybe StepsTaken
with: [Int]
What we want is a function that will accept a Maybe value. takeStep doesn't do that, but what the heck, we can raise it to those lofty heights with the bind operator, >>= which has the type signature.
t :: (m0 a0 -> (a0 -> m0 b0) -> m0 b0) -> [a]
From what I get in that, we have a Maybe something getting passed to a function that takes a non Maybe value and outputs a Maybe value.
And now we can chain together steps just as if we were walking the labyrinth ourselves!
ghci> takeStep 1 [] >>= takeStep 2 Just [2,1]
Here's a "dead end" example using the Maybe context and our bind operator. It is route A.
λ> takeStep 1 [] >>= takeStep 2 >>= takeStep 3 >>= takeStep 4 >>= takeStep 5 Nothing
And the route with the Minotaur at the end. Route B.
takeStep 1 [] >>= takeStep 2 >>= takeStep 3 >>= takeStep 4 >>= takeStep 9 >>= takeStep 14 >>= takeStep 19 Just [19,14,9,4,3,2,1]
2.1. Backwards and forwards, forwards and back
We have a complete representation of our route, but no easy way of reasoning about going backwards and forwards. The metaphor that we are after is that of a stack.
2.1.1. Why a stack?
A stack, we could also call it a pile; something common for any of us who wash clothes, do the dishes, and now enter's labyrinth's with the objective of killing hybrid beings and want to get out again.
At it's most basic a stack looks like this code here. We have a pop function that takes the first item in a list and returns it as it is, and then drops it from the stateful list; the push function joins the supplied integer onto the front of the stateful list.
import Control.Monad.State type Stack = [Int] pop :: State Stack Int pop = state $ \(x:xs) -> (x,xs) push :: Int -> State Stack () push a = state $ \xs -> ((),a:xs) stackManip :: State Stack Int stackManip = do push 0 push 10 push 10 a <- pop -- Doing a pop like this means that we can use the /a/ value to do furter calculations. pop -- whereas here we just throw the value away. -- pop
In this example:
- we start with our values 1,2,3.
- Next we push 0 onto that, giving us: 0,1,2,3.
- Now we push 10, and we have 10, 0,1,2,3.
- Again we push 10, and we have 10, 10,0,1,2,3.
- And now we remove a 10
- And another 10. This leaves our state as 0,1,2,3
- And the last pop was 10, which we add as the first expression in our pair.
runState stackManip [1,2,3] (10,[0, 1,2,3])
What we see then is an easy way to think about going backwards and forwards.
Now, how could Theseus enter the the Labrynth, kill the half man/ half bull, and come out unscathed, virtually?
Well we want to run route B, like before, where we had Just [19,14,9,4,3,2,1], and then we want to pop our way back to 1.
import Control.Monad.State type Stack = [Int] pop :: State Stack Int pop = state $ \(x:xs) -> (x,xs) push :: Int -> State Stack () push a = state $ \xs -> ((),a:xs) stackManip :: State Stack Int stackManip = do push 1 push 2 push 3 push 4 push 9 push 14 push 19 pop pop pop pop pop pop
The next step will be to make this visually appealing, and to add interaction. I will add a link here, once ready.