News for hackers. Stuff that matters.
Re:Do I really want to be using a language where memoize is ... by jrockway on Tuesday July 20, 2010 @08:14PM (#1533904)
The description you give of "type-level hackery" and "monad wizardry" leads me to believe that you don't really understand what's going on. This is dangerous, because you are expecting these things to be complicated, but they are actually so simple that you've probably already invented them in your own computer programs. The Haskell community merely gives names to ideas you already know about.

This isn't "smart people showing off about how clever they can be", it's people giving names to things that they use everyday.

The problem people have with monads is that the word "Monad" does not describe something they're used to dealing with. A computer programmer is used to concrete things like lists, trees, functions, compilers; things you could hold in your hand (or at least draw on a whiteboard), poke at, and observe.

Monads can't be understood in this way, because they are not anything concrete; "Monad" is a word to describe concrete things that, individually, are all very different. It's like explaining the concept of "Green" to someone by showing them an apple, a tennis ball, and some grass clippings. They will never understand "Green", because you can't understand what Green is by seeing three examples of them. Green is a color, not some sort of weird tennis-ball-apple-grass-clipping hybrid.

Monads are the same way. List is a Monad. Reader is a Monad. State is a Monad. But when you look at these things and try to generalize, you might not see the parts that are the same, because the parts that are the same that make them all monads are hard to see.

I think the hard part is that you hear about what defines a monad ("return" and "bind" or "return", "fmap", and "join"), and don't see how some dual or triple like that helps you write computer programs. Each set of functions is so different from the other sets that the fact that they are all called "return" and "bind" doesn't seem to matter. And that's exactly right; at some level, it doesn't matter.

You use a List as a monad to combine computations that return multiple values, and you use Cont to write your programs in a continuation-passing style. Very different. Nothing similar at all, really. On the concrete level.

The similarity does matter at a higher level, though; noticing similarities means you can write parts of your program in advance, and just tweak those parts for each specific case.

An example is liftM2; it abstracts away the tedium of using a calling a two-arg function with monad-like semantics. If there were no similarities between List and Maybe, you'd have to write something like this:

   liftList2 f xs ys = concat $ (\x ->
                                 concat $ (\y -> [f x y])
                                          `map` ys)
                                 `map` xs

   -- this doesn't compile; I want to use more descriptive words than the Data.Maybe API does :)
   liftMaybe2 f x y = if has x then extract x -> \x'
                          if has y then extract y -> \y'
                                           makeMaybe f x' y'
                          else Nothing
                      else Nothing
(Here's how to use the functions, in case you aren't sure:

   liftList2 (,) [1,2] [3,4]      ==> [(1,3),(1,4),(2,3),(2,4)]
   liftList2 (,) [] [1..infinity] ==> []

   liftMaybe2 (,) (Just 10) (Just 20)     ==> Just (10, 20)
   liftMaybe2 (,) Nothing (Just "oh hai") ==> Nothing
.)

These seem very similar. There is the same sort of nesting in both structures, we seem to be saying the same thing twice in both functions. We seem to be applying functions to values "inside" each of these things.

Maybe we can abstract those things away somehow, and make the two functions look a little more similar:

    newList x = [x]
    fmapList xs f = f `map` xs --
    joinList xs = concat xs

    liftList2 f xs ys = joinList $ fmapList xs $ \x ->
                        joinList $ fmapList ys $ \y ->
                        newList $ f x y
    -- hey, the code looks nicer already!

    newMaybe x = Just x
    fmapMaybe Nothing _ = Nothing
    fmapMaybe (Just x) f = Just $ f x
    joinMaybe Nothing = Nothing
    joinMaybe (Just x) = x

    liftMaybe2 f x y = joinMaybe $ fmapMaybe x $ \x' ->
                       joinMaybe $ fmapMaybe y $ \y' ->
                       newMaybe $ f x' y'
Now that we've given List and Maybe some common terminology, it's very hard not to see how these lift2 functions are nearly identical. We just need to do some refactoring, and then we can use the same definition for both!

    class Monad m where
        new :: a -> m a
        fmap :: m a -> (a -> b) -> m b
        join :: m (m a) -> m a

    instance Monad [] where -- haskell98 spells List as []
        new  = newList
        fmap = fmapList
        join = joinList

    instance Monad Maybe where
        new  = newMaybe
        fmap = fmapMaybe
        join = joinMaybe

    liftM2 f x y = join $ fmap x $ \x' ->
                   join $ fmap y $ \y' ->
                   new $ f x' y'
And there you go, that's what a Monad is. It's just refactoring, so we have less code to maintain! That's what any programmer would do, not just super-smart PhDs. You do the same thing every day!
Re:Do I really want to be using a language where memoize is ... by skybrian on Wednesday July 21, 2010 @12:42AM (#1534361)
Agreed that abstraction is itself the problem - very abstract things are more difficult to understand than concrete things, because there's nothing to grab onto.

I know you're trying, but you're going to lose the beginner as soon as you get to the code example - it's just too terse and foreign. Remember that people who don't know monads also don't understand Haskell very well, so they need to know your intentions before trying to read the code. You have to explain this in English.

First you'd have to explain what the comma function does (creates a pair), what liftList2 does (takes the cartesian product and applies an operator to each pair - oops, that assumes the reader knows what cartesian product means!) and what the liftMaybe2 does (applies a binary operator if both arguments are not null - er, I mean Nothing).

In Java all these methods would have JavaDoc, so you have some clue what the author intends before reading the code. I think readable Haskell would probably need five times as many lines of comments as actual code since so many functions are one-liners.

It's much like math: if you really want to explain things so a beginner will get it, you need half a page of text and maybe some diagrams per equation.

Personally I like this Monad tutorial. We can at least say that a Monad is more like a macro syntax than like a data structure and people will get the vague idea: http://kawagner.blogspot.com/2007/02/understanding-monads-fo...

Re:Do I really want to be using a language where memoize is ... by jrockway on Wednesday July 21, 2010 @01:49AM (#1534464)
Agreed. I didn't want to spend too much time on this, since sigfpe already beat me to "you invented mondas" by like 8 years :)

I think the key point I missed is explaining why a sequence like this is join . fmap . return . f. Mapping over a list makes sense, but would would I pick that abstraction for null/not null? Why "join"? Why not if/then?

But on the other hand, I think the main idea, "it's just programming", sticks.

One day, a Haskell programmer was writing some code. He wrote code that felt similar, and he looked for the similarities. He noticed, "hey, these are both containers", and "oh look, i'm applying a function inside the container", and "hmm, i always have to remove a level of nesting". Some thinking later, and the return/fmap/join abstraction appeared, and with even more thinking, the monad.

This is how programmers should always approach programming. Not just "genius PhD students". Just because some PHP programmer doesn't do this much thinking for his login page, doesn't mean you shouldn't.

Re:Do I really want to be using a language where memoize is ... by greenlblue on Wednesday July 21, 2010 @09:39AM (#1535130)
I have a degree in mathematics so don't try to explain to me what abstract is. I'm no stranger to chasing diagrams and figuring out if something is a natural transformation. The problem is that haskell overlays all this heavy duty math on top of state computations and hopes that by throwing enough examples at the reader, kinda like you did, the reader will figure out that "return", "join", etc. are very special kinds of natural transformations. The fact remains that you are using categorical constructs to program and to me this is just a horrible idea because it confounds a whole bunch of ideas and is basically using a hammer to kill a fly. Just because every concept in programming can be coerced into being a monad doesn't mean it should and that's exactly what haskell does and don't even get me started on arrows. Semantic distinctions between concepts in programming are a good thing because they show beginners boundaries and allow them to apply the concept and gain mastery. There is such a thing as too much abstraction when you are trying to be practical because after all everything in mathematics is basically some kind of category but when you are integrating a function you are not thinking of limits and colimits. Haskell doesn't have many semantic distinctions between it's underlying concepts. Everything is a function, a type or a type constructor and that's it. Sure it's theoretically very beautiful but it's not very practical. There is no way a language with such constructs is going to gain any kind of followers other than people who already have a PhD and eat natural transformations for breakfast.
Re:Do I really want to be using a language where memoize is ... by jrockway on Wednesday July 21, 2010 @01:10PM (#1535781)
You didn't read my post. Monads are just refactoring with a funny name. That's it.

Unless the deepest abstraction you are capable of understanding is cut-n-paste, this is not particularly far-fetched. I don't have a PhD in math, and I don't have any trouble writing "real applications" in Haskell.

Re:Do I really want to be using a language where memoize is ... by greenlblue on Wednesday July 21, 2010 @03:30PM (#1536263)
Good for you.