6 ms·

"A functor instance lifts a function over some structure to affect only the values within. An applicative (a monoidal functor) leverages a structure and functio

"A functor instance lifts a function over some structure to affect only the values within. An applicative (a monoidal functor) leverages a structure and function together while lifting the function over structure. A monad (an applicative functor) creates new structure whilst in the process of lifting a function over existing structure." I think https://xkcd.com/483/ https://xkcd.com/483/ should apply to programming languages too. ;-) But seriously, can someone put this in English? Is it really more complicated than "apply a function to every object in a list"?

yingw787 7y ago
I actually wrote a monad tutorial last year: https://bytes.yingw787.com/posts/2019/12/06/monads/ https://bytes.yingw787.com/posts/2019/12/06/monads/ After reading about monads...honestly no, there is no way to simplify it. Without understanding the type system, it’s alien.
TheAsprngHacker 7y ago
But "apply a function to every object in a list" isn't the definition that the author is getting at! Most programmers probably know "map" as being an operation takes a function and a list and returns a list of the results of the function applied to each element of the input list. However, the "map" operation can be generalized to generic types other than lists, where it has different behavior but shares certain properties. In functional programming, the idea of a functor gives a name to this pattern. The idea is that if you have some generic type `T a` covariant in `a`, there is a function `map : (a -> b) -> T a -> T b` that can "lift" every function `f : a -> b` into a function `map f : T a -> T b`. The lifting operation respects function composition and identity. However, what if the function has multiple arguments, e.g. `f : a -> (b -> c)`? Then, `map f : T a -> T (b -> c)` An applicative functor lets you convert that `T (b -> c)` into a `T b -> T c`. So, with applicative functors, you can individually map each parameter of a multi-parameter function. A monad is a functor that can be "flattened." It has an operation `join : T (T a) -> T a`, as well as an operation `return : a -> T a`. A monad can be seen as generalizing the idea of flattening a list, or generalizing async/await.
- greydius 7y ago
  Small correction: Join should be T (T a) -> T a
  - TheAsprngHacker 7y ago
    Oops, thanks.
- anko 7y ago
  I really like your description. One thing i don't understand though, is why generalising these operations is considered a good thing? In my day to day I spend a bit of time writing functional code, and a lot of time reviewing it, and when you generalise in this manner it hides a lot of the details of the algorithmic complexity. Is this operation happening in a future? or is on a list? You could argue that the type signature will let you know, but quite often it's inferred. Suddenly I find myself needing an IDE just to do code reviews. People make arguments about naming variables and suddenly we're back to using hungarian notation. I also find it's easy to make mistakes - you do a flatmap instead of a map and the Nones just vanish. Or you're composing so many generic functions that the intent of the code just disappears. I guess i just wanted to see if it's just me.
  - hopia 7y ago
    You can write your own definitions for your types for instances of Functor, Applicative etc. explicitly. Are you worried about the performance when you refer to algorithmic complexity, or what exactly?
    - anko 7y ago
      Well performance is certainly the main factor, but it's really about the Big O's of a function. https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation
  - rovolo 7y ago
    > is why generalising these operations is considered a good thing? > Is this operation happening in a future? or is on a list? You could argue that the type signature will let you know, but quite often it's inferred. 1) You are generalizing the input of a function to multiple types. Many of the functions you'd write wouldn't care whether you're using a List or a Future, they would accept either. It's just like declaring your Java method to take a Collection instead of an ArrayList. 2) You are getting more specific in the output of the function. If you write `filter`, it would be nice to get a `LinkedList` back if you pass in a `LinkedList`. With more common type systems, the best you'll be able to do writing the function once is a return type of `Collection` or `Iterable`. Your method may perform horribly if a LinkedList is passed in instead of an ArrayList. If your operation really depends on a specific behavior the Functor doesn't specify, you should be using a different type than Functor.
gizmo686 7y ago
From the official documentation: > Functors: uniform action over a parameterized type, generalizing the map function on lists. > Is it really more complicated than "apply a function to every object in a list"? It is defined for more data structures then just a lists. Other than that, not at all. As far as I can tell, the only reason Haskell has both map and fmap is because "map" came first. When applied to a list, fmap and map are identical.
wk_end 7y ago
Well, in the case of functors - yes, that's basically it. Except it's also "apply a function to every object in a tree", "apply a function to an optional object (if it's there)", and so on (there's a list of ones built into Haskell's standard library here [1]). And then the real kicker is - very often stuff can use that general functor idea ("apply a function to whatever objects are inside this wrapping object, whatever it is") instead of being written against a specific, concrete kind of thing. And then you can use that stuff in all kinds of unexpected places, and combine it with other stuff written in the same way, and it all composes together and works harmoniously. [1] https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#t:Functor https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelu...
- nybble41 7y ago
  I think it's important to point out that Functor, Applicative, etc. are not only about "containers" like lists and trees which hold a specific set of concrete values but also things like IO actions ("compose this pure function with the result of the readLine action, producing a new action") or even regular functions (where the map operation is just function composition). When other languages import the concept they unfortunately often specialise it to only work on containers.
