tag:blogger.com,1999:blog-1777990983847811806.post5391466899455638872..comments2014-11-07T09:06:07.021-08:00Comments on Haskell for all: Haskell for Mainstream Programmers - Code reuseGabriel Gonzaleznoreply@blogger.comBlogger15125tag:blogger.com,1999:blog-1777990983847811806.post-65948159262692636422014-05-02T18:19:18.024-07:002014-05-02T18:19:18.024-07:00Sorry for the really delayed reply!
Yes, the real...Sorry for the really delayed reply!<br /><br />Yes, the real `fmap` for `State` only has two parameters if you insert all the newtype wrapping and unwrapping.<br /><br />However, to answer your more general question, it's perfectly legitimate to define a function in terms of the parameters of the function it returns. A great example of this is how function composition is defined:<br /><br /> (.) :: (b -> c) -> (a -> b) -> (a -> c)<br /><br />There are two equally valid ways to define it:<br /><br /> (f . g) = \x -> f (g x)<br /><br /> (f . g) x = f (g x)<br /><br />The reason this works is that the latter notation is syntactic sugar for the former version. All function definitions with parameters just get desugared to lambdas:<br /><br /> f x y = z<br /><br /> -- is equivalent to:<br /><br /> f = \x -> \y -> z<br /><br />Regarding the `State` function question, I should have been more precise and said that there is no way to define a function of type:<br /><br /> (s1 -> s2) -> (s1 -> (a, s1)) -> (s2 -> (a, s2))<br /><br />The way I phrased it before was really confusing.<br /><br />Regarding `second`, I find it helps to ignore the whole `Arrow` class stuff and just think of it as a function of the following type:<br /><br /> second :: (a -> b) -> (x, a) -> (x, b)<br /><br />This is a special case of the `Arrow` type, which is:<br /><br /> second :: Arrow arr => arr a b -> arr (x, a) (x, b)<br /><br />Just replace `arr` with `(->)` and you get the simpler version. I personally find this `Arrow` generalization of `second` to be really unfortunate since it's very non-obvious to beginners that it can be used in the simpler way.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-40560617529127674412014-04-20T20:07:14.535-07:002014-04-20T20:07:14.535-07:00Damn autocorrect, by "and" I meant "...Damn autocorrect, by "and" I meant "snd".<br />NekoNiaowhttp://www.blogger.com/profile/05869545668215870056noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-91789471753997289872014-04-20T20:06:06.892-07:002014-04-20T20:06:06.892-07:00I actually have to correct my first remark. After ...I actually have to correct my first remark. After looking up "second" I realized that I mistook it for "and" and that it actually seems to be a completely different beast (arrow), one which is completely out of my league (rookie).<br /><br />Maybe then, is it a little bit too advanced for an example?NekoNiaowhttp://www.blogger.com/profile/05869545668215870056noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-43325410936478073412014-04-19T19:29:03.389-07:002014-04-19T19:29:03.389-07:00I am trying to understand the State example but th...I am trying to understand the State example but there is something which puzzles me both with the type of fmap and its implementation.<br /><br />Shouldn't<br />instance Functor (State s) where<br /> fmap :: (a -> b) -> State a -> State b<br /> fmap f x s = second f (x s) -- a pure function<br />actually be:<br /><br />instance Functor (State s) where<br /> fmap :: (a -> b) -> State s a -> State s b<br /> fmap f x s = (s, second f (x s))<br /><br />Also something bothers me about defining fmap using three parameters when it only has two. I kind of understand that this has to do with the fact that fmap is a function which returns a function in this case so the last parameter x is meant for the returned function but being a complete rookie I am not too sure that this is the correct interpretation and if it is then I have to admit that this formulation bothers me since I cannot (yet?) grasp how the compiler can generate code for a function using parameters meant for the function it returns.<br /><br />I suspect that if State s a was expanded into its equivalent type then this would likely make sense but it is quite a steep shortcut to take for me at this stage.<br /><br />Finally I have two remarks regarding explanations you posted in the comments:<br />You say: "there is no function that has the type: `(s1 -> s2) -> (State a s1 -> State a s2)", but I guess you mean that it would not make much sense right? It seems to me that it is possible to write such function even if I have a hard time figuring out if it could be useful at all.<br /><br />Also, I'm confused when you say that the result of State s a is the a and not the s. I do not understand why since the state seems to me the most important part of the transition and a seems secondary since it's not taken into account for future transitions.NekoNiaowhttp://www.blogger.com/profile/05869545668215870056noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-2515747949164845132013-05-19T08:05:21.584-07:002013-05-19T08:05:21.584-07:00I have two kids, too, so I understand. :)
The len...I have two kids, too, so I understand. :)<br /><br />The lens packages are not my packages. They both belong to Edward Kmett.<br /><br />The key thing you need to read if you want to understand StateT is a paper called "Monad Transformers - Step by step". Google that and the PDF will be the first result. It is very beginner friendly.<br /><br />If you need more introductory concepts, then I recommend "Learn You a Haskell for Great Good", which walks through all the basic Haskell concepts for people new to functional programming.<br /><br />Also, thanks for the kind words!Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-15047722503446952652013-05-18T15:33:11.345-07:002013-05-18T15:33:11.345-07:00Hi, sorry for not responding for such a lon time, ...Hi, sorry for not responding for such a lon time, I've just checked and saw you answered me back in March.<br /><br />Unfortunately recently I've had very little time left for Haskell between my two young children and an insane workload (in fact, I've written half the post above back in February with my baby son slung over my shoulder trying to get him to sleep, and when I was very tired myself, that's why it has some incomplete sentences).<br /><br />Anyway, thanks for the detailed answers, I'll try to read them again later this week and respond. From reading them just now some things were clearly explained, but others were even more confusing than the original post. I'll try reading it again next week and see if I can point out the confusing parts.<br /><br />By the way, back in February I also wrote a response to your blog post about the State monad, however due to some bug (in Blogger, I assume) it got lost somehow when I pressed "Publish", and I was too tired to rewrite everything.<br /><br />To summarize, my response there essentially said that your explanation there was the best one I've read about the State monad yet. It just seemed a shame to me now you never saw it. I think you're doing a great job on this blog.<br /><br />I also started reading your series of posts on your Lenses package, however I didn't get very far, and I realized I obviously missed some concepts, so I went back to try and finish reading Real World Haskell.<br />Orennoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-47366978510560667652013-03-17T11:21:23.884-07:002013-03-17T11:21:23.884-07:00> All the examples given here seem to indicate ...> All the examples given here seem to indicate they change "something" "inside" the "context", but this is very, very vague. Is there a better definition? Also, "inside" is poorly defined.<br /><br />The definition of inside is literally "whatever is the last type variable". Any intuition more specific than that is bound to fail for some functor. All you need to know is that `fmap` changes the last type variable in something's type, whatever that type variable happens to be. That type variable *could* be a value that is wrapped, but that's not necessarily the case. For example, here's a Functor that doesn't wrap anything:<br /><br />data U a = U<br /><br />instance Functor U where<br /> fmap _ U = U<br /><br />Notice that the above definition of `fmap` satisfies the functor laws I described:<br /><br /> fmap id = id<br /><br /> fmap (f . g) = fmap f . fmap g<br /><br />... but there is no `a` value stored inside the `U`. It's purely a phantom type.<br /><br />> Speaking of which, I don't see any example of reuse here. Care to elaborate?<br /><br />Yes, that was an omission on my part. The reuse part comes about when we program generically over the `Functor` class. For example, I can write:<br /><br /> setToOne :: (Functor f) => f a -> f Int<br /> setToOne = fmap (\_ -> 1)<br /><br />... and that will work on anything that implements `Functor`, so I can reuse it for a wide range of types.<br /><br />An even more powerful example of Functor reuse is the `lens` library, but I can't fit the explanation of that within this comment.<br /><br />> What IS the result of the state, anyway? Why is it necessary? Isn't it a state like in a state machine? All you need then, in terms of data, is the state variable which is some of an enum, is this the "s" thing here?<br /><br />In `State s a`, the result is the `a`, not the `s`. The reason is that the `s` type is fixed throughout the computation and cannot change. So, for example, our state type might be an `Int` (i.e. the `s` is `Int`), but we may be interested in computing things using that state which are not `Int`s. This is why we distinguish between the state type and the result we are computing.<br /><br />There are a few cases when the state and the result coincide, like the `get` function:<br /><br /> get :: State s s<br /><br />... but that's just a special case.<br /><br />> What's so special about the getInteger example?<br /><br />The special part is that I was able to modify the result of an `IO` action without even understanding how `IO` works under the hood. Even more importantly, if the internal implementation details of `IO` were to change, `parseInt` would still work because it doesn't use any implementation-specific details about `IO`. It just uses `fmap` and then lets `fmap` do all the heavy lifting to make sure that the parser gets applied to the correct place (the result, in this case).<br /><br />If those answers are still confusing, feel free to ask more questions. I'd like to improve my explanation of this.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-78834639072213904642013-03-17T11:21:00.640-07:002013-03-17T11:21:00.640-07:00> How IS exactly changing the type of a tree, a...> How IS exactly changing the type of a tree, a set, a list or a map, "the same" as changing the result of a state? Those are obviously two different things.<br /><br />They aren't! That's the point! The reason that Functor is so useful is precisely because it is so abstract. The definition of a Functor is completely "positional". The trick to "getting" category theory is to just ignore what everything means and think of it as just a way of positionally manipulating types. Once you get in the "Haskell zone", you start approaching type-chasing "spatially". For example, when I program I might say to myself:<br /><br />"I have an IO Int, but I want an IO String. All I need to change is the Int and I don't actually care whether or not it is wrapped in IO or anything else. That means I want to use a Functor so I can just ignore the whole IO part, and now I only need to supply fmap with a function of type `Int -> String`."<br /><br />When you think in terms of these higher-order abstractions, you basically bypass all the complex machinery you don't need to deal with (i.e. the IO in the above example) and focus the part you actually care about (i.e. the Int). By doing so, I guarantee that I don't get tripped up by some accidental complexity involving `IO`.<br /><br />For example, if I write a function of type: `IO Int -> IO String`, I can't actually be sure that such a function isn't doing something weird involving `IO`, but when I force myself to only use `fmap` to modify the `Int`, I'm guaranteeing to myself that the ONLY thing I'm modifying is the `Int` and I'm not accidentally using the extra complexity that `IO` provides. In short, many category theory abstractions like Functor are a principled way to reduce software complexity by sandbox some function's effect and reducing complex problems into simpler narrower problems that have less opportunities to screw things up.<br /><br /><br />> Are there any rules for knowing what fmap will DO, given a certain context?<br /><br />Yes! Actually, there are exactly two rules that all instances of the Functor class must obey, no exceptions:<br /><br />fmap id = id<br />-- i.e.: fmap id x = x<br /><br />fmap (f . g) = fmap f . fmap g<br />-- i.e.: fmap (f . g) x = fmap f (fmap g x)<br /><br />In plain English, those two rules just say:<br /><br />* If you don't modify the wrapped value, you don't modify anything else either<br /><br />* If you do two modifications at once, it's the same as doing each one successively<br /><br />The first rule is the "sandboxing" rule. That's the rule that guarantees that `fmap` doesn't actually trigger any accidental complexity from the surrounding context. The idea is that you give 'fmap' an empty modification function (i.e. 'id') sort of like a test to see if it accidentally changes anything by mistake. If it doesn't modify anything, then you wrote the `Functor` instance correctly and you can guarantee that `fmap`'s effect is truly sandboxed.<br /><br />The second rule is the "refactoring" rule. It basically says that we can always group up or split apart multiple uses of `fmap` so that we can define whatever modularity boundaries we require.<br /><br />The really fascinating part is that it turns out that those are the ONLY two rules you ever need to prove. Those two rules alone always magically guarantee that you wrote it correctly and they always uniquely define the one correct implementation.<br /><br />The more important point is that those are the ONLY two rules you ever need to know about `fmap`. After all, the whole point of `fmap` is that it completely ignores the surrounding context (i.e. the `IO` or `State`), so by definition, any functions that modify the wrapped value cannot use any features from that surrounding context in their implementation. <br /><br />Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-2065912687905369672013-03-17T11:19:53.940-07:002013-03-17T11:19:53.940-07:00Ok, before I rewrite this post, let me first take ...Ok, before I rewrite this post, let me first take an initial stab at answering your questions and once I've answered them to your satisfaction I'll work it into the post.<br /><br />I have to split these answers into multiple replies because they are so long:<br /><br />> Why is fmap changing the State's result, and not the state itself?<br /><br />The best way to understand a lot of category theory concepts is that they are just a way of "organizing" types and operations on those types.<br /><br />For example, a Functor is nothing more than a type that exposes some way to modify its very last type variable. So when somebody says that `State s` is a `Functor`, that's just a fancy way of saying "I can change the `a` in `State s a`".<br /><br />For example, let's say that we reorganized the type variable and instead put them in the order `State a s`. You wouldn't be able to make a `Functor` out of that, because there is no function that has the type: `(s1 -> s2) -> (State a s1 -> State a s2)`.<br /><br />Note that a type can be `Functor` in more than one way. The simplest example is the pair:<br /><br /> data Pair a b = P a b<br /><br />It's obviously a functor over `b` since there exists a function:<br /><br /> second :: (b1 -> b2) -> (Pair a b1 -> Pair a b2)<br /><br />... but if we switch the type variables around it is also a `Functor` over `a`, too:<br /><br /> data Pair' b a = P' a b<br /><br /> first :: (a1 -> a2) -> (Pair' b a1 -> Pair' b a2)<br /><br />Category theory is totally abstract. It doesn't say what that last type variable should represent. All it says is that if it is a functor then we can modify whatever that type variable points to. Functors are just a structured way of interfacing with specific type variables.<br /><br />This is one of the reasons that you almost never get a straight answer when you ask "But what IS a Functor and what does that last type variable represent?" The real answer is that it can be anything that supports modification of some sort.<br /><br />- What if I need a more complex transformation of state or IO, something that is more complex than a simple (a -> b) ?<br /><br />By that I assume you mean that instead of:<br /><br /> fmap :: (a -> b) -> f a -> f b<br /><br />You instead want something like:<br /><br /> fmap :: C a b -> C (f a) (f b)<br /><br />... where `C` is some arbitrary instance of the `Category` class. Yes, that's perfectly reasonable. The only reason the `Functor` class uses just Haskell functions is just a historical artifact. With multi-parameter type classes you could generalize the `Functor` class to do what you ask:<br /><br /> class GFunctor c f where<br /> fmap :: (Category c) => c a b -> c (f a) (f b)<br /><br />Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-70671026964894903582013-03-04T08:18:19.485-08:002013-03-04T08:18:19.485-08:00Sorry for the delayed response. I agree with all ...Sorry for the delayed response. I agree with all your points and I will update the post to build a better practical intuition of what is going on. It takes a bit of time to do because I'm a slow writer, which is why I haven't fixed it, yet.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-34598827798168313602013-02-24T12:36:43.943-08:002013-02-24T12:36:43.943-08:00This is a good attempt to explain fmap. I've b...This is a good attempt to explain fmap. I've been reading Real World Haskell and it kept referring to fmap, dropping it here and there with not much of an explanation except a laconic "here, we use fmap", as if that should be obvious.<br /><br />But your explanation only goes halfway. You say that State s and IO are functors, but fail to explain what does fmap actually do in each case, instead resorting to just showing the definition and a simple example. <br /><br />Now, throwing an equation at the reader this way is probably ok for people who have an intuitive grasp of math, I'm not one of them. And math people won't be reading this particular blog entry anyway - it's all obvious to them. For me this was annoying.<br /><br />My suggestion: Why not explicitly say, in plain English:<br />1) fmap as defined for the State function takes the current state and the current result, changes the result using the given function, and returns the same state but with a different result.<br /><br />2) fmap as defined for IO takes the result of the IO action, changes it using the given function, and returns another IO action with the new result.<br /><br />Here are some questions which popped up into my mind while reading this:<br /><br />- Why is fmap changing the State's result, and not the state itself?<br />- What if I need a more complex transformation of state or IO, something that is more complex than a simple (a -> b) ?<br />- How IS exactly changing the type of a tree, a set, a list or a map, "the same" as changing the result of a state? Those are obviously two different things. <br />- Are there any rules for knowing what fmap will DO, given a certain context? <br /> All the examples given here seem to indicate they change "something" "inside" the "context", but this is very, very vague. Is there a better definition? Also, "inside" is poorly defined.<br />- Speaking of which, I don't see any example of reuse here. Care to elaborate?<br />- What IS the result of the state, anyway? Why is it necessary? Isn't it a state like in a state machine? All you need then, in terms of data, is the state variable which is some of an enum, is this the "s" thing here? <br />- What's so special about the getInteger example? I <br /><br />I think I know the answers to these questions by now, I'm just mentioning them because that's the kind of questions I asked myself when first reading about the state monad and the IO monad in RWH. I'm not too happy with the answers, BTW, but I'm willing to accept them.<br /><br />So, I dunno, you seem to have a sort of disconnect from what a "real-world" imperative programmer thinks like. Again, throwing equations at the reader and then waxing about <br /><br />Also, Real World Haskell calls these fmap uses "lifting operators". This should be mentioned here, I think, unless RWH's name is not the conventional one.<br />orennoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-54777499509032395462012-08-21T10:24:45.121-07:002012-08-21T10:24:45.121-07:00Jonathan Johnsson: It should work when you add a &...Jonathan Johnsson: It should work when you add a 'return ()' to the definition of 'add' in the following manner:<br /><br />"let add = (\n -> do x <- get; put (x+n); return ()) :: Int -> State Int ()", <br /><br />or equivalently:<br /><br />"let add = (\n -> get >>= put . (n +) >> return ()) :: Int -> State Int ()"Willem Obbenshttp://www.blogger.com/profile/09567608723622645197noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-3754952082908533552012-08-03T03:26:27.040-07:002012-08-03T03:26:27.040-07:00Ok, thanks. :) I realized just after hitting submi...Ok, thanks. :) I realized just after hitting submit that you could most probably define it either way ((a,s) or (s,a)). <br /><br />I actually noticed this difference in the process of trying to work through your post on state in GHCi. I got stuck on the conversion to do notation and tried to find out what I was doing wrong. If I do "let add = (\n -> do x <- get; put (x+n)) :: Int -> State Int ()" at the prompt, I get an error. The other versions of add has the type "Int -> State Int ()". Could you give me some hints? I guess there is some difference between your "bind" and "(>>=)". <br /><br />I'm quite new to Haskell and find some of the details of state to be a bit difficult, although I understand the main concept.Jonathan Johnssonhttp://www.blogger.com/profile/03882416756788411687noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-70714662751219934442012-08-02T06:07:08.528-07:002012-08-02T06:07:08.528-07:00Yeah, I actually take liberty with the State type ...Yeah, I actually take liberty with the State type and reverse the output to simplify the implementation of the monad instance. Both versions form a monad, but the official one is not as clean. However, I'll change both posts so that they make clear that I'm reversing the convention for simplicity.<br /><br />There's another reason I prefer this different ordering, which is that when you define the state monad using the Kleisli category formulation (where `return` is `id` and `(<=<)` is `(.)`), thenyou get:<br /><br />return = curry id<br />f <=< g = curry (uncurry f . uncurry g)<br /><br />... whereas if those variables are rearranged then it ends up being:<br /><br />return = (flip . curry) id<br />f <=< g = (flip . curry) ((uncurry . flip) f . (uncurry . flip) g)<br /><br />You are also right about the mistake in the other post. I will fix it.<br /><br />Some of the more recent posts are more advanced, but I will write some more intermediate posts soon.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-82067591765995928112012-08-02T02:38:15.468-07:002012-08-02T02:38:15.468-07:00Is there an error in the following?
"type St...Is there an error in the following?<br /><br />"type State s a = s -> (s, a) -- actually a newtype"<br /><br />Should (s,a) be (a,s)? I just read http://www.haskellforall.com/2012/01/haskell-for-mainstream-programmers_04.html and there it is<br /><br />"type State s a = s -> (a, s) -- actually a newtype, but whatever"<br /><br /><br />Also, on http://www.haskellforall.com/2012/01/haskell-for-mainstream-programmers_04.html, there is an error in one of the add functions, where it should say "put (x+n) s1" instead of "put x s1".<br /><br />I much appreciate your blog posts, by the way, and I'm working my way through them. :)Jonathan Johnssonhttp://www.blogger.com/profile/03882416756788411687noreply@blogger.com