Max Hallinan

Map Is for Lifting

I doubt very much if it is possible to teach anyone to understand anything, that is to say, to see how various parts of it relate to all the other parts, to have a model of the structure in one's mind. We can give other people names and lists but we cannot give them our mental structures; they must build their own.

—John Holt1

My earliest intuition for map was the for-loop. Map was a cleaner way to iterate over items in a collection. I thought of map primarily as a way to write less code.

Then I learned about functors and map as a for-loop no longer made sense. Functors were presented as boxes. I started to think of map as a hand. Map’s hand reaches out of the box and scoops up a function, pulling it into the box and applying it to the value there.

man building a structure

In both cases, my mental models were driven by how I was using the function. New uses of the function changed my mental model. Working through the monad instance for Free changed my model for map again.

Free contains a structure f and a value a.

data Free f a
  = Pure a
  | Free (f (Free f a))

To implement map, ap, and bind for Free, you need to get at a. But sometimes f stands in the way.

The structure f was like an impossibly tall wall that I kept bumping into. I didn’t want to think about f. I just wanted to get closer to a. Map was the solution every time. I started to think of map as a helpful crane, lifting me up and over the wall, depositing me softly on the other side.

crane lifting a stone

Here are three places where I bumped into the wall f.

fmap k (Free x) = Free $ (fmap . fmap) k x
(<*>) (Pure k) (Free x) = Free $ fmap (fmap k) x
(<*>) (Free k) x = Free $ fmap (<*> x) k
(>>=) (Free x) k = Free $ fmap (>>= k) x

In each case, map carries the function k over this intermediate, unknown structure.

Lift is a term I heard a lot when I started learning Haskell. It’s a term from math and it’s not lifting like cranes lift. Or maybe it is. I’m not sure I understand lift in the formal sense. But I do understand this feeling of bumping into walls. And I understand map as a way over the wall.2

man asking a bird to lift a stone

There are other ways over walls. Each takes a different approach. Some tear the wall down. Others build a new wall. Map is the way over when you want to pretend like the wall doesn’t exist. Nothing happens to the wall, you just get to the other side.

  1. How Children Fail by John Holt, page 145.  
  2. I am curious about the formal definition. But I don't use formal definitions to solve problems. I must understand the concept in a different way, as a fantasy that I inhabit, like the hand or the crane.

    Again from Holt, “A child who has really learned something can use it, and does use it. It is connected with reality in his mind, therefore he can make other connections between it and reality when the chance comes. A piece of unreal learning has no hooks on it; it can't be attached to anything, it is of no use to the learner.” How Children Fail, page 169.