bontaq 7y ago
For things like this I recommend going to wikipedia and looking up "Functor" -- there's some weird dislike of category theory terms but we're all fine with terms like "singleton" or "Factory" You'll see the definition and be like, "shit that's just a map." We sell each other a bit short. Likewise for applicative, monoid, monad -- they're mathematically pretty clear and if you squint while assuming a list is a category, you can probably read most of the definitions and get it. functor -> equivalent of map for lists monoid -> equivalent of having an identity ([]) and a join (a.concat) for lists applicative -> equivalent of turning one element into a list monad -> equivalent of unwrappering list items, applying a function to each, and rewrapping it This is just for lists, but the terms are more powerful than that and have many variations. The nice thing is because it's universal. You don't have to wonder, "have I done this pattern right," because you test the laws for them. It might also help, for some of the laws, to remember identity and associativity as like from multiplication -- ie 1 * 9 = 9, 3 * 2 = 2 * 3
- TheAsprngHacker 7y ago
  > applicative -> equivalent of turning one element into a list This is only one part of the definition of an applicative. Applicatives must also preserve the monoidal operation (product). That is, there is a function `pair : f a -> f b -> f (a * b)`. Then, you can map functions of multiple arguments by turning `(a * b) -> c` into `f (a * b) -> f c` via `map` and passing it the result of the applicative `pair` operation. > monad -> equivalent of unwrappering list items, applying a function to each, and rewrapping it I'm not sure how precise or accurate this definition is. I'd say that a monad is about collapsing multiple layers of a functor into one layer. > This is just for lists, but the terms are more powerful than that and have many variations. The nice thing is because it's universal. You don't have to wonder, "have I done this pattern right," because you test the laws for them. It might also help, for some of the laws, to remember identity and associativity as like from multiplication -- ie 1 * 9 = 9, 3 * 2 = 2 * 3 Yup, I agree that this is a benefit of generalizing these operations based on their common structure.
6gvONxR4sf7o 7y ago
> Is it really more complicated than "apply a function to every object in a list"? Not more complicated, but yes more general. Perhaps "apply a function to every object in a data structure," even when that data structure can be kind of a abstract.
elbear 7y ago
One thing that could help you understand is that Haskell has many types which act kind of like containers of primitive values. One example is `Maybe a` which has a value `Just a`. `a` can have any type, including `String`, `Int`, `Float`, etc. But a function that accepts a `String` can't take `Just String` as an argument. This is the problem that `Functor` solves. It applies your function to the value inside the container. `Applicative` applies a function that takes two arguments to the values inside two containers. For example, you have the function: `<> :: String -> String -> String` and you apply it to two `Just String` values, like this: ghci> liftA2 (<>) (Just "hello") (Just " world") Just "hello world"

yingw787 7y ago

I actually wrote a monad tutorial last year: https://bytes.yingw787.com/posts/2019/12/06/monads/ https://bytes.yingw787.com/posts/2019/12/06/monads/ After reading about monads...honestly no, there is no way to simplify it. Without understanding the type system, it’s alien.

TheAsprngHacker 7y ago

But "apply a function to every object in a list" isn't the definition that the author is getting at! Most programmers probably know "map" as being an operation takes a function and a list and returns a list of the results of the function applied to each element of the input list. However, the "map" operation can be generalized to generic types other than lists, where it has different behavior but shares certain properties. In functional programming, the idea of a functor gives a name to this pattern. The idea is that if you have some generic type `T a` covariant in `a`, there is a function `map : (a -> b) -> T a -> T b` that can "lift" every function `f : a -> b` into a function `map f : T a -> T b`. The lifting operation respects function composition and identity. However, what if the function has multiple arguments, e.g. `f : a -> (b -> c)`? Then, `map f : T a -> T (b -> c)` An applicative functor lets you convert that `T (b -> c)` into a `T b -> T c`. So, with applicative functors, you can individually map each parameter of a multi-parameter function. A monad is a functor that can be "flattened." It has an operation `join : T (T a) -> T a`, as well as an operation `return : a -> T a`. A monad can be seen as generalizing the idea of flattening a list, or generalizing async/await.

greydius 7y ago
Small correction: Join should be T (T a) -> T a
- TheAsprngHacker 7y ago
  Oops, thanks.
anko 7y ago
I really like your description. One thing i don't understand though, is why generalising these operations is considered a good thing? In my day to day I spend a bit of time writing functional code, and a lot of time reviewing it, and when you generalise in this manner it hides a lot of the details of the algorithmic complexity. Is this operation happening in a future? or is on a list? You could argue that the type signature will let you know, but quite often it's inferred. Suddenly I find myself needing an IDE just to do code reviews. People make arguments about naming variables and suddenly we're back to using hungarian notation. I also find it's easy to make mistakes - you do a flatmap instead of a map and the Nones just vanish. Or you're composing so many generic functions that the intent of the code just disappears. I guess i just wanted to see if it's just me.
- hopia 7y ago
  You can write your own definitions for your types for instances of Functor, Applicative etc. explicitly. Are you worried about the performance when you refer to algorithmic complexity, or what exactly?
  - anko 7y ago
    Well performance is certainly the main factor, but it's really about the Big O's of a function. https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation
