{"id":319,"date":"2007-02-20T20:52:43","date_gmt":"2007-02-20T20:52:43","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/20\/using-monads-for-control-maybe-its-worth-a-look\/"},"modified":"2007-02-20T20:52:43","modified_gmt":"2007-02-20T20:52:43","slug":"using-monads-for-control-maybe-its-worth-a-look","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/20\/using-monads-for-control-maybe-its-worth-a-look\/","title":{"rendered":"Using Monads for Control: Maybe it's worth a look?"},"content":{"rendered":"

So, after our last installment, describing the theory of monads, and the previous posts, which focused on representing things like state and I\/O, I thought it was worth taking a moment to look at a different kind of thing that can be done with monads. We so often think of them as being state wrappers; and yet, that’s only really a part of what we can get from them. Monads are ways of tying together almost anything<\/em> that involves sequences.<\/p>\n

<\/p>\n

In previous parts of this tutorial, we’ve seen the Maybe<\/code> type. It’s a useful type for all sorts of things where there might<\/em> be a value. For example, a dictionary
\nlookup function would often be written something like:<\/p>\n

\nlookup :: (Ord a) => Dictionary a b -> a -> Maybe b\n<\/pre>\n
 You might expect (Ord a) => Dictionary a b -> a -> b<\/code>, meaning a function from a dictionary and a value of type a to a value of type b. But that’s not a great type definition for a lookup, because then what would the function return when the key isn’t in the dictionary? Maybe<\/code> gives us a way of handling that: if the key is included, we’ll return Just b<\/code>; otherwise, we’ll return Nothing<\/code>.<\/p>\n
 The problem with Maybe<\/code> is that anytime you use it, you need to wrap
\nthings up in pattern matches to check if a Nothing<\/code> value was returned, and to extract a value if a Just<\/code> was returned. That gets particularly messy if you have a sequence<\/em> of things to be looked up. For example, imagine that we’re writing a program for the police. They’ve got a license plate number, and they’d like to get the phone number of the person who owns the car with that plate. But the data is in different places: there’s a list of license plate numbers associated with owners; and then there’s the telephone book which has listings of peoples names and phone numbers. So here are some trivial implementations of the basic types and lookup functions:<\/p>\n
\n>data LicensePlate = Plate String deriving (Eq,Show)\n>\n>getPlateOwner :: [(LicensePlate,String)] -> LicensePlate -> Maybe String\n>getPlateOwner ((p, n):plates) plate\n>                  | p == plate = Just n\n>                  | otherwise = getPlateOwner plates plate\n>getPlateOwner [] _ = Nothing\n>\n>data PhoneNumber = Phone String String String deriving (Eq,Show)\n>         -- area code, prefix, number\n>getPhoneNumberForName :: [(PhoneNumber,String)] -> String -> Maybe PhoneNumber\n>getPhoneNumberForName ((num,name):phonebook) person\n>                  | name==person = Just num\n>                  | otherwise = getPhoneNumberForName phonebook person\n>getPhoneNumberForName [] _ = Nothing\n<\/pre>\n
 Suppose we had some databases for that:<\/p>\n
\n>plateDB = [(Plate \"abc\", \"Mark\"),(Plate \"h1a j2b\", \"Joe Random\"), (Plate \"u2k 5u1\", \"Jane Random\")]\n>\n>phoneDB=[(Phone \"321\" \"123\" \"3456\", \"Joe Random\"), (Phone \"345\" \"657\" \"3485\", \"Mark\"), (Phone \"588\" \"745\" \"1902\", \"Foo Bar\")]\n<\/pre>\n
 Now, suppose we wanted to write a lookup function from plate to phone number. The naive way would be:<\/p>\n
\n>getPhoneForPlate :: [(LicensePlate,String)] ->  [(PhoneNumber,String)] -> LicensePlate -> Maybe PhoneNumber\n>getPhoneForPlate ldb pdb lic =\n>   let person = getPlateOwner ldb lic\n>   in case person of\n>         Just name -> getPhoneNumberForName pdb name\n>         Nothing -> Nothing\n<\/pre>\n
 Now, imagine if we wanted to add another layer – we’d need to add another<\/em> let\/case inside of the “Just name<\/code>” case. The more we use Maybe<\/code>, the messier it gets. But Maybe<\/code> is a monad! So we could use:<\/p>\n
\n>mGetPhoneForPlate ::  [(LicensePlate,String)] -> [(PhoneNumber,String)] -> LicensePlate -> Maybe PhoneNumber\n>mGetPhoneForPlate ldb pdb lic =\n>    do\n>       name        phone        return phone\n<\/pre>\n
  What happened here is that “Maybe<\/code>” as a monad gives us a great way of chaining. Anywhere in the chain, if any step returns “Nothing”, then the entire series will stop there, and return “Nothing<\/code>“. Any step where it returns “Just x<\/code>“, we can just capture the value as if there were no “Just<\/code>“. Suddenly chains of Maybe<\/code> aren’t a problem anymore.<\/p>\n
 An important thing to notice about this is that the monad is being used as a control structure. We’ve got a sequence<\/em> of operations chained together in a monad. When we evaluate the monadic sequence, the implementation of the binding operator that combines monads actually does control flow management. Let’s take a quick look at the internals of Maybe<\/code> just to see how that’s done:<\/p>\n
\ninstance Monad Maybe where\nreturn         = Just\nfail           = Nothing\nNothing  >>= f = Nothing\n(Just x) >>= f = f x\n<\/pre>\n
 Pretty simple, right? return<\/code> really just wraps the value in a “Just<\/code>“. If there’s an error along the way, “fail<\/code>” will make the monad evaluate to “Nothing<\/code>“. And for chaining, “Nothing<\/code>” chained with anything else results in “Nothing<\/code>“; (Just x)<\/code> chained with something unwraps x<\/code>, and passes it to the next step in the chain. The control flow is captured in the pattern match between “Nothing<\/code>” and “Just x<\/code>” in the instance declaration of the “>>=<\/code>” chaining operator.<\/p>\n
 This basic trick, of using the chaining operator to insert control flow into monadic sequences is an incredibly useful technique, which is used by a variety of really cool monads. Some examples that we’ll look at in later installments are
\nmonads for backtracking computation (like prolog); for non-deterministic computation; and for a really remarkably elegant way of building parsers.<\/p>\n
(In fact, if you’re not<\/b> very lucky, and I have time over the next couple of days to finish it, on friday I’ll post one of my own pathological programming languages, which has a parser implemented using the parsing monad. It’s a language based on Post’s tag systems, which form the most frustratingly simple Turing equivalent computing system that I know of.)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
So, after our last installment, describing the theory of monads, and the previous posts, which focused on representing things like state and I\/O, I thought it was worth taking a moment to look at a different kind of thing that can be done with monads. We so often think of them as being state wrappers; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[89],"tags":[],"class_list":["post-319","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-59","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/319","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=319"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/319\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=319"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=319"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}