Hacker News Reader

Comment by mnsc | Hacker News Reader

> 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.

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?

View on HN

This is mostly useful for reusable boilerplate. For example, if I have a list and want to map over it with a function, I can call normal `map`. But if I want to map over it with a function that doesn't return a normal value, I can get something weird. With promise, for example, I might end up with a list of promises, where what I want is a promise containing a list. If I didn't have monads, I would have to write a function that manually took each value out of the list, awaited it, and put that value into a new list that will be returned from that function.

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...

Here is a quick real world example: You are working on a compiler, type checking statements one by one. You come across a function call and to type check that, you first need to type check the argument expressions to get their types and abort the whole thing if they don't make sense. You use a `Maybe` type to model the result of type checking the argument expressions: The result is either `Nothing` (in case of failure) or `Type` (in case of success). `Maybe` is kinda similar to a nullable type in other languages. In Java you would now make an if-statement for each argument and check that the result of type checking wasn't null; Very annoying. Luckily for you, `Maybe` is an `Applicative` so you can just use the `traverse` function to do this for you automatically: The argument iteration will stop automatically and return `Nothing` if any single argument type check returns `Nothing`. You are happy with your compiler, but your colleague says it sucks, because they can never know what went wrong. To fix this you replace `Maybe` with the `Either` type. Instead of returning `Nothing` in case of failure you can now return an `Error`. Dreadfully you set about to refactor your whole codebase, only to realize that `Either` is also an `Applicative` and has the `traverse` function. Everything works just as before. Your colleague still isn't satisfied: Your compiler always aborts at the first error but they would like to see all the errors in the input at once. Again, you replace `Either` with the `Validation` type, which accumulates errors in independent computations. `Validation` is also an `Applicative` and everything still works as before. You just got your error accumulation for free without large refactoring.

Map-reduce is effectively the fruit of realising that, as long as your processing can be described as a combination of Functor (map) and Monoid (reduce) operations, then you can trivially parallelise your computation by letting the implementation of `map` and `reduce` handle all the parallelism for you.

A question. Does map-reduce assume a commutative monoid, or does it need to order the output of map?

Edit: seems like it's the latter.

traverse (for sequence-like structures) or cataM (for tree-like structures). They let you walk a data structure with an applicative or monadic operation and compose the monadicity in the way that obviously makes sense.

Thanks for this short explanation. The benefits of these patterns were not clear to me just from reading the article. Questiob: is the idea always to think in terms of types as groups of values + some operations on those types such that <insert properties about resulting groups here>?

It's important not to think of types as just sets of values, because types are more semantic than that; two quite different types might have the same underlying values but they're different types because you use them to mean something different. A typeclass is one or two levels higher than a type, and yes, for a type to conform to a typeclass usually means that that type supports particular operations in a way that conforms to certain laws (e.g. a type `a` will have an instance of the monoid typeclass if there is a definition of `+` for `a` that is associative and a value `0` of type `a` that behaves as left and right identity wrt this `+`).

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.

Seems similar to type traits in Rust. I skimmed through "Category Theory for Programmers" and it's mentioned this thing is mainly about composition. Composing functions? So you've got a trait (say Functor) that is meant for functions. You know something about functions that have this trait, so you can exploit that knowledge to create compositions of those functions. So then in theory you can write algorithms with as input functions implementing some trait? I'm trying to get the 'aha' moment here, I guess then that there exist many useful such algorithms? Or did I just completely miss the mark? :)

Rust traits are pretty much typeclasses. I don't agree with "this thing is mainly about composition" so I don't know what to tell you there. Functor isn't meant for functions, it's meant for types, or rather type constructors (types of kind * -> *).

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.

That's pretty cool! Too bad Rust doesn't support higher-kinded types...

The simplest but still most versatile one is probably fmap (also knowns as <$>) which lets you use a function on whatever is inside the burrito:

(+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.

No. If you attempt to write monad-generic code using the burrito analogy you will inevitably write broken code, causing serious problems for other users and/or your future self.

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.

Nah, like any bad analogy, it can be stretched :) Once you've moved past the "lies-to-children[1]" version, you can ascend to the real meat of the burrito: https://blog.plover.com/prog/burritos.html

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] https://en.wikipedia.org/wiki/Lie-to-children

too late to edit, but that should look like

    (+1) <$> Just 1 → Just 2 

    (+1) <$> getIntFromThatUserThatOnlyTypes1 → IO 2

    (+1) <$> [1,2] → [2, 3]

    ((+1) <$> ask) 1 → 2

and

    take <$> Just 2 <*> Just "abc" → Just "ab"

as if the operator line noise wasn't bad enough already :)

Sure. Let's look at alterF for the Map type in the containers library:

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)

Note that it works for all instances of Functor. Trivial choices allow this to reduce to simple things like insert or lookup:

    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)

But those aren't really compelling examples because they just reproduce simpler functionality. It starts to pay off when you start compounding requirements, though. What if you need to insert a value and return the previous one, if it existed?

    insertAndReturnOld :: Ord k => k -> a -> Map k a -> (Maybe c, Map k a)
    insertAndReturnOld key val map = alterF (\old -> (old, Just val)) key map

OK, those are all fine and good, but they're still barely scratching the surface. What if you had problem where when you had a value to insert and there was a previous value at the same key, it was ambiguous which you should use? And let's say the structure of the problem provides interdepencies which restrict the options such that you can't just stack up a list of every possibility for each key. So ideally, you'd like a way to model "insert this value, but if something was already present at this key, give me both possible maps back". Turns out alterF can do that!

    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

Fun facts with that one - thanks to using Functor, it only traverses the tree once, whether it returns one or two results. And thanks to Map being a persistent data type, returning two results only takes O(log n) space more than returning one.

(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.

Reply on news.ycombinator.com