Functors, applicatives, and monads in pictures
adit.io
adit.io
When you program in normal languages, you have the ability to perform effects all of the time. You can always read/write to/from files, you can always raise exceptions or otherwise change the control flow. There's nothing you can't do.
Haskell is different. In Haskell, by default, you don't have any effects at your disposal at all. You can create values from other values, that's it. When you want to program with effects, you use a monad. The type of monad that you use decides the effects that you are allowed. For example, the maybe monad instance gives you the "fail without an error effect". The either monad gives you the "fail with an error effect". The list monad instance gives you the non-determinism effect. etc. You might expect me to say that IO gives you the "interact with the outside world effect", but that's not really true, forget what you know about IO for the moment.
The continuation monad instance is a bit special. In a sense, it is the most general of the monad types, because every monad instance can be seen as a specialization of it. The continuation monad allows every kind of effect. At this point, you might be thinking, "but how can this be, it doesn't allow IO".
To reconcile these facts. I present the coroutine monad. It has an effect, yield, that gives a value to the caller and waits for the caller to respond with a value so that it can continue. Here are some types:
runCoroutine :: Coroutine i o x -> Either (o, i -> Coroutine i o x) x
yield :: o -> Coroutine i o i
This is why Haskell is pure despite having effects. Haskell programs don't do IO, they yield control to the runtime environment whenever IO needs to be done.
So why are monads useful? They allow you to restrict the effects that are possible in different parts of your programs. This aids in reasoning about your programs, because you don't have to think about whole classes of behaviour, but they're less useful in other languages where you already have effects everywhere.
> but they're less useful in other languages where you already have effects everywhere.
Scala has side effects everywhere, yet the Monad is extensively used in Scala programs. Monads have nothing to do with "effects".
Monads are not used to decide the kind of "effects" you are allowed. By calling every Monad a kind of "effect", you are just begging the question. Monads are merely objects that follow 3 monad laws, no more no less.
> This is why Haskell is pure despite having effects. Haskell programs don't do IO, they yield control to the runtime environment whenever IO needs to be done.
How is this different from a C program? Haskell is pure in the presence of IO, because the type system tracks IO calls and forces any function that even indirectly refers to a quantity obtained via IO to modify its type signature to reflect the IO action. This can be done with/without Monads. Haskell IO is a Monad, because it pretty much analogous to the State Monad and Haskell has special Monad syntax that lets you pass the World State implicitly and write imperative code in an imperative style.
The monad operations happen to be a convenient interface for combining IO values to form a composite value that is then called "main", and when the program is actually run, the value of main is executed to produce all the effects.
newtype PureIO a = PureIO (() -> a)
print :: String -> PureIO ()
print s = PureIO $ \_ -> unsafePrint s -- impure primitive
Invoking the pure IO values is something only the runtime can do, so referential transparency is not violated.
The important thing here is the abstract type wrapper. You're exposing pure primitives that are implemented in terms of (hidden) impure ones.
That's why code that uses unsafePerformIO can be pure and referentially transparent, as long as the exposed primitives are pure and implementation details are hidden.
To demonstrate this, imagine that you did expose the PureIO data constructor -- then values of type PureIO would not be referentially transparent anymore.
That's quite an assertion.
> Scala has side effects everywhere, yet the Monad is extensively used in Scala programs. Monads have nothing to do with "effects".
I didn't say monads weren't used outside of Haskell, I say that they are less useful. I haven't programmed in Scala before, I assume monads are used for their notation. They aren't required.
> Monads are not used to decide the kind of "effects" you are allowed. By calling every Monad a kind of "effect", you are just begging the question. Monads are merely objects that follow 3 monad laws, no more no less.
I don't know if you're familiar with group theory, but in group theory, every finite group is a specialization of the group of permutations. Groups are defined abstractly by the operations that they allow in the same way that monads are, but this definition for finite groups is as general as saying that every group is a subgroup of the group of permutations.
It's the same for monads, they are defined abstractly, but the abstract definition is equivalent to saying monads are all of the things that you can create by a specific kind of specialization of the continuation monad.
Continuations are an effect. Specializations of continuations are also effects. Monads define effects. What's really interesting is thinking about monads in terms of the Curry-Howard Isomorphism, on one end of the scale, the identity monad, you have constructive logic and at the other end, continuations, you have classical logic, what's in the middle? Does the list monad instance have an interesting associated logic?
Which question am I begging?
> How is this different from a C program?
It's just a different way of looking at programs. The distinction is never drawn for C programs.
> Haskell is pure in the presence of IO, because the type system tracks IO calls and forces any function that even indirectly refers to a quantity obtained via IO to modify its type signature to reflect the IO action.
This is quite a shallow way of looking at it.
> This can be done with/without Monads.
Sure, you could use continuations or uniqueness types.
> Haskell IO is a Monad, because it pretty much analogous to the State Monad
AFAIK, that's not defined in the Haskell standard, but that is the way that GHC does it.
> Haskell has special Monad syntax that lets you pass the World State implicitly and write imperative code in an imperative style.
No, it's not syntax that's letting you pass the world state implicitly. In GHC:
IO x = State RealWorld x = (RealWorld -> (RealWorld, x))
Monadic combinators are really just kind of type-sugar. Think: any ordering of computations can be expressed as a tree. However, the only ordering trees a pure-functional language must obey are call-trees (the parameters of a function must be computed before the results of a function, even after lazy-evaluation is taken into account). Monadic programming is a way to transform arbitrary ordering trees of possibly-dynamic depth and width into call trees while preserving the original ordering.
The really neat thing about monads is that they statically guarantee they'll preserve the original ordering, despite its being of dynamic width and depth.
There are plenty of effects IO (the ambient monad of most languages) doesn't support:
You can't do ListT fork effects. You can't do ContT effects (coroutines are not as powerful as ContT). You can't have Parsec effects (you need to write parser combinators as in Haskell).
The Monad generalization is useful for working with nullables, lists, and the effectful view of Monads is only one way to see them.
When using languages "without monads" I do miss Control.Applicative and Control.Monad very much.
> the effectful view of Monads is only one way to see them
Absolutely, but what's interesting is that it is as general as any other view of monads.
They're hard to implement in Javascript though, because of return type polymorphism or explicit dictionary passing being required. So people don't implement them -- not because Monads aren't useful there, but because Monads are hard to implement there.
Here's a recent experience I can share: I've been working on a Haskell project for three days now, I've been type-checking as go, but I haven't been running the program I'm writing. This is mainly because I started "in the middle" and so I couldn't just run it, I'd have had to have written supporting code.
I've finally got to the stage where I _can_ run it. I've just tried it now and thanks to the style in which I write Haskell, where I clamp down quite severely on unnecessary effects/complexity before they become issues, it works perfectly. Creating specialized monads is just one aspect of the style of writing. This wasn't a trivial project either, I've essentially written a cross between a database and distributed source control.
Would you have a specific suggestion to improve his presentation?
And I've given Maybe's Monad instance definition as well as explained it in pictures. If there's something missing please let me know specifically.
The audience level of this piece is confusing -- it looks like a friendly, cartoony introduction for a general audience, but it actually assumes you already know Haskell.
Basically, you and I are not the intended audience.
i wish people who are writing guides on these topics pick a non-simplified situation where using this method makes for an easier program (vs using the "traditional method"). The comparison and contrasting of a functional/monadic approach vs a procedural approach in a complex scenario might actually shed more light - at least, for some one who is familiar with the procedural approach.
http://book.realworldhaskell.org/read/programming-with-monad...
"Learn You A Haskell For Great Good" [1], while much less complete, is the best intro I have found so far. It's also free.
There are very few things in the world of CS/programming where I can't follow along and grok what's going on, especially when laid out in a tutorial form like this. The fact that I was totally lost when reading this is not a good sign when you're trying to get people to adopt your school of thought.
At the end of the day, you adopt a new way of thinking that is incredibly clarifying for all programming. One simple thing is that it allows you to "see" where state, re-entry, evaluation, IO, and failure are happening in a program---things that you are blind to when you're used to languages where the answer is "always".
This article isn't even meant to explain why you ought to learn Haskell. It's more like a signpost on your path to mastery, should you begin walking it.
That's probably because most of the tutorials you've followed have adopted an imperative style of programming. It is easy for you to follow along because it really isn't all that different from what you are accustomed to. Functional programming really is a different beast entirely. It's often said (though I remain skeptical) that it's actually easier to learn functional programming as a non-programmer than to un-learn your imperative programming tendencies.
>The fact that I was totally lost when reading this is not a good sign when you're trying to get people to adopt your school of thought.
I don't think that's a fair assessment. You could say the same thing about starting from functional programming and switching to imperative; some people actually do this! They find the idea of mutating a variable to be completely counter-intuitive!
The notion of mutation is implicit in the definition of "variable."
So you don't change it during one exercise, but you can and certainly will change it when you change the exercise to another one with the same principle.
For example, if you integrate x^2 dx from x=0 to 10, x changes continuously.
It's clear that x is not fixed to any particular value.
foo x = x * 2
The series of additions can also be infinite, in which case it would be quite difficult to expand fully, but that doesn't prevent you from doing mathematics with it.
That's not analogous at all to mutation.
As someone who'd done reasonably well with both and had thought of them as heavily overlapping areas, I thought this was interesting, so I tried to poke at this a bit.
One of the concepts I got back from a talented classmate was basically a complaint about mutable variables -- that in an algebraic description of relationships for a given system what we call "variables" are less variable and more "unknowns" which represent fixed if unidentified quantities. Others similarly noted there was something absurd about writing out equations like "x = x + 2".
The trick is to stop reading that line (in your head) as "x is equal to x plus two", but instead "x is assigned the value of x plus two".
That's one potential takeaway, but when I turned over the complaint in my mind, this was arguably another way of complaining about mutability.
Also, given the timing, it's pretty likely that one of the languages they'd learned was Pascal: that was the language of the first few CS classes at my school in the 90s, it was also the language of any high school curriculum that led to the AP exam, and Borland's Pascal products were still pretty popular PC dev environments.
They could've also been unlucky and received their first exposure by choosing to do a numerical analysis class in Fortran or C, of course. :/
Source: all my classmates.
Haskell is difficult to explain because it has many terms, vocabulary, and syntax that are not familiar to people. It's ML-style syntax doesn't help.
Most tutorials targeting Haskell beginners implicitly assume the readers already know the Haskell syntax, terms, definition, etc, and go right ahead to explain the advance concepts like functor, applicative, or monad. It's like teaching them how to fly before they know how to walk, in the Haskell land. No wonder Haskell beginners are frustrated with any of the monad tutorial.
The thing is. Stop. Stop telling beginners what monad is. Just show them the basics in Haskell and get something useful going. Get them to write and use Haskell programs. When the need arise, they will look into what monad is. Programmers have used STL plenty without knowing the internals of C++ templates. Same thing can be done with monad.
> When the need arise, they will look into what monad is.
I couldn't have said it any better. This is the exact scenario that this post is aimed at.
The Haskell community has a longstanding tradition of using condescending language ("fmap is from the street, fmap is hip to contexts."), and deliberate childrens-book style metaphors and illustrations in tutorials.
The theory seem to be that if monads haven't been adopted by mainstream developers yet, it is just because the presentations haven't been dumbed-down and kiddie-friendly enough yet. (If only they from the onset had called "monads" for "warm fuzzy things" instead, surely developers would not be so scared of them!)
The strategy have not yet borne fruit, though.
Maybe is usually used as an example since it's the simplest non-trivial monad (and therefore also an applicative functor).
The point of eg. fmap etc. is that you can have regular Int -> Bool functions, and apply them to data with more structure than simple values. a Maybe String is not a String, but you can still transform one to uppercase by doing fmap (map toUpper) mstring. The fun part is that that exact same thing works on a list of strings, an IO String (fmap (map toUpper) getLine), a Tree of Strings, etc... It's fully generic over anything that can implement Functor; the exact behaviour is defined by the particular instance.
Applicative is just an extension to the idea, where the function applied itself can have this extra structure, and when combined with an infix fmap you get to do
(+) <$> Just 2 <*> Nothing <*> Just 5 -- Nothing
(++) <$> getLine <*> getLine -- IO action that reads two lines and concats them
a Monad is yet more powerful because it allows a previous computation to affect what follows in an arbitrary manner (Applicative doesn't), allowing things like state, asynchronous execution, continuations, and countless other things. It's such an useful abstraction that Haskell provides the do syntax for using it.
Edit: In languages like Java where all types are nullable, if you uppercase a String, but that String is null, your program breaks, even though the type system claims that you have a String when in reality all types are Maybes, and you are forced to always check for nulls manually or just rely on users to not give you nulls, even though it would be trivial for the compiler to check something like that statically if the language were expressive enough to allow it.
Rust also has a Maybe type as well. You use it like this:
use core::io::{Reader,ReaderUtil};
use core::io::println;
fn main() {
let in = io::stdin().read_line();
println("INPUT:");
println(int::str(int::from_str(in)));
}
$ make
rustc option.rs
option.rs.rs:125:23: 125:41 error: mismatched types: expected `int` but found
`core::option::Option<int>` (expected int but found enum core::option::Option)
option.rs:125 io::println(int::str(int::from_str(in)));
^~~~~~~~~~~~~~~~~~
error: aborting due to previous error
make: *** [build] Error 101
We can make the compiler satisfied by pattern matching over the return value:
use core::io::{Reader,ReaderUtil};
use core::io::println;
fn main() {
let in = io::stdin().read_line();
match int::from_str(in) {
Some(number_string) => println(int::to_str(number_string)),
None => println("Hey, put in a number.")
}
}
This is where the advantages of Maybe come into play. In dynamic languages, you don't get the advantage of always making sure you handle the degenerate case.
Now, what the Maybe _monad_ does is allow you to chain multiple things that work with Maybe together. I don't have a Rust example of this handy. Like "Do this, do that, do the other thing, and then let's see if that failed anywhere along the way."
Asynchronous execution is one particular case that I like as an example: You can implement promises (which represent async computations) in Haskell and such a Promise type will also be able to implement the monad type class. Because they are monads, you can use do notation:
-- Let's assume we want to fetch two large datasets asynchronously over the network and filter them
asyncSanitize :: Promise [String] -> Promise [String] -> Promise [String]
asyncSanitize p1 p2 = do
x <- p1
y <- p2
return (sanitize (x ++ y)) -- no callbacks!
Think of Maybe as a container. It either "contains" a value, or it doesn't. The container itself is not usable except for passing around; it's the contained value that is important. Even if we know that the container is supposed to contain a number, we can't use the container to perform computations; every time we need the number, we need to open the container, peek inside, and decide what to do whether it's contains something or nothing.
In Haskell terms, this "peeking inside" is typically done with pattern matching, which is core to the type system. For example, this is a function that checks if a Maybe value has anything, and returns true or false:
hasValue x =
case x of
Just _ -> True
Nothing -> False
At the opposite end, we can have functions that produce Maybes (naive and simplified example, not working code):
fetchPage url =
do response <- performHttpRequest "GET" url
case (getStatusCode response)
200 -> return (Just (getBody response))
404 -> return Nothing
In languages such as Java or Ruby we can build classes that are containers that act in a similar way. But those languages are limited in that "peek inside the container" logic needs to happen at runtime. In Haskell, the container's possible values are enforced entirely by the type system at compile time.
To really appreciate this, you really have to be familiar with statically typed languages such as C++ or Java. In such languages, you have "nil" or "null" or "NULL" values to represent "nothing". Any time you have a pointer, you have to explicitly check if the pointer is valid; if you try to use it, and it happens to be null, the program will blow up at runtime, but not at compile time.
In Haskell, there is no generic null value. The value "Nothing" on its own belongs to a specific type, such as "Maybe String", and won't work with another such as "Maybe Integer". Thus when we want to use "fetchPage", we are forced into a situation where must make a choice based on whether there is a value or not (again, naive example):
crawlPageRecursively url =
do contents <- fetchPage url
case contents of
Just s -> map crawlPageRecursively (map (\body -> getLinks body) s)
Nothing -> putStrLn ("Failed to fetch " ++ url)
This was my attempt at "explain it like I'm five" Haskell as carefully as I could. The real world is somewhat more complex, but not awfully so. As you say, too often haskellers will get into "formal academic theory", even when, in my opinion, it's not necessary. Haskell becomes more elegant and beautiful if you study and know group theory, but most people don't, and it really just obscures the language for ordinary, mortal programmers who are trying to learn it.
As for monads, it's true that Maybe is a monad, but think of it as a convenience, in the sense that this lets it play well with the rest of the monad infrastructure. You can use, and even implement, Maybe without involving the monad aspect.
My best suggestion regarding monads is to just start using the language; as DanWaterworth points out, monads are pretty much inexplicable for beginners until one really needs to use them. Haskell actually lets you use some monads (like IO) without requiring any deep understanding of what they are. Case in point: The above examples actually use the IO monad, concealed by the "do" and the "<-" syntax. But because this syntactic sugar makes the language look like an imperative language, you can use this stuff without too much deep knowledge about just exactly how it works under the hood.
There's no way this Java thing will catch on. Why would anyone choose to deal with it?
print "Hello World"
Also, the example of hello world doesn't show much about complexity. After all, in Haskell it's just:
main = putStr "Hello World"e.g. loosely translating the idea of Maybe to C++ syntax (perhaps more familiar?) might give something resembling:
Maybe<int> x = Just<int>(30);
Maybe<int> y = Nothing<int>();
Given an arbitrary value of type Maybe<int> you have two cases to consider - either it is a "Nothing" which contains no further data, or it is a "Just<int>" which contains an int value.
You can think of the type Maybe<int> as being a "nullable int" type or perhaps a special collection of ints that can only contain 0 or 1 int value.
(beware: my knowledge of both haskell & c++ is not fantastic)
As for the syntax itself? It's called a tagged union. Just and Nothing are defined to be constructors for building values of type Maybe a. Just takes one argument (of any type) and Nothing takes no arguments.
Just "hello"
Nothing
data Maybe a = Nothing | Just a
Assume that a is the type String. Then Nothing is a value of type Maybe String but it's an empty box that contains no value. On the other hand Just "Hello, World!" is a box with the specified string inside.
Disclaimer: I'm not a Haskell expert. Feel free to correct me.
The definition states "For all types a, the data type Maybe a consists of 'Nothing' or 'Just a'", where the a in 'Just a' is a value of type a.
Nothing and Just are polymorphic constructors that create the values of any "Maybe a" type.
So if you take a concrete type, say String, you get a new concrete type called "Maybe String" whose values are Nothing, Just "Hello", Just "World", etc. For Maybe Int the values are similarly Nothing (polymorphism!) and Just 1, Just 2, etc.
Extra: 'a' can be any type so Maybe (Maybe Int) is a perfectly valid type, with values like Nothing, Just Nothing, and Just (Just 1). Something like that would be useful when retrieving a "possibly empty" value from a database: Nothing means it's not in the database, Just Nothing means it's there, but it's empty, and Just (Just x) means it's there and it has a value.
https://bitbucket.org/qznc/d-monad/src/1ec4ca36e46df1d0fce41...
foo (Just a) = bar a
foo (Just a) = bar a
foo Nothing = ...
The function "fromJust" which is equivalent to "getValue" is very rarely useful, and considered a smell: making that one of the primary ways to use your Maybe value is a very bad idea.
if (isNothing (m))
{ .. }
else
{ .. m.getValue() .. }
case m of
Nothing -> { .. }
Just val -> .. val ..
In Haskell, use of fromJust is considered a code smell, and is of course sometimes justified. But pretty rarely.
I actually did write the code that way the first time around. However, it ended up being a huge duplication of effort for a tiny amount of increased safety from type-checking. Literally, if I'm willing to move the checks of certain type-system-checkable properties to runtime this way, I can write 1/3 the actual lines of code.
The ideal would be to have data structures that are polymorphic over proofs of their properties, allowing the type-system to consider "unchecked AST", "generalized AST" and "specialized AST" as the instantiation of the same basic "AST" data type over three different proofs (or lack of proofs).
To restore nice, concise types, use a bunch of type synonyms.
While this is slightly cumbersome, I much prefer it over partiality.
Ideally, even this wouldn't be necessary, with structural records and variants that let you work with changing, precise types without having to declare a lot of duplicate types.
The other solution I'm thinking of in Scala (that doesn't involve Option[T].get, I mean) is to treat the properties I want "proven" as a set of methods over the data, built as a separate object or trait similar to how Scala represents type-class dictionaries. I can then write one data-structure that quantifies over the type of the proof-witness dictionary it stores as part of itself.
So when, for example, I want a fully-instantiated AST with no remaining "holes" to be filled in by static checking, I could write a function that only works on AST[FullyInstantiated]. Functions that don't care about the proof-witness are quantified over it.
It then takes a bunch of extra typing to construct the proof-witness instances, but when I'm doing that construction I will have the compiler statically checking that all types relied on by the witness are correct.
data Foo a = Bar a | Baz a | Qux a
data Foo' a = Bar a | Baz a
For one, this sounds like a perfect use case for OCaml's polymorphic variants[1]. I've always liked that particular feature. Honestly, most of the time, it seems like OCaml is the only language doing sub-typing correctly, especially in regards to type inference.
[1]: http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual006.ht...
Haskell does not have polymorphic variants, unfortunately. Happily, we can add them in as syntax sugar over multiparameter typeclasses[2]. The very first example in section 1.2 of this paper is particularly relevant here: they're showing how polymorphic variants make it easy to work with different kinds of ASTs. I don't think this is necessarily an immediately practical approach, but it's very interesting from a language design point of view.
[2]: http://guppy.eng.kagawa-u.ac.jp/~kagawa/PVH/PolymorphicVaria...
Your last example sounds like a prime case for using GADTs[3] (along with data kinds). You could write a type something like:
data Typed = Checked | Unchecked
data AST ∷ Typed → ★ where
Checked' ∷ Int → AST 'Checked
Unchecked' ∷ Int → AST 'Unchecked
Neutral ∷ Int → AST a
checked ∷ AST 'Checked → Int
checked (Checked' i) = i
[3]: http://www.haskell.org/ghc/docs/6.6/html/users_guide/gadt.ht...
This approach gives you relatively little syntactic overhead at the use site--the appropriate type is chosen based on the constructors you used. You also get nice type-safe pattern matching. I think it's a very good tool for this job. Perhaps you should consider using Haskell more one of these days ;).
Which I think I can actually do anyway just by declaring the polymorphism, or even using inclusion polymorphism on the witnesses to make Neutral a supertype of Checked and Unchecked (thus letting any function valid for Neutral ASTs operate trivially over both other kinds).
Polymorphic variants are indeed the ideal solution here, the problem being that those require either OCaml or a vastly improved subtyping system. I'm very slowly getting the logic worked out for the vastly improved subtyping system as a side-research project that's been going for years (but really got proper this past November as I started learning more of the logic behind type-theory and thus being able to reason much better about what I'm doing). For now, my own language would probably use structural-extensions and witness objects to do something like this, since it doesn't operate using the Vastly Improved Subtyping System.
At the very least, the GADT approach is not hard in Haskell. I don't see how it's any more difficult than the Scala approach. If anything, it's more natural: this is exactly the sort of use case GADTs were designed for.
The main advantage of using GADTs here is that they're simple and explicit. Sure, you could do the same thing with case classes, but it would be more awkward, and you'd really be rebuilding part of the same functionality yourself.
You don't really have to use data kinds in my example, but it makes the code nicer because you explicitly limit the types you can use as flags to 'Checked and 'Unchecked. You could have just made Checked and Unchecked empty types and stayed with normal kinds; the data kind approach is simply more elegant.
The GADT method also ensures that the pattern matching is always safe. It also preserves exhaustiveness checking, which is very nice. I'm not sure if the Scala approach can do this.
Another advantage over using witness objects (assuming I understood your idea correctly) is that you do not introduce anything new at the value level. 'Checked and 'Unchecked are only ever types, so the actual AST ends up being exactly the same as before just with a different type. I think this is a boon to clarity and simplicity. It also means that the use-site of the AST type doesn't change very much, if at all.
Really, the main idea is that this is very easy in Haskell, basically using a single simple abstraction: the GADT. Just being hidden behind a language extension does not magically make the concept any more complicated or difficult to use!
As an aside, if you want polymorphic variants, I don't see any reason not to use OCaml. It's a very nice language, and gets sub-typing right. All without sacrificing type inference.
Scala already has GADTs! http://lambdalog.seanseefried.com/posts/2011-11-22-gadts-in-... So yes, I use GADTs already.
> (+) <$> (Just 5)
Just (+5)
> Just (+5) <$> (Just 4)
ERROR ??? WHAT DOES THIS EVEN MEAN WHY IS THE FUNCTION
WRAPPED IN A JUST
No, that will never make sense. Sorry. Haskell is hard.
edit: oh, it's in a just value, I didn't notice that the first time I read it, for... some reason.
(+5) <$> (Just 4)
Where you're getting mixed up is in the distinction between Functors and Applicative Functors. You can think of an Applicative Functor as one which allows you to apply its contents to other things. One function which must be defined for all Applicative Functors is:
(<*>) :: f (a -> b) -> f a -> f b
Just (+5) <*> Just 4
>>> Just 9
(+5) 4
>>> 9
My intro to functional programming has been via Scala; not quite Haskell, but makes use of some of the same functional idioms, so a good place to get your feet wet in FP if you're tied to the JVM (yes, yes, there's also Clojure, prefer Scala's type system and easily grok-able syntax).
Maybe a better example than the common 'or nothing' would help in this case.
The payoff of the article is, I think, supposed to be:
getLine >>= readFile >>= putStrLn
Which looks great. But what I'd like to see is a longer explanation of why this is better than the alternatives (like simple function composition).
My goal was just to provide a gentle introduction.
There is a big problem that "Monads" can refer to the generalization and combinators that work with any Monad, or to specific Monad types and the style of composition that they choose to compose values together.
Monadic IO is a solution to combining referential transparency and effectful programs.
Moands in general is a solution to defining the same combinators over and over for each Monad.
That said, one thing I noticed is that there are two main "types" of monad tutorials. The first one is the the one taken by the OP and I call it the "category theory" approach. It tends to show what sorts of things you can do with monads and how they work mathematically but they kind of lack an explanation for why you should bother with monads in the first place.
The other approach for monads is the "monads as an useful interface" approach. One paper I would highly recommend in this category is the "awkward squad" paper by Simon Peyton Jones:
https://research.microsoft.com/en-us/um/people/simonpj/Paper...
Its an introduction to monads that helped me a lot and it also explains quite a bit about the history of monads.
Which lets me come back to your main point:
> why this is better than the alternatives (like simple function composition)
Because simple function composition doesn't work! While nowadays people like to point out that Haskell is a pure functional language, noone would have bothered with making a pure language (back then) if all you gained was all this headache with monads. The reason Haskell was pure in the first place was because its original goal was to be a lazily-evaluated language and that lazyness kind of forces you into pureness. You might think the order of evaluation of function arguments in C being unspecified is bad, but Haskell would be even worse since the order of evaluation for everything is unspecified and some things might not even end up being evaluated at all!
They ended up trying all sorts of approaches for adding effectful computation to Haskell and the most successful one was the monad one (the SPJ paper goes over this a bit). If you pay attention, the monad interface forces computations to be single threaded (you can't "branch out" monadic effects) and doesn't let you generally start or end an effectful computation wherever you want, meaning that whoever defined the monad you are using can control how effects are started or terminated via what functions they expose in the public interface (Maybe exposes the constructors directly so you can pattern match on them but IO makes it so `main` the only place you can start an IO computation)
Finally, this gets us back to notational problems. While monads make things really neat in the type level and as a platform for effects, it can end up really noisy in practice:
getNumber >>= (\a -> getNumber >>= (\b -> f a b)))
a <- getNumber
b <- getNumber
f a b
f <$> getNumber <*> getNumber
To wrap things up I would like to point out that most of the time monads and functors are an "advanced" technique that lets you take programs that you could already write before but write them in a neater way, with do notation, fmap, <$>, etc. (While its true that you can write generic programs that abstract over the monad interface, you only end up doing that if you are writing a control flow library or something even more advanced like a parser combinator). To give examples of what I am talking about, if you have functions that return null on error you can already get by with adding an if statements after every call (like you have to do in C) but monads let you omit the boilerplate if statements. A more advanced example I like is coroutines/generators (things that "yield"). You can write this sort of program in a normal language by manually inverting your control flow, storing state explicitly in stacks or other data structures. A continuation monad lets you write the code in a more natural way (and as a library, without needing to extend the base language with suport for a yield statement!)I think the biggest problem with monad tutorials is that it seems that everyone finally "gets" monads in a different way so the monad tutorials that get written lack motivation. For example, I finally "got" monads when I was working with a promise library in Javascript...
That said, one thing I noticed is that there are two main "types" of monad tutorials. The first one is the the one taken by the OP and I call it the "category theory" approach. It tends to show what sorts of things you can do with monads and how they work mathematically but they kind of lack an explanation for why you should bother with monads in the first place.
The other approach for monads is the "monads as an useful interface" approach. One paper I would highly recommend in this category is the "awkward squad" paper by Simon Peyton Jones:
https://research.microsoft.com/en-us/um/people/simonpj/Paper...
Its an introduction to monads that helped me a lot and it also explains quite a bit about the history of monads.
Which lets me come back to your main point:
> why this is better than the alternatives (like simple function composition)
Because simple function composition doesn't work! While nowadays people like to point out that Haskell is a pure functional language, noone would have bothered with making a pure language (back then) if all you gained was all this headache with monads. The reason Haskell was pure in the first place was because its original goal was to be a lazily-evaluated language and that lazyness kind of forces you into pureness. You might think the order of evaluation of function arguments in C being unspecified is bad, but Haskell would be even worse since the order of evaluation for everything is unspecified and some things might not even end up being evaluated at all!
They ended up trying all sorts of approaches for adding effectful computation to Haskell and the most successful one was the monad one (the SPJ paper goes over this a bit). If you pay attention, the monad interface forces computations to be single threaded (you can't "branch out" monadic effects) and doesn't let you generally start or end an effectful computation wherever you want, meaning that whoever defined the monad you are using can control how effects are started or terminated via what functions they expose in the public interface (Maybe exposes the constructors directly so you can pattern match on them but IO makes it so `main` the only place you can start an IO computation)
Finally, this gets us back to notational problems. While monads make things really neat in the type level and as a platform for effects, it can end up really noisy in practice:
getNumber >>= (\a -> getNumber >>= (\b -> f a b)))
a <- getNumber
b <- getNumber
f a b
f <$> getNumber <*> getNumber
To wrap things up I would like to point out that most of the time monads and functors are an "advanced" technique that lets you take programs that you could already write before but write them in a neater way, with do notation, fmap, <$>, etc. (While its true that you can write generic programs that abstract over the monad interface, you only end up doing that if you are writing a control flow library or something even more advanced like a parser combinator). To give examples of what I am talking about, if you have functions that return null on error you can already get by with adding an if statements after every call (like you have to do in C) but monads let you omit the boilerplate if statements. A more advanced example I like is coroutines/generators (things that "yield"). You can write this sort of program in a normal language by manually inverting your control flow, storing state explicitly in stacks or other data structures. A continuation monad lets you write the code in a more natural way (and as a library, without needing to extend the base language with suport for a yield statement!)
A simple example in the blog, it talks about Just 2 or Just a but don't explain what Just is. Also 'a' as a parameter for type is not explained. Leaving the readers to wonder whether a is argument to a function or it is a value since Just 2 and Just a are mentioned in the same section.
Also a lot of tutorials are afraid to draw parallel concepts from other languages that would be familiar with the readers, instead preferring to invent abstract definition to build things up. Most people learn by relating and inferring from familiar concepts.
E.g. Functor is just like template in C++ for constructing type. As a template it has placeholders to let the programmer to fill in to build a concrete type. These placeholders are the parameters to the functor. The programmer supplies a type as the parameter to the functor to construct a concrete type. E.g. "List a" is a functor which is called List and its parameter is a. "List int" would build a concrete type for values of list of int.
Maybe and Just are not a good introduction functor for beginners. Few other languages have a similar concept and people just roll their eyes when they learn what it is since it's not as useful in general.
List is a better introduction to functor. Most programmers have work with List and know what it is and its problems relating to its element type. Seeing "List int" people immediately know it's defining a list of int, and they know right the way what functor is and what it is for. Doing a couple more examples of List float, List string, and people will see why functor is very useful. May be adding Tree or some other functor operator like Eq or Show to how to have generic behaviors applying to any types.
No, a type variable is! For instance, if we have a data type:
data MyBox a = MyBox a
template <class T>
struct MyBox {
MyBox(T const &nv) : v(nv) {}
T const v;
};
MyBox :: * -> *
MyBox Int :: *
* -> *
fmap :: (a -> b) -> f a -> f b
fmap id = id
fmap (p . q) = (fmap p) . (fmap q)
instance Functor MyBox where
fmap f (MyBox v) = MyBox (f v)
I had a great success understanding Monad as a sequential program. The simplest way to write such a program would be just to chain elementary statements with the >> operator, however, to do any kind of control this way you'd need to rely on implicit state (think of programming in Assembler where you do branches based on implicit flag registers set by the previous instructions and the branch target itself is implicitly a new program).
So Monad is just the minimal improvement over this that allows control structures without need of implicit conventions. It achieves this with three simple additions to the basic sequential model: 1. add explicit results to the statements 2. allow a switch after each statement based on its results 3. add pure elementary statements (that don't do anything other than returning the value they have been created with) so we could transform results without modifying the context.
You can still do the simple chaining of statements in the Monad but whenever you need conditional/switch - you can do it explicitly with the >>= operator, whose argument is essentially a switch table, that assigns a new sequence of statements for each value.
You still need to figure out how do the List monad takes multiple branches in its switches simultaneously but it might be easier for a programmer to understand than container-value analogy.
http://web.cecs.pdx.edu/~antoy/Courses/TPFLP/lectures/MONADS...
fx
f <*> x
x >>= f
> the last conjures memories of PHP
As a non-PHP programmer I'm not sure what you mean.
EDIT: I may have skimmed a bit.
fromJust :: Maybe a -> a
fromJust (Just x) = x
fromJust Nothing = ??? -- What can we put here?
edit: In many cases there is a clear value that should be used in the Nothing case, suppose you have a Maybe Int which is the number of times a specific event happened in the last second. Clearly 0 is a good default and you can write a function (Maybe Int -> Int). There's a function I tend to use for such cases: (maybe :: b -> (a -> b) -> Maybe a -> b). In this case:
maybe 0 id :: Maybe Int -> IntWhat you can do, is pass a callback to a function that handles the case where you do have an "a" in the Maybe. And that's basically what fmap, <$>, and >>= do.
import Data.Maybe
let x = fromMaybe 1 (Just 2)
-- x == 2
let y = fromMaybe 1 Nothing
-- y = 1The tech field needs people that are both confident with words, fun and have a deep understanding of the inner details of things.
_why was such a writer, let's hope Adit (correct?) is another.
Regarding form vs. content, I think that the HN community enjoy discussing form as much as content. Most of the people here are interested in design or typography, things that more close to form than to content.
He openly claims to be a poor programmer, and as an artist... well, my contention is that he appeals to a very limited audience. That's not a criticism, simply a suggestion that while he may be valuable in an artistic sense to some people, he's not contributing to the "tech community" in a meaningful way. By which I simply mean that he should not be a yardstick by which we measure anyone.
Let him be himself. Let the rest of us be ourselves. Let that be good enough.
_why even said this himself:
> caller asks, “should i use hpricot or nokogiri?” if you're NOT me: use nokogiri. and if you're me: well cut it out, stop being me.
is one of the better gentle into to haskell guides.
I think it started attempting to be sort of similar to why's guide but ended up being a lot more straightforward although there are still some whimsical examples and pictures.
This guide is for understanding the theory behind monads, the use should not be something difficult to get if you have used the IO monad before.