It has classes

    • Speaker [e/em/eir]
      ·
      edit-2
      4 years ago

      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 :: Monad m => 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".

      bind ([[1,2,3],[4,5,6]]) id = [1,2,3,4,5,6]
      bind ([[1,2,3],[4,5,6]]) (map (+1)) = [2,3,4,5,6,7]