- rovolo 7y ago
  > is why generalising these operations is considered a good thing? > Is this operation happening in a future? or is on a list? You could argue that the type signature will let you know, but quite often it's inferred. 1) You are generalizing the input of a function to multiple types. Many of the functions you'd write wouldn't care whether you're using a List or a Future, they would accept either. It's just like declaring your Java method to take a Collection instead of an ArrayList. 2) You are getting more specific in the output of the function. If you write `filter`, it would be nice to get a `LinkedList` back if you pass in a `LinkedList`. With more common type systems, the best you'll be able to do writing the function once is a return type of `Collection` or `Iterable`. Your method may perform horribly if a LinkedList is passed in instead of an ArrayList. If your operation really depends on a specific behavior the Functor doesn't specify, you should be using a different type than Functor.

gizmo686 7y ago

From the official documentation: > Functors: uniform action over a parameterized type, generalizing the map function on lists. > Is it really more complicated than "apply a function to every object in a list"? It is defined for more data structures then just a lists. Other than that, not at all. As far as I can tell, the only reason Haskell has both map and fmap is because "map" came first. When applied to a list, fmap and map are identical.

wk_end 7y ago

Well, in the case of functors - yes, that's basically it. Except it's also "apply a function to every object in a tree", "apply a function to an optional object (if it's there)", and so on (there's a list of ones built into Haskell's standard library here [1]). And then the real kicker is - very often stuff can use that general functor idea ("apply a function to whatever objects are inside this wrapping object, whatever it is") instead of being written against a specific, concrete kind of thing. And then you can use that stuff in all kinds of unexpected places, and combine it with other stuff written in the same way, and it all composes together and works harmoniously. [1] https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#t:Functor https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelu...

nybble41 7y ago
I think it's important to point out that Functor, Applicative, etc. are not only about "containers" like lists and trees which hold a specific set of concrete values but also things like IO actions ("compose this pure function with the result of the readLine action, producing a new action") or even regular functions (where the map operation is just function composition). When other languages import the concept they unfortunately often specialise it to only work on containers.

bontaq 7y ago

For things like this I recommend going to wikipedia and looking up "Functor" -- there's some weird dislike of category theory terms but we're all fine with terms like "singleton" or "Factory" You'll see the definition and be like, "shit that's just a map." We sell each other a bit short. Likewise for applicative, monoid, monad -- they're mathematically pretty clear and if you squint while assuming a list is a category, you can probably read most of the definitions and get it. functor -> equivalent of map for lists monoid -> equivalent of having an identity ([]) and a join (a.concat) for lists applicative -> equivalent of turning one element into a list monad -> equivalent of unwrappering list items, applying a function to each, and rewrapping it This is just for lists, but the terms are more powerful than that and have many variations. The nice thing is because it's universal. You don't have to wonder, "have I done this pattern right," because you test the laws for them. It might also help, for some of the laws, to remember identity and associativity as like from multiplication -- ie 1 * 9 = 9, 3 * 2 = 2 * 3

TheAsprngHacker 7y ago
> applicative -> equivalent of turning one element into a list This is only one part of the definition of an applicative. Applicatives must also preserve the monoidal operation (product). That is, there is a function `pair : f a -> f b -> f (a * b)`. Then, you can map functions of multiple arguments by turning `(a * b) -> c` into `f (a * b) -> f c` via `map` and passing it the result of the applicative `pair` operation. > monad -> equivalent of unwrappering list items, applying a function to each, and rewrapping it I'm not sure how precise or accurate this definition is. I'd say that a monad is about collapsing multiple layers of a functor into one layer. > This is just for lists, but the terms are more powerful than that and have many variations. The nice thing is because it's universal. You don't have to wonder, "have I done this pattern right," because you test the laws for them. It might also help, for some of the laws, to remember identity and associativity as like from multiplication -- ie 1 * 9 = 9, 3 * 2 = 2 * 3 Yup, I agree that this is a benefit of generalizing these operations based on their common structure.

6gvONxR4sf7o 7y ago

> Is it really more complicated than "apply a function to every object in a list"? Not more complicated, but yes more general. Perhaps "apply a function to every object in a data structure," even when that data structure can be kind of a abstract.

elbear 7y ago

One thing that could help you understand is that Haskell has many types which act kind of like containers of primitive values. One example is `Maybe a` which has a value `Just a`. `a` can have any type, including `String`, `Int`, `Float`, etc. But a function that accepts a `String` can't take `Just String` as an argument. This is the problem that `Functor` solves. It applies your function to the value inside the container. `Applicative` applies a function that takes two arguments to the values inside two containers. For example, you have the function: `<> :: String -> String -> String` and you apply it to two `Just String` values, like this: ghci> liftA2 (<>) (Just "hello") (Just " world") Just "hello world"