tag:blogger.com,1999:blog-1777990983847811806.post5213878713371325770..comments2015-04-19T03:19:07.016-07:00Comments on Haskell for all: The functor design patternGabriel Gonzaleznoreply@blogger.comBlogger25125tag:blogger.com,1999:blog-1777990983847811806.post-15404785953264282732014-12-31T14:52:47.747-08:002014-12-31T14:52:47.747-08:00Yeah, Haskell is the first language that let me se...Yeah, Haskell is the first language that let me see the connections between mathematics and programming. It really appealed to me because I had always loved mathematics because of all the patterns and commonalities, so I loved it even more when I could find patterns and commonalities in my code that were also mathematical.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-4250617159448915082014-12-06T02:59:29.335-08:002014-12-06T02:59:29.335-08:00This post just blew my mind!
I guess your point i...This post just blew my mind!<br /><br />I guess your point is that Haskell awesomeness is part of a much bigger scheme.<br /><br />"Why Functional Programming Matters" by John Hughes was my first aha moment regarding FP - composing using higher-order functions and lazy evaluation as glue.<br /><br />This is my second aha moment - that we can use functors, monads, and other math stuff as glue. We can get powerful and generally applicable code by gluing together seemingly unrelated areas (e.g., using the same function on numbers, lists, Maybes, trees, IOs, and whatnot thanks to fmap). <br /><br />I keep hearing about Category Theory but never really got _why_ it matters (amid all the vague-sounding mathematical talk). This is the first time I've heard anyone claiming direct concrete benefits to us programmers.<br /><br />That's really inspiring! Now that I know it can make a huge difference, I'll dive into the whole math intuition behind Monad/Functors/Categories, etc. Thank you so much.<br />S Pradeep Kumarhttp://www.blogger.com/profile/05651956099656034363noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-80962186000161658872014-05-31T20:27:58.655-07:002014-05-31T20:27:58.655-07:00You're welcome!You're welcome!Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-92201535142590081432014-05-31T01:30:26.780-07:002014-05-31T01:30:26.780-07:00Thank you. I don't understand everything but t...Thank you. I don't understand everything but this explanation fills in some of the gaps of my understanding. jarturhttp://www.blogger.com/profile/06117763824030544555noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-34548974027078077932014-05-30T08:00:48.570-07:002014-05-30T08:00:48.570-07:00Sorry for the late reply. So to be totally accura...Sorry for the late reply. So to be totally accurate a functor is a combination of two things: a way to transform morphisms and way to transform objects. Using Haskell's `Functor` class as an example, `fmap` would be the way to transform morphisms (which are in this case functions) and the type constructor (like `Maybe`) would be the way to transform the objects (which in this case are types).<br /><br />In the monad morphism examples, this time the source and destination categories are kleisli categories (i.e. morphisms of the shape `a -> m b`) and the transformation between morphism is `(morph .)`. The objects are Haskell types and the monad morphism just leaves them unchanged (i.e. the identity transformation).<br /><br />The other examples are trickier because the source and destination categories in those examples are monoids. You can think of a monoid as a category with a single anonymous object, and the elements of the monoid are morphisms that begin and end on that object.<br /><br />Using the `length` example, the morphisms of the source category are lists and the morphisms of the destination category are integers, and both categories have a single nameless object which is not included in the type. The `length` function is the transformation between the morphisms and the single anonymous object is left unchanged (i.e. the identity object).<br /><br />So going back to your original question, the answer is that the combination of `Maybe` and `fmap` (specialized to the `Maybe` type) are the true functor.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-7811243530795915092014-05-20T22:36:39.524-07:002014-05-20T22:36:39.524-07:00What I don't understand is when I write
...What I don't understand is when I write <br /><br /> instance Functor Maybe where <br /> fmap = ... <br /><br />what is exactly a functor here? Is fmap a functor? Is Maybe a functor? Seems to me that Maybe is not a functor but why then we say that it is by defining an instance of Functor?jarturhttp://www.blogger.com/profile/06117763824030544555noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-52818774953164749062014-04-06T09:52:00.346-07:002014-04-06T09:52:00.346-07:00Why I should think of them as monoid homomorphisms...Why I should think of them as monoid homomorphisms when functors describe them just fine. What is the advantage of introducing an additional concept?Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-11641261239911675802014-04-05T11:02:44.408-07:002014-04-05T11:02:44.408-07:00You can construct a category from any monoid. That...You can construct a category from any monoid. That category has just one object, and the monoid elements become the arrows; the neutral element becomes the identity arrow. Under this translation, monoid homomorphisms become functors.<br /><br />It's unclear to me that it's useful to think of these as functors instead of monoid homomorphisms, though...robhttp://www.blogger.com/profile/15111725241719520181noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-7221359760822637912014-03-29T14:32:04.563-07:002014-03-29T14:32:04.563-07:00I'm not very good at category theory, so take ...I'm not very good at category theory, so take this for what it's worth. Delete if not helpful.<br /><br />From a mathematics view, it seems that categories and monoids are being confused with each other. Under "Functors Hidden Everywhere", the post claims lists with append and numbers with addition are categories. I would claim they are objects in the category of monoids. You have an underlying set (lists of Characters, or individual Integers), an operation on members of the set (append, or add), and an identity (empty list, or zero) and out comes a monoid.<br /><br />To treat lists as a functor, which you can do, you have to think what categories they are moving between. One possible list functor (there are many), moves from the category of sets to the category of monoids (also called the free monoid functor). Take your underlying alphabet (the set of all characters, or the set of all objects of some kind), and lift it into the kleene closure (all finite lists of characters from the alphabet), with the added append operation and empty list. This is essentially what Haskell lists do and why they are functors. All lists of a given kind (say, lists with lower case letters as elements) comprise a single object in the monoid category.<br /><br />Integers with addition can be thought of as an object in a category, like the category of abelian groups, or the category of monoids.<br /><br />Basically, these ideas in category theory are one step more abstract than the way they are presented and used here. A category does not have an identity object, but each object in a category has an identity arrow. Composition is the stringing of arrows together, not an arbitrary operation between objects that you get to define.thaumkidhttp://www.blogger.com/profile/11319338489107643359noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-24705929101715926602013-09-03T18:16:40.026-07:002013-09-03T18:16:40.026-07:00It doesn't change the type in that specific ca...It doesn't change the type in that specific case. The reason it is there is that monad morphisms do need the forall notation when they are the argument of a function and I just kept it for consistency.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-20823688808659713042013-09-03T17:47:39.868-07:002013-09-03T17:47:39.868-07:00I'm still struggling to understand the purpose...I'm still struggling to understand the purpose of `forall`, and maybe this is a good chance to get some insight: what is the purpose of `forall` in<br /><br /> morph :: (Monad m, Monad n) => forall r . m r -> n r<br /><br />The function would be already polymorphic without the quantifier. How does the quantification change the type, in concrete terms?Riccardo Pelizzihttp://www.blogger.com/profile/07735194013529688266noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-52394755632815809732012-11-01T11:32:15.818-07:002012-11-01T11:32:15.818-07:00Actually, 3 is the morphism and the source/destina...Actually, 3 is the morphism and the source/destination are just some anonymous object which could be anything. That's the confusing thing about monoids, which is that the monoid elements (i.e. the 3) are the morphisms, not the object. Mappending monoid elements (i.e. adding integers) is analogous to composing morphisms and the monoid laws correspond to the category laws.<br /><br />Monoids are an example of a category where the morphisms are more interesting than the object.<br /><br />To make the analogy perhaps clearer, you can remember that for any Haskell `Category` instance you can simply pick one object in that `Category`, any object, and all functions from that object to itself form a monoid:<br /><br />instance (Category c) => Monoid (c a a) where<br /> mempty = id<br /> mappend = (.)<br /><br />For example, if the category is the category of Haskell functions, then you just pick some type `a` and all function of type (a -> a) form a monoid. For example, let's say that `a = String`, then, you can take all functions of type `String -> String` form a monoid:<br /><br />f :: String -> String<br />g :: String -> String<br /><br />mappend f g = f . g :: String -> String<br /><br />mempty :: String -> String<br />mempty = idGabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-22568822475653382352012-10-29T04:05:31.977-07:002012-10-29T04:05:31.977-07:00Yeah, I’m confused :)
So, lists and integer are b...Yeah, I’m confused :)<br /><br />So, lists and integer are both morphisms in the Monoid category, because the source and destination objects of these morphisms coincide. More concretely, in the category IntCat 3, 3 is the both the source and the destination. Correct?Giorgio Valotihttp://twitter.com/giorgio_vnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-41197283132053365532012-10-25T10:50:50.716-07:002012-10-25T10:50:50.716-07:00A functor is actually TWO things:
1) A way to map...A functor is actually TWO things:<br /><br />1) A way to map objects, and<br />2) way to map morphisms.<br /><br />This post only discussed how a functor maps morphisms because I wanted to give a treatment of objects in a later post.<br /><br />So your "container-ish" intuition is more or less right in the sense that a functor transforms an object. You might imagine that if the functor is "F", and the object is "X", then you can wrap the object "X" in "F" to generate a new object: "F(X)". <br /><br />However, since I gave a "morphism-only" treatment of functors, it didn't really make clear what the objects were and what "F" is wrapping, so I'll try to address this using the concrete example I gave of "length".<br /><br />It's type signature is:<br /><br />length :: [a] -> Int<br /><br />"length" transforms morphisms, not objects, meaning that the list (i.e. "[a]") is a morphism in some source category and the Int is a morphism in some destination category.<br /><br />In this particular case, the source category is a Monoid (where mappend = (++) and mempty = []) and the destination category is a Monoid (where mappend = (+) and mempty = 0). Remember that the lists are morphisms, not the objects, and the integers are morphisms, not the objects. That's why they don't have the container-like shape you are expecting.<br /><br />But there are objects there, even if they don't show up in length's type signature. To see why, you have to think of a Monoid as a category with one object. In fact, the nature of the object does not matter at all. It could be anything. The only thing that matters is just that there is only one such object.<br /><br />So let's call that single object "X". That means that lists are morphisms from "X" to "X". We can prove this by wrapping Haskell lists in a GADT that permits a suitable "Category" instance:<br /><br />-- Notice that we never actually use 'x'<br />data List e a b where<br /> List :: [e] -> List e x x<br /><br />instance Category (List e) where<br /> id = List []<br /> List xs . List ys = List (xs ++ ys)<br /><br />Since there is only one object in this category, every morphism has the same source and destination object, so all compositions type-check. Monoids are basically categories where we just want to ensure that every composition type-checks.<br /><br />We can similarly define a category for Ints:<br /><br />data IntCat a b where<br /> IntCat :: Int -> IntCat x x<br /><br />instance Category IntCat where<br /> id = IntCat 0<br /> IntCat x . IntCat y = IntCat (x + y)<br /><br />So using these two GADTs I've made the objects explicit so we can talk about them now.<br /><br />This means our "length" function should really be thought of as:<br /><br />length :: List e a b -> Int (f a) (f b)<br /><br />... where f is the container-like thing you were looking for. Notice the similarity between our upgraded "length" type signature and "fmap"'s type signature:<br /><br />length :: List e a b -> Int (f a) (f b)<br />fmap :: (a -> b) -> (f a -> f b)<br /><br />Now we can see that we are actually transforming objects under the hood in a "container-ish" way, even if the original type of "length" didn't really make that explicit.<br /><br />The only difference is which source and destination category we use. fmap uses the category of Haskell functions for both its source and destination category. length uses the list monoid as its source category and the Int monoid as its destination category.<br /><br />I'm sorry if that's long-winded and perhaps confusing, but if you need any more clarification I'd be happy to help.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-7283577117160645522012-10-25T09:54:04.606-07:002012-10-25T09:54:04.606-07:00Hi Gabriel, if I understand correctly, you seem to...Hi Gabriel, if I understand correctly, you seem to imply that a functor is more or less a function which respects a given set of properties regarding composition and identity of the source and destination categories. However, when I look at this example: http://www.haskell.org/haskellwiki/Category_theory/Natural_transformation#Vertical_arrows:_sides_of_objects it seems to view the functor more as a container. <br /><br />They both make sense but I don’t know how to reconcile them.Giorgio Valotihttp://twitter.com/giorgio_vnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-25984540528831622432012-10-23T12:31:26.014-07:002012-10-23T12:31:26.014-07:00Yes, the code should run identically no matter whi...Yes, the code should run identically no matter which bind you choose. In practice, there may be performance differences.<br /><br />This definition of equality ignores observable differences in performance, but you could imagine some more sophisticated language where performance differences had some in-language representation and equality also meant "equally performant".<br /><br />Also, I will fix the typo. Thanks for bringing that up.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-29985318207122226652012-10-23T12:27:46.953-07:002012-10-23T12:27:46.953-07:00Hi Gabriel, thanks for this. I want to point out a...Hi Gabriel, thanks for this. I want to point out a typo in, and ask a question about, building the bridge between enumerator and iteratee.<br /><br />Typo: the 'f' at the end of the chain should be 'h' for both code1 and code2, e.g. "code1 = f <=< ..." should be "code1 = h <=< ..."<br /><br />Question: You motivate a preference for I.(>>=) over E.(>>=), but it's not clear where that topic leads. By showing that the composition law holds, are you simply showing that the code is provably correct regardless of which bind you choose? For some value of "provably". :)Bryan Richterhttp://www.blogger.com/profile/00380593834900043397noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-61292052912138489362012-09-24T17:14:20.688-07:002012-09-24T17:14:20.688-07:00Yes, this was a mistake on my part. At the time I...Yes, this was a mistake on my part. At the time I wrote it I had in mind the following composition:<br /><br />(>->) :: (a -> (b, b)) -> (b -> (c, c)) -> (a -> (c, c))<br />(f >-> g) a = (g $ fst $ f a, g $ snd $ f a))<br /><br />id2 :: a -> (a, a)<br />id2 a = (a, a)<br /><br />id2 >-> f = f<br />f >-> id2 = f<br />(f >-> g) >-> h = f >-> (g >-> h)<br /><br />And then you get the correct functor laws:<br /><br />(fst .) id2 = id<br />(fst .) (f >-> g) = (fst . f) >>> (fst . g)<br /><br />... but somehow the wires got crossed when I wrote it and I wrote something completely wrong. I'll just remove the example.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-43847401546652529062012-09-17T07:34:23.720-07:002012-09-17T07:34:23.720-07:00Wow, that's really pretty inspiring that you&#...Wow, that's really pretty inspiring that you're mostly self-taught. I've seen you around on /r/haskell and I appreciate the effort you put into discussing, debating and explaining things there. Thanks and keep it up!Dan Fornikahttp://www.blogger.com/profile/04261210451709985032noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-66628717465460348032012-09-16T19:07:16.016-07:002012-09-16T19:07:16.016-07:00There's a typo in the type of (fst .):
(fst ....There's a typo in the type of (fst .):<br /><br />(fst .) :: ((a, c) -> (b, c)) -> (a -> b)<br /><br />this type is uninhabited (or would be if not for bottoms), snce you have nowhere to pull from the c to plug in, and the b in the result can depend arbitrarily on it.<br /><br />I think you meant<br /><br />(fst .) :: (a -> (b, c)) -> (a -> b)<br /><br />which is, incidentally, the principal type of (fst .) anyway.<br />gergo-erdihttp://gergo-erdi.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-83706485933669881412012-09-16T12:03:42.100-07:002012-09-16T12:03:42.100-07:00I think the way I learn most of these things is a ...I think the way I learn most of these things is a combination of programming in Haskell, some self-taught category theory, and looking for patterns in my own programs and libraries.<br /><br />I don't read a lot of computer science papers. Usually I only read a paper if it comes up in a Google search or if it appears on /r/haskell. Most of the category theory I learn is either (a) from Wikipedia, (b) from asking more experienced Haskell programmers (either on #haskell or /r/haskell), or (c) from Steve Awodey's Category Theory textbook, in roughly that order.<br /><br />Unfortunately, most literature on category theory uses math examples to motivate each topic, which would really frustrate me, so I would read about it and I wouldn't "get" the significance of it to programming at all. Like, I'd be able to define it and point to Haskell code examples of it, but I wouldn't understand the purpose or motivation behind it or why I should structure my code that way as opposed to some other abstraction or design pattern.<br /><br />For example, I took a scientific writing mini-course and they would always stress that you should begin with the motivation and purpose before you introduce anything else, and I found that profoundly missing from every category theory topic, at least with respect to programming. So I decided I would just try to figure it out on my own instead of waiting for the category theory tutorial that would never come. Mathematicians seemed to be generally excited about category theory and how generally applicable it was, so I just sort of kept trying, assuming that they were really onto something. It took me a while before I could finally figure out a way to articulate their excitement in a programmer's voice.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-69809365770188441812012-09-16T10:52:36.864-07:002012-09-16T10:52:36.864-07:00How have you learned such a deep understanding of ...How have you learned such a deep understanding of Haskell's type system and category theory? Do you study this at school? Do you read a particular academic journal, or have a good textbook to suggest?<br /><br />I've been making my way through Real World Haskell, and it's great but this sort of post is just on a whole other level.Dan Fornikahttp://www.blogger.com/profile/04261210451709985032noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-23540663503112353992012-09-16T03:10:19.566-07:002012-09-16T03:10:19.566-07:00Eh, I guess your blog didn't like the OpenID a...Eh, I guess your blog didn't like the OpenID auth I used, but that's my comment above.Twisolhttp://www.blogger.com/profile/02414993179869658725noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-32531083360007515642012-09-16T03:09:15.115-07:002012-09-16T03:09:15.115-07:00This comment has been removed by the author.Twisolhttp://www.blogger.com/profile/02414993179869658725noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-40622714408285338052012-09-16T03:07:26.558-07:002012-09-16T03:07:26.558-07:00I'm a relative newcomer to Haskell, and your b...I'm a relative newcomer to Haskell, and your blog has been a huge boon for learning to think more functionally. Great work, and thanks!idhttps://www.google.com/accounts/o8/id?id=AItOawk68L_4DiSkvMyoENqZXLEB6NddA6QVeKQnoreply@blogger.com