Functor, Applicative, and Monad
typeslogicscats.gitlab.io
typeslogicscats.gitlab.io
This article is most readable to those who already understand OCaml code, and if you can already read OCaml code you already understand these concepts.
You can write perfectly fine production OCaml programs without knowing what a monad is. Some may, but a lot of OCaml devs don’t care about them.
"Haskell's built in support for monads is split among the standard prelude, which exports the most common monad functions, and the Monad module, which contains less-commonly used monad functions. The individual monad types are each in their own libraries and are the subject of Part II of this tutorial."
https://wiki.haskell.org/All_About_Monads#Monad_support_in_H...
The fact that monads are used to implement parts of the language doesn't make them a core part of it. Techniques used in implementation aren't the same as language features.
> A do expression provides a more conventional syntax for monadic programming
Yet I imagine most C# programmers have little to no formal understanding of Monads (although quite a few probably do at least know about the link).
It is only recently that I've started getting comfortable with concepts cogently explained in this post, so to me it is quite valuable.
As an aside, I think OCaml/Reason/Elm should become the de-facto Typed FP entrypoint for programmers instead of Haskell. That'll help drive more adoption for the paradigm because the ecosystem is a lot more approachable and one wouldn't feel overwhelmed to even begin.
It works on almost any platform, be it web, mobile, desktop or server via Fable, Xamarin or .NET Core.
It can work as an object-oriented language as well, which makes it easier to interface with C# code, but the documentation makes it very clear that functional is the way to go for F#.
For UIs there are libraries like Fabulous and Elmish, that provide a very similar programming model as Elm does.
You can even share code between all your target platforms:
It was a bit of a slog, but there are some wonderful books out there. I don't think we should discount the amount of pedagological resources that are available in the language. My favorite is the "First Principles" book.
As a side effect, I found that once I had learned most of Haskell (minus some of the language extensions aimed at type level programming). You pretty much won't find anything in any other typed language that will surprise you.
For people from dynamically typed or static OO background, being able to write functional code with records and sum types alone is a huge quality of life improvement. They should be able to get there with the least amount of effort. Haskell however demands far too much understanding and effort before it can be confidently used in a commercial setting. That excludes mainstream programmers who could otherwise most benefit from the paradigm.
I'm struggling to justify spending more time on picking up Haskell myself as I can't see clearly what's at the end of that tunnel.
This is a mistake. There are plenty of functional programmers who aren't familiar with these concepts. It's hardly a topic in introductory OCaml...
For a long time in the beginning I was just learning about the basics, like list manipulation functions, and typeclasses. There was quite a journey in between beginning Haskell and even starting to look at the learning material for monads/functors etc.
The product type is the type of pairs. It's definition is
x : A
y : B
--------------
(x, y) : A * B
- Product type on Wikipedia: https://en.wikipedia.org/wiki/Product_type - Product type on the nLab (which is a math-heavy resource): https://ncatlab.org/nlab/show/product+type
Instead, functors/monads/applicatives are more like a technique that can be used to solve a wide variety of problems that all coincidentally use the same function signature. And therefore, it's perfectly acceptable to say "I know how monads work with Maybe and List, but not Reader" Because fundamentally, how a Reader implements bind is in no way related to how Maybe or List implement bind.
If this is indeed true, what is the point of learning these "patterns"? From a mechanical understanding of the signature of bind and unit, you'd arrive at more sophisticated signatures, say filterM, but an understanding of what it does will still need an understanding of the specific implementation of the Monad instance it is being applied on. That sounds like a leaky abstraction. If so, why bother?
They are in fact much better, more precisely defined than classic design patterns.
And in expressive programming languages (that support higher kinded types or that at least let you encode such types) you can also describe generic code that works over any applicative or monadic type.
Having reusable functions that work just as well on lists, maybe/option, reader, io / promise or what have you means these type classes do a very good job at abstracting over data types. These are the purest forms of abstraction.
And you can get syntactic sugar from the language as well. For example "for comprehensions" in Python work via the iterator/enumerable protocol, but that's super limiting. Haskell's "do notation" or Scala's "for comprehensions" work on any monad instead, being much more powerful and reusable.
Unfortunately it takes an expressive language to understand and work with these abstractions comfortably. You won't grok monads in Go or Java.
This is where I get kinda lost. Can you give an example of such a reusable function that works for all these things which does something valuable?
I'm not sure how important that is when working practically with them though. I tend to think of typeclasses as something like categories of types that behave similarly.
Higher-kinded types are just "what if type parameters could be parameterized types" - I'd argue that from a certain perspective a language that allows them is simpler than one that doesn't. If you know Rust then you can hopefully see that Future#and_then, Option#and_then, and Result#and_then are in some sense "the same" function (and that function is the heart of the usual definition of a monad). But if you try to write some generic code in terms of and_then that could work for Future, Option, and Result, you'll find that Rust's type system isn't sophisticated enough to let you do that (even if you try to define a custom trait for it).
More generally, the way I tend to see applicatives and monads is: what if you could write an algorithm that worked generically for any secondary concern. What if you could write functions that incorporated what the AOP people call "pointcuts", in a generic way, but without having to step outside the type system and break the normal way that code and functions behave? But you absolutely need higher-kinded types before you can even start to talk about this, because you need to be able to talk about "wrapper" types in a generic way, which you can'd do if you can't have generic (parameterised) types as parameters.
Edit: seems like it's the latter.
(+1) <$> Just 1 → Just 2 (+1) <$> getIntFromThatUserThatOnlyTypes1 → IO 2 (+1) <$> [1,2] → [2, 3] ((+1) <$> ask) 1 → 2
Want let a function eat several burritos without making a mess? Keep your burritos apart with <>:
take <$> Just 2 <> Just "abc" → Just "ab"
etc.
You can be quite productive without moving past the burrito analogy.
Burritos may be a good analogy for some subset of monads, e.g. collections, but they are not a good analogy for monads in general: the function you pass to fmap may be executed now or later, zero, one, or many times, before or after a function you pass to a later fmap.
And once you've fully grokked burritos in terms of monads, you can finally reach that zen level where you solve your problems without even a single line of code (because you've started working at the burrito shop instead: http://chrisdone.com/posts/monads-are-burritos ).
(+1) <$> Just 1 → Just 2
(+1) <$> getIntFromThatUserThatOnlyTypes1 → IO 2
(+1) <$> [1,2] → [2, 3]
((+1) <$> ask) 1 → 2
take <$> Just 2 <*> Just "abc" → Just "ab"
In Haskell, that function is just called `mapM`, and it's consistent whether you're working with exceptional cases (Either String a), nullable cases (Maybe a), IO (IO a), Promises (Async a), or even weirder things.
This is actually a huge problem for the Java Streams API, because Java's checked exception feature is sort of like most monads. You can't call a function that throws an exception inside of a function that doesn't, except by using some weird incantation. (You can think of `try` as being a built in syntax for "running" the exception monad). Which means that you can't call an exception throwing function in `Stream::map`. Instead, you have to do something really ugly. https://www.reddit.com/r/java/comments/49yjqf/tunnelling_exc...
http://hackage.haskell.org/package/containers-0.6.2.1/docs/D...
It has the type:
alterF :: (Functor f, Ord k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
insert :: Ord k => k -> a -> Map k a -> Map k a
insert key val map = runIdentity (alterF (\_ -> Identity (Just val)) key map)
lookup :: Ord k => k -> Map k a -> Maybe a
lookup key map = getConst (alterF Const key map)
insertAndReturnOld :: Ord k => k -> a -> Map k a -> (Maybe c, Map k a)
insertAndReturnOld key val map = alterF (\old -> (old, Just val)) key map
insertNonDet :: Ord k => k -> a -> Map k a -> [Map k a]
insertNonDet key val map = alterF (maybe [Just val] (\old -> [Just old, Just Val])) key map
(note: this is all typed on my phone without a compiler to verify. There might be simple mistakes in the above, but it's all conceptually sound.)
That's all still just the start. You can insert an IO operation on the old value to calculate the new one, and it still only traverses the data structure once. Or a huge number of other things. Anything that can be made into a Functor can be used to augment the operation alterF does.
And you know the best part of all this? Despite all that freedom, the type of alterF tells you that you can't change the key associated with a value and even that you can't operate on more than one value in the map. It really is nice when simple things give you lots of options, but make it clear what they don't offer.
except you can't because you can have unlawful implementations.
filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
Now this is already a lot of information on what filterM does. But to use it in an action piece of code, you need to supply your own understanding of what the "action" is in this context. It does not matter whether or not you understand the implementation details of the specific Monad instance. You just need to understand its behavior: with the Reader monad, you know the action in question is just reading a piece of value from a "hidden" environment, so your filtering function has access to this environment when it determines whether or not to keep or retain an element; with the State monad, you know the action in question can possibly modify this environment as well; with the Maybe monad, you know the filtering action can say I don't know and that would result in the entire result to be Nothing as well.
Your argument of functions like filterM being a leaky abstraction is akin to saying, a Java interface is a leaky abstraction because you can't instantiate an interface (you need a class) so you need to understand both the interface as well as the class being used that implements the interface. Instead, think about it, it's just how the nature of combining orthogonal (de-coupled) things requires you to have an understanding of both of the pieces you are combining.
doubleIf :: Applicative m => (a -> m Bool) -> [a] -> m [a]
doubleIf f values = case values of
[] -> pure []
x:xs -> prepend x <$> f x <*> doubleIf f xs
where
prepend :: a -> Bool -> [a] -> [a]
prepend x True xs = x:x:xs
prepend x False xs = x:xs`keep`: Given a predicate and a collection, filter the collection to retain only items for which predicate evaluates to true.
`discard`: Given a predicate and a collection, filter the collection to discard items for which the predicate evaluates to false.
These are two very reasonable functions that would have the exact same signature, would be appropriate for the same arguments, but have two different behaviors!
The function below matches the signature of filterM for List monad, but does not do anything remotely similar to what you described.
foo :: (Int -> [Bool]) -> [Int] -> [[Int]]
foo f xs =
case bool of
[True] -> []
_ -> [xs]
where bool = f $ length xs
In OOP design patterns not only solve a specific problem, they are only used to solve the problem (no need to sprinkle the visitor-pattern all over your classes just because it's possible). Monad/Functor etc. instances are defined where they are possible. I view them as making inherent properties visible and explicit ("this action obeys these laws").
They are used to solve problems, but mainly by making abstract properties directly visible and reminding the programmer that he can just view them as this abstract concept and reuse existing machinery.
Back when I didn't understand what a monad was, I would read a bunch of tutorials and get confused by the analogies and examples. For example, I would get confused by comparisons to "boxes," or I would think that Maybe was the definition of a monad, or that IO was the definition of a monad.
The information in the tutorial that you link seems to be all correct. However, it's too "jumpy" for my tastes. The tutorial talks about "contexts," but doesn't really explain what a "context" is, except for making a comparison to "boxes." I get that a functor is an abstract idea, so explaining it in an understandable way is difficult. However, I wish that the article would discuss type constructors, because the idea of mapping types to types is an important part of the definition of functor. Without this explanation, I imagine that the comparison to "boxes" would have given the past me the wrong impression of what a functor is.
In my tutorial, I sought to teach the actual definition of a functor, applicative, and monad. I explain that a functor maps types to types and functions to functions in a way that preserves composition and identity, that an applicative preserves the product, and that a monad is characterized by a "join" operation that "flattens" the data and a "return" operation that "wraps up" the data. I actually would have preferred to explain the actual category theory, but I felt that it would be too intimidating, and so I attempted to convey the ideas in a non-category-theory way. With my current understanding of functor, applicative, and monad, I believe that if one doesn't learn their actual definitions, one doesn't truly understand them. I guess that I wanted my tutorial to be more rigorous.
However, I am not an expert on teaching, so maybe I'm taking the wrong approach.
See my Reddit comment: https://www.reddit.com/r/programming/comments/cy35zz/functor...
I think someone who is a beginner or just want to use Functor / Applicative / Monad without mastering underlying Category Theory, boxed model seems good enough. However, if you are creating own monads, then of-course we need to understand monadic laws. Every programming language has monad of some sort e.g. Optional in Java. To use optional chaining, I may not need to know all details but only how `flatMap` works. Maybe I am wrong too :).
[1] https://www.i-programmer.info/news/167-javascript/5207-crock...
Monad tutorials for newbies are like explaining quantum mechanics to someone who hasn't learned anything about optics or electricity or complex numbers yet - a bunch of false, meaningless metaphors.
> I use OCaml in this tutorial, with some occurrences of Haskell.
> My intention is for anyone familiar with the basics of typed functional programming to be able to follow along.
I don't know OCaml or Haskell and I got lost very early on due to the unfamiliar syntax. Do you think your explanation would be easy to translate to a more widely known language like Python or C?
I admit that I'm more fluent in OCaml than I am in Python or C, so please correct me if I'm mistaken.
The problem with other languages is that they lack the support for the higher order types, so the implementation is dishonest or you have to build up an API (new embedded minilanguage) to express them, which is a lot of work and a distraction.
And, the result tends to be very cluttered with syntax junk, as you can see in Scala and Functional Java.
Which incidentally is why people generally don't use these ideas in Java code. You can use these design ideas in your Java architecture, but not directly express them in your Java code.
And OCaml's module language is much more powerful than Java, since module language is a dependently typed language. You can't, say, pass a class including a type for another class in java.
Thanks, I liked reading it a lot. It's a good refresher, since I never use haskell but have read about this a couple of times.
The tutorial appears great on mobile, so I was able to refresh my memory very quickly. However, the code boxes had a very small font. I think this could me easily fixed with fome html-fu on the meta tag or the sizing of the box/font.
I also think that it would be great it you could explain at the end what is a counterexample input for the small haskell program. For example, if the user inputs a file that doesn't exist, then the readFile returns Nothing, then putStrLn returns Nothing. There's a sentence in the conclusion that explains that monads are nice to use but not why. I understand that it deals with values inside contexes, but in practice how does it affect development?
I'm a little confused by your last paragraph. My last code example doesn't use readFile and putStrLn, and it isn't written in Haskell?
class Functor f => Applicative f where
unit :: f ()
(**) :: f a -> f b -> f (a,b)
(i'll be writing the second operation as `××` in some places because of HN asterisk weirdness)
this gives us:
- `unit`, a "template" container with a hole we can fill (by doing `fmap (const myValue) unit`, equivalent to `pure myValue`)
- `fa ×× fb`, to "compose" two Applicative values. this shows how, unlike with Monads, the two computations must be "independent". for example, if IO were only an Applicative, you could do
print "hello" ** print "world"
getLine >>= \s ->
print ("hello, " ++ s)
it also nicely shows the two ways lists can be an Applicative - `fa ×× fb` can be either the Cartesian product `[(a,b) | a <- fa, b <- fb]` or `zip a b` (ZipList).
(also, it's kind of like a Monoid, which is neat!)
My two cents: personally, I would've started with the fact that a monad is exactly the stringing together of functions (a -> m b), and the similarity between monoids, monads, strings / lists and functions under composition. You mentioned that
• (a -> [b]) is the type of non-deterministic computations
• (a -> Maybe b) is the type of fallible computations
• (a -> IO b) is the type of effectful computations
• (a -> (s, b)) is the type of computations with state s
• that the Monad instance merely specifies how to compose them
• all such composable constructs can be expressed as a monad
• do notation and list comprehensions automatically work across all of them
and, in my opinion, these are all much more powerful motivation than beginning with a comparison to functors.
notePlayer notes octs dur = musicSeq $ (uncurry <$> notes) <*> ((, dur) <$> octs)
Won't make much sense without context, but it's there!
[2]: https://soundcloud.com/a-mathematical-way/not-enough-time-to...
notePlayer notes octs dur = musicSeq $ notes <*> octs <*> pure dur
That's really one power of functor/applicative/monad - if you understand their interfaces, you can work with new unfamiliar types that have these instances without much effort at all.
Although abstracting over this stuff isn't possible in any imperative language unless Scala or maybe advanced C++ template count. But that isn't due to their imperative nature exactly.
But local reasoning is very hard to count on in most other languages - that's for sure. It's easier to just run a VM in your head.
Purity's power is that beautiful meaningless changes are safe.
http://learnyouahaskell.com/functors-applicative-functors-an...
I would really hope to see a tutorial that have a diverse set of examples and just fmap each example with a light explanation of say, what is a monad in this code and what is not, and because it's a monad we can do this.
Essentially the tutorial can just train a classifier in one's head, and with a nice set of examples maybe the brain can learn a general representation of concepts for the classifier ...
It's just a start, but maybe it could help.
https://egghead.io/lessons/javascript-linear-data-flow-with-...
The Elm community goes out of it’s way to avoid talking about them because they make learning functional programming seem far more intimidating. It’s a very simple language though - Evan had always had beginners in mind when desiging the language and tools. If you’re looking to improve your functional programming skills it’s got a great learning curve.
I like OCaml because it strikes a balance between imperative and functional programming. Maybe learning OCaml would be easier than learning Haskell?
(Plus, OCaml has neat features like polymorphic variants and a powerful module system!)
More like one of these months/years. It's not just a language, but a philosophy of computation.
here’s the paper: https://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/b...
It turns out that every generic type t has a corresponding map function map : ('a -> 'b) -> 'a t -> 'b t.
Even worse with `data Bar a = Bar (a -> a)`.
You're right, my claim that every type 'a t has a corresponding (covariant) functor is incorrect, and I should either take that out or mention contravariant functors.
data Foo a = Foo (a -> a)
I always end up finding out more about any subject I actually publish a post about when people read it...
I thought isomorphism was when a function was reversible. I didn't think it had anything to do with currying.
The witnesses in Haskell are the higher-order functions (they transform functions) `{,un}curry`:
curry :: ((a, b) -> c) -> (a -> b -> c)
uncurry :: (a -> b -> c) -> ((a, b) -> c)Hom(A * B, C) ~ Hom(A, C ^ B)
This is one of the laws of a Cartesian closed category. The simply typed lambda calculus with products is the internal language of a Cartesian-closed category.
Mathematical language is worse specified than markdown and has a huge amount of ambiguity and requirement that you understand the context that you're working in.
It works fairly well for mathematicians, in terms of being concise to express complex ideas on a blackboard, but overall it's a mess.
But, functional programming is really about programming with types, not named things, and so a lot of the time we work with much smaller functions that are expressions. It should be trivial to follow the intention without explicit names.
Having terse and concise names can make it much easier to read if you're following the types. Occasionally, if a piece of code is more challenging to read, I may use single word variable names, but mostly it's trying to get the names out of the way of the types and operators.
For example, if I have a type (where `a` is generic):
a -> bool
It's definitely a mindset change for a different approach, functional programming is much more about function composition, whereas imperative is about a list of steps to perform, and so that composition is much more about whether the types fuse or not, the names become slightly less relevant, especially for general purpose library functions.
Personally, I feel it helps. But this is probably one of those subjective things like tabs vs spaces.
(spaces are correct)
You see this sort of thing from language warriors fighting silly wars but, yeah, what's wrong with Learn You a Haskell? Why must it be fought and suppressed immediately? Crazy...