It's really just that. A monad is really just a type that admits lawful definitions of map (so it's a functor), pure and ap (so it's an applicative functor) and bind (or flatmap, though depending on your language this may be too powerful compared to a classical bind, cf. Scala). There's a lot of cool stuff that falls out of that, but if you understand "given a value in some context (of type m a, say) and a function that lifts values into that context (possibly at a different type, i.e., a -> m b), I can produce a value in the same context (m b, again, possibly at a different type)", there's not much else to look into. The functor, applicative, and monad laws dictate some of the operational characteristics of such definitions on a particular type, but that's really only relevant if you're making your own.
Lifting is just a fancy word for (in this specific case, anyway) taking a concrete value and putting it some kind of computational context.
I have a value 1 :: Int. There are a lot of contexts I can put that concrete value in! That is, I can make lots of values of type m Int that represent different views on the same value.
Let's start by looking at how functors (types that admit a lawful definition of map) lift values.
map :: Functor f => (a -> b) -> (f a -> f b) -- equivalently (and more usually) (a -> b) -> f a -> f b
Normally, this is explained by saying "given a function a -> b and a value of type f a for some functor f, apply the function on each a in f a and give me the result wrapped up in f". Another way of explaining it (which I've written the type for preferentially) is "given a function a -> b, give me a function f a -> f b. We're lifting the entire function into whatever our functorial context is.
Examples:
1 :: Int
map (+1) :: Functor f => f Int -> f Int
map show :: Functor f => f Int -> f String
Just 1 :: Maybe Int
map (+1) (Just 1) = Just 2 :: Maybe Int
map show (Just 1) = Just "1" :: Maybe String
[1] :: [Int]
map (+1) [1] = [2] :: [Int]
map show [1] = ["1"] :: [String]
Skipping directly up to monads, we really just need pure :: Monadm=> a -> m a (a function which does nothing but put a value into a monadic [technically applicative] context) and bind :: Monad m => m a -> (a -> m b) -> m b. To keep it simple, we'll just reproduce map.
-- We compose our function with pure to get their types into a shape that bind will understand
incM :: Monad m => (Int -> Int) -> (Int -> m Int)
incM = pure . (+1)
showM :: Monad m => (Int -> String) -> (Int -> m String)
showM = pure . show
-- worth noting, Just 1 and [1] are both the same as pure 1 :: f Int with f fixed at Maybe and [], respectively
bind (Just 1) incM = Just 2
bind (Just 1) showM = Just "1"
bind [1] incM = [2]
bind [1] showM = ["1"]
bind (bind (Just 1) incM) showM = Just "2"
-- bind (Just 2) showM
bind (bind [1,2,3] incM) showM = ["2", "3", "4"]
-- bind [2,3,4] showM
So you can see that this is a way of getting a value "out of" some context (like pulling the value of a Maybe or all the values out of a list), doing some sort of transformation on it, then wrapping it back up in the initial context; it also lets you chain these transformations, finally wrapping everything back up when you're done. flatmap is called that because bind for the list monad is exactly "map a function over this list and then flatten the list".
nah, they just pop up in a lot of contexts like futures/promises, errors, optionality, etc.. there's also a couple of neat tricks where you take a functor that represents a set of operations you'd like to provide and use an automatic construction to create a (free) monad out of it, thereby getting an interpreter for your DSL with no extra work.
I'll attempt a more thorough explanation, let me know if this makes any sense.
so I've got a type that represents some operations I want to provide:
data Op = Plus IntInt | Mul IntInt
I can turn that into a Functor by swapping the concrete values for a type variable:
data Opa= Plus a a | Mul a a
I'm doing this because I want to be able to compose these operations together - I should be able to freely sequence them however I like. so I can pass Op values in for a and nest them as deep as I like. I can also write an interpreter for Op values by breaking it down by cases and doing the obvious thing:
eval :: OP Int ->Int
eval (Plus a b) = a + b
eval (Mul a b) = a * b
I give that type the obvious, dumb Functor instance, nothing special (exercise left for the reader). then, I can pass Op to a function (liftFree) that turns it into a monad:
liftFree :: Functorf=> f a -> Free f a
(I'm going to skip the actual definition of Free as it's just a type out of the standard library)
so I can use liftFree to turn the basic operations on Op (Plus and Mul) into monadic operations that are allowed to use do-notation:
plus :: a -> a -> Free Op a
plus ab= liftFree (Plus a b)
mul :: a -> a -> Free Op a
mul ab= lift Free(Mul a b)
calculation :: Free Op Intcalculation=do
a <- plus 23
b <- mul a 5
plus a b
foldFree then allows me to pass it an interpreter function that evaluates my Op and turn it back into a regular value (like the obvious one I mentioned previously).
foldFree :: Functor f => (f r -> r) -> Free f r ->r
(foldFree eval calculation) :: Int
BUT because I can pass any interpreter I want, I've decoupled evaluation from the definition of the actions I'd like to take. so I could, instead of using an interpreter that calculated the final value, pass in one that pretty-printed it instead, or does a dry-run, etc..
prettyPrint :: Op String->String
foldFree prettyPrint (fmap show calculation)
so I can define actions that do a bunch of crazy IO stuff when called with a regular interpreter and run them instead with an interpreter that just sequences the operations and their arguments such that I can unit test that code without doing a bunch of mocking, etc.
I use a version of this trick wherever I can get away with it, even where I can't actually give a monad instance (like rust), because the decoupling alone is super powerful.
deleted by creator
It's just a monoid in the category of endofunctors, what's the problem?
Understanding abstract algebra is the reading theory of functional programming
Amateur! Category theory is the true way (or homotopy type theory if you wanna get wild).
TBH I consider category theory to be a branch of algebra. At least that's the class where it was first formally presented to me.
That's fair. Though I'd say algebra is a branch of category theory. 👀
in theory, yes, but pedagogically it makes more sense as a branch of algebra
You take your pedagogy back to Comet Ping Pong! 👁
deleted by creator
Man everytime I asked my Programming Languages professor what a monad was he would make punting motion.
deleted by creator
It's really just that. A monad is really just a type that admits lawful definitions of
map(so it's a functor),pureandap(so it's an applicative functor) andbind(orflatmap, though depending on your language this may be too powerful compared to a classicalbind, cf. Scala). There's a lot of cool stuff that falls out of that, but if you understand "given a value in some context (of typem a, say) and a function that lifts values into that context (possibly at a different type, i.e.,a -> m b), I can produce a value in the same context (m b, again, possibly at a different type)", there's not much else to look into. The functor, applicative, and monad laws dictate some of the operational characteristics of such definitions on a particular type, but that's really only relevant if you're making your own.deleted by creator
Lifting is just a fancy word for (in this specific case, anyway) taking a concrete value and putting it some kind of computational context.
I have a value
1 :: Int. There are a lot of contexts I can put that concrete value in! That is, I can make lots of values of typem Intthat represent different views on the same value.Let's start by looking at how functors (types that admit a lawful definition of
map) lift values.Normally, this is explained by saying "given a function
a -> band a value of typef afor some functorf, apply the function on eachainf aand give me the result wrapped up inf". Another way of explaining it (which I've written the type for preferentially) is "given a functiona -> b, give me a functionf a -> f b. We're lifting the entire function into whatever our functorial context is.Examples:
Skipping directly up to monads, we really just need
pure :: Monad m => a -> m a(a function which does nothing but put a value into a monadic [technically applicative] context) andbind :: Monad m => m a -> (a -> m b) -> m b. To keep it simple, we'll just reproducemap.So you can see that this is a way of getting a value "out of" some context (like pulling the value of a Maybe or all the values out of a list), doing some sort of transformation on it, then wrapping it back up in the initial context; it also lets you chain these transformations, finally wrapping everything back up when you're done.
flatmapis called that becausebindfor the list monad is exactly "map a function over this list and then flatten the list".nah, they just pop up in a lot of contexts like futures/promises, errors, optionality, etc.. there's also a couple of neat tricks where you take a functor that represents a set of operations you'd like to provide and use an automatic construction to create a (free) monad out of it, thereby getting an interpreter for your DSL with no extra work.
deleted by creator
I'll attempt a more thorough explanation, let me know if this makes any sense.
so I've got a type that represents some operations I want to provide:
data Op = Plus Int Int | Mul Int IntI can turn that into a Functor by swapping the concrete values for a type variable:
data Op a = Plus a a | Mul a aI'm doing this because I want to be able to compose these operations together - I should be able to freely sequence them however I like. so I can pass
Opvalues in foraand nest them as deep as I like. I can also write an interpreter forOpvalues by breaking it down by cases and doing the obvious thing:eval :: OP Int ->Int eval (Plus a b) = a + b eval (Mul a b) = a * bI give that type the obvious, dumb
Functorinstance, nothing special (exercise left for the reader). then, I can passOpto a function (liftFree) that turns it into a monad:liftFree :: Functor f => f a -> Free f a(I'm going to skip the actual definition of
Freeas it's just a type out of the standard library)so I can use
liftFreeto turn the basic operations onOp(PlusandMul) into monadic operations that are allowed to use do-notation:plus :: a -> a -> Free Op a plus a b = liftFree (Plus a b) mul :: a -> a -> Free Op a mul a b = lift Free (Mul a b) calculation :: Free Op Int calculation = do a <- plus 2 3 b <- mul a 5 plus a bfoldFreethen allows me to pass it an interpreter function that evaluates myOpand turn it back into a regular value (like the obvious one I mentioned previously).foldFree :: Functor f => (f r -> r) -> Free f r -> r (foldFree eval calculation) :: IntBUT because I can pass any interpreter I want, I've decoupled evaluation from the definition of the actions I'd like to take. so I could, instead of using an interpreter that calculated the final value, pass in one that pretty-printed it instead, or does a dry-run, etc..
prettyPrint :: Op String -> String foldFree prettyPrint (fmap show calculation)so I can define actions that do a bunch of crazy IO stuff when called with a regular interpreter and run them instead with an interpreter that just sequences the operations and their arguments such that I can unit test that code without doing a bunch of mocking, etc.
I use a version of this trick wherever I can get away with it, even where I can't actually give a monad instance (like rust), because the decoupling alone is super powerful.