News for hackers. Stuff that matters.
Re:Functor, Applicative, and Monad by mavelikara on Wednesday September 18, 2019 @01:36AM (#21002620)
> 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?

Re:Functor, Applicative, and Monad by bad_user on Wednesday September 18, 2019 @02:13AM (#21002756)
The point is that Monad, Applicative and Functor are well defined interfaces with laws (properties) you can count on.

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.

Re:Functor, Applicative, and Monad by mnsc on Wednesday September 18, 2019 @02:53AM (#21002933)
> 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?

Re:Functor, Applicative, and Monad by lalaithion on Wednesday September 18, 2019 @11:03AM (#21006138)
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...

Re:Functor, Applicative, and Monad by tsss on Wednesday September 18, 2019 @08:54AM (#21004847)
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.
Re:Functor, Applicative, and Monad by pdpi on Wednesday September 18, 2019 @08:10AM (#21004441)
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.
Re:Functor, Applicative, and Monad by 3PS on Wednesday September 18, 2019 @08:59PM (#21012178)
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.

Re:Functor, Applicative, and Monad by lmm on Wednesday September 18, 2019 @02:58AM (#21002957)
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.
Re:Functor, Applicative, and Monad by thsealienbstrds on Wednesday September 18, 2019 @07:01AM (#21003980)
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>?
Re:Functor, Applicative, and Monad by lmm on Wednesday September 18, 2019 @07:09AM (#21004020)
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.

Re:Functor, Applicative, and Monad by thsealienbstrds on Wednesday September 18, 2019 @10:15AM (#21005655)
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? :)
Re:Functor, Applicative, and Monad by lmm on Wednesday September 18, 2019 @10:55AM (#21006054)
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.

Re:Functor, Applicative, and Monad by thsealienbstrds on Wednesday September 18, 2019 @01:38PM (#21007842)
That's pretty cool! Too bad Rust doesn't support higher-kinded types...
Re:Functor, Applicative, and Monad by unhammer on Wednesday September 18, 2019 @08:48AM (#21004785)
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.

Re:Functor, Applicative, and Monad by lmm on Wednesday September 18, 2019 @09:04AM (#21004940)
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.

Re:Functor, Applicative, and Monad by unhammer on Friday September 20, 2019 @03:00AM (#21023898)
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

Re:Functor, Applicative, and Monad by unhammer on Thursday September 19, 2019 @01:50PM (#21018689)
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 :)
Re:Functor, Applicative, and Monad by chowells on Wednesday September 18, 2019 @02:18PM (#21008318)
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.

Re:Functor, Applicative, and Monad by mlevental on Monday September 23, 2019 @11:14AM (#21049646)
>The point is that Monad, Applicative and Functor are well defined interfaces with laws (properties) you can count on.

except you can't because you can have unlawful implementations.

Re:Functor, Applicative, and Monad by kccqzy on Wednesday September 18, 2019 @03:37AM (#21003122)
Your example, filterM has the type

    filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]
from this I can tell you conclusively what it does: it takes a monadic function that returns a Bool after performing some "action" as well as a list of values; it then performs this action on each element and look at whether the result is True or False; when True, keep it otherwise discard it.

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.

Re:Functor, Applicative, and Monad by dllthomas on Wednesday September 18, 2019 @01:08PM (#21007465)
"Conclusively" is probably a little strong. You're relying not just on the type, but also the name - the type alone isn't enough here, even without resorting to bottom, and even when requiring every piece be meaningfully used. For instance, with the same type we can write:

    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
Re:Functor, Applicative, and Monad by zeugmasyllepsis on Wednesday September 18, 2019 @01:50PM (#21007994)
Maybe a simpler way to illustrate this is two different functions built off of filter:

`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!

Re:Functor, Applicative, and Monad by dllthomas on Wednesday September 18, 2019 @03:46PM (#21009237)
Honestly, you could reasonably call either of those "filter" :D
Re:Functor, Applicative, and Monad by mavelikara on Wednesday September 18, 2019 @04:01PM (#21009434)
> I can tell you conclusively what it does: it takes a monadic function that returns a Bool after performing some "action" as well as a list of values; it then performs this action on each element and look at whether the result is True or False; when True, keep it otherwise discard it.

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  
This is a contrived example, but I think a large part of your guess on what filterM does comes from the word "filter" in its name. This isn't any different from other mainstream programing language, so it is not a ding on Haskell.
Re:Functor, Applicative, and Monad by kccqzy on Wednesday September 18, 2019 @11:37PM (#21013062)
That's actually what I meant: using both the name of the type to figure out what it does. I'm not claiming there's a single implementation given the type. Indeed I don't think that's possible in any signature that's not totally just type variables; here we have Bool and [] as base types so there are operations on them that the function can perform by baking in knowledge of these two types.
Re:Functor, Applicative, and Monad by TheAsprngHacker on Wednesday September 18, 2019 @01:39AM (#21002628)
To my understanding, although the behaviors of filterM, etc. differ depending on the monad instance, as long as the monad instances follow the laws, those functions like filterM have predictable behavior. It's a consequence of "theorems for free" / parametricity.
Re:Functor, Applicative, and Monad by willtim on Wednesday September 18, 2019 @02:16AM (#21002772)
Monads let you redefine what a statement is. This is very powerful and makes Haskell my favourite language for imperative programming. There's no need to modify the compiler for e.g. Async/Await, it can be a library. A Monad instance has a set of properties or laws that it obeys. This gives you a general understanding of what e.g. filterM will do, i.e apply an effectful filter function such that the effects are sequenced in the order of the input list.
Re:Functor, Applicative, and Monad by pyrale on Wednesday September 18, 2019 @02:15AM (#21002766)
You may not know how it is implemented, but because you have used other monads, you will know how to use it and how to compose it.