Functor map

map is a pretty cool guy—he’s even pretty regular in normal codebases now. As we come to see data more as a transformation, the idea of mapping just makes sense. Surprisingly many people think map is just for collections. Really, map is for transforming values inside contexts. You’ve probably used to map in this form:

[ 0, 1, 2, 3, 4 ].map((x) => x + 10)
//=> [10, 11, 12, 13, 14]

R.map(R.add(10), [ 0, 1, 2, 3, 4 ])
//=> [10, 11, 12, 13, 14]

but that same concept can be applied to Maybe. In the previous blog, we talked about how to get values out of a Maybe, but we really need to be able to do things inside the Maybe so that we can hold on to this optionality.

Functor ≠ Iterable

As we will look at in this and some Maybe examples, we can map something that’s not iterable. If we imagined the hand holding a value, or an apple

we have an eat function: eat : FreshFood -> EatenFood. We know that outside that context we can eat food freely (imagine a floating apple in space). However, we have a context, our hand, with which we must deal with. We can lift that concept of eat into hand context with map.

-- conceptually this is just like a Maybe
type Hand a = Holding a | Empty

Hand.map eat (Holding Apple)
--=> Holding EatenApple

and BAM, we have an apple that’s eaten that is still in that hand context!

Had my hand been empty, I would having nothing to eat, so the hand would remain empty. So when you think of x is “mappable”, you can start thinking x is a Functor. Also with a type system, we can guarantee that we will turn type a into type b.

Click to expand if you really care to see the full implementation, but it’s basically the next section (but it does compile :3)

import Html exposing (Html, text)


type Hand a
    = Holding a
    | Empty


type FreshFood
    = Apple


type EatenFood
    = EatenApple


map : (a -> b) -> Hand a -> Hand b
map f hand =
    case hand of
        Holding value ->
            Holding <| f value

        Empty ->
            Empty


eat : FreshFood -> EatenFood
eat (Apple) =
    EatenApple


prestineApple : Hand FreshFood
prestineApple =
    Holding Apple


main : Html String
main =
    text << toString <| map eat prestineApple
--=> Holding EatenApple

Maybe Functor

map : (a -> b) -> Maybe a -> Maybe b
map f maybe =
    case maybe of
        Just value ->
            Just <| f value

        Nothing ->
            Nothing

You can see that we will pattern match the Maybe that was passed in. If it’s Just and contains a value, apply a value to that value and wrap it back up with a Just. In the Nothing case, there’s nothing to map, so we return Nothing. Reiterating, we are going from some generic a to generic b, so we can change types.

Elm
m : Maybe Int
m = Maybe.map ((*) 2) <| Just 4
--=> Just 8

n : Maybe Int
n = Maybe.map ((*) 2) <| Nothing
--=> Nothing

o : Maybe String
o = Maybe.map toString <| Just 10
--=> Just "10"

p : Maybe String
p = Maybe.map toString <| Nothing
--=> Nothing

q : Maybe (List Int)
q = Maybe.map (List.map ((*) 2)) <| Just [ 0, 2, 4 ]
--=> Just [ 0, 4, 8 ]

r : Maybe (List Int)
r = Maybe.map (List.map ((*) 2) <| Nothing
--=> Nothing
JavaScript + Ramda Fantasy
const m = Maybe.Just(4).map((x) => x * 2)
//=> Object { value: 8 }

const n = Maybe.Nothing().map((x) => x * 2)
//=> Object {  }

const o = Maybe.Just(10).map((x) => x.toString())
//=> Object { value: "10" }

const p = Maybe.Nothing().map((x) => x.toString())
//=> Object {  }

const q = Maybe.Just([0, 2, 4]).map((xs) => xs.map((x) => x * 2))
//=> Object { value: [0, 4, 8] }

const r = Maybe.Nothing().map((xs) => xs.map((x) => x * 2))
//=> Object {  }
JavaScript + Ramda + Ramda Fantasy
const s = R.map(R.multiply(2), Maybe.Just(4))
//=> Object { value: 8 }

const t = R.map(R.multiply(2), Maybe.Nothing())
//=> Object {  }

const u = R.map(R.toString, Maybe.Just(10))
//=> Object { value: "10" }

const v = R.map(R.toString, Maybe.Nothing())
//=> Object {  }

const w = R.map(R.map(R.multiply(2)), Maybe.Just([0, 2, 4]))
//=> Object { value: [0, 4, 8] }

const x = R.map(R.map(R.multiply(2)), Maybe.Nothing())
//=> Object {  }

Functor Laws

So there are Functor laws to be proven for a type to be a functor.

-- Haskell Signatures

-- Identity
id :: a -> a

-- Functor map
fmap :: Functor f => (a -> b) -> f a -> f b

Law 1:

-- Haskell
fmap id = id

Mapping with identity is the same as identity itself

Elm
Maybe.map identity <| Just "$$"
--=> Just "$$"

identity <| Just "$$"
--=> Just "$$"
JavaScript
//: a -> a
const identity = (x) => x

Maybe.Just("$$").map(identity)
//=> Object { value: "$$" }

identity(Maybe.Just("$$"))
//=> Object { value: "$$" }
JavaScript + Ramda + Ramda Fantasy
R.map(R.identity, Maybe.Just("$$"))
//=> Object { value: "$$" }

R.identity(Maybe.Just("$$"))
//=> Object { value: "$$" }

Law 2:

-- Haskell
fmap (p . q) = (fmap p) . (fmap q)

Mapping and mapping again is the same as mapping once, but composing those inner functions. This law has a positive performance side-effect, because it doesn’t have the cost of unwrapping and rewrapping with the Functor context.

We’re going to take a Maybe (List Int), add 1 to each value, then sum the list.

j : Maybe (List Int)
j =
    Just [ 0, 1, 2, 3 ]


-- Point-full & pipeless
Maybe.map List.sum (Maybe.map (List.map (\x -> x + 1)) j)
--=> Just 6

-- Same as above but using pipe, |>, and taking advantage of currying
j
    |> Maybe.map (List.map ((+) 1))
    |> Maybe.map List.sum
--=> Just 6

-- Composed gives the same result + THE PERF WIN
Maybe.map (List.map ((+) 1) >> List.sum) j
--=> Just 6
//: Maybe [Number]
const j = Maybe.Just([0, 1, 2, 3])


j.map((xs) => xs.map((x) => x + 1))
	.map((xs) => xs.reduce((acc, x) => acc + x, 0))
//=> Object { value: 6 }

// Composed
j.map((xs) =>
  xs.map((x) => x + 1)
    .reduce((acc, x) => acc + x, 0)
)
//=> Object { value: 6 }


//-- Ramda -----

// Not piped
R.map(R.sum, R.map(R.add(1), j)))
//=> Object { value: 6 }

// Point-free & piped
R.pipe(
	R.map(R.map(R.add(1))),
	R.map(R.sum),
)(j)
//=> Object { value: 6 }

// Composed
R.map(R.pipe(R.map(R.add(1)), R.sum), j)
//=> Object { value: 6 }

Of note in JS, you start to see that with more complex transformations, the currying of Ramda becomes waaay more terse and also a lot less noisy with the pointful lamdas (often called “anonymous functions” in JS). With a good function API, you can be both expressive, terse, and easy to read.

Lists & Arrays

We talked about how iterable doesn’t mean functor. So what does that mean for List? If map is transforming values in a context, how would transform the values inside a List? map by definition has this (a -> b) part in its signature. If you have a List Int and you are going to List String, your map implementation better change all values of that list from an Int to a String. To do that you’d walk a function across all of the list values. Let’s implement this recursively (note this is not how Elm actually does map in the core, and it’s also not optimal because it’s not tail-call optimized).

map : (a -> b) -> List a -> List b
map f xs =
    case xs of
        [] ->
            []

        head :: tail ->
            f head :: map f tail

Just like the Maybe, this starts with a pattern match. Given our empty list, return an empty list, otherwise split on the head and tail of the list, then run the function on the head and cons the return of a recursive call to map on the tail—transforming every value in that list. Granted we are going from List Int to List Int, not showing (a -> b) (which is okay), but addition is such an easy-to-understand example. So looking at that in slow motion:

map ((+) 1) [ 1, 2, 3 ]
--=> [ 2, 3, 4 ]

((+) 1 1) :: map ((+) 1) [ 2, 3 ]
2 :: map ((+) 1) [ 2, 3 ]
2 :: ((+) 1 2) :: map ((+) 1) [ 3 ]
2 :: 3 :: map ((+) 1) [ 3 ]
2 :: 3 :: ((+) 1 3) :: map ((+) 1) []
2 :: 3 :: 4 :: map ((+) 1) []
2 :: 3 :: 4 :: []
-- Which is already the same as [ 2, 3, 4 ] since
-- that is the underlying structure of a cons list
2 :: 3 :: [ 4 ]
2 :: [ 3, 4 ]
[ 2, 3, 4 ]
JavaScript Via Destructuring (Also Not Optimal)
//: (a -> b) -> [a] -> [b]
const map = (f, [ head, ...tail ]) =>
  head === void 0 ? [] : [ f(head), ...map(f, tail) ]

map((x) => x + 1, [ 1, 2, 3 ])
//=> [ 2, 3, 4 ]

[ 1 + 1, ...map((x) => x + 1, [ 2, 3 ]) ]
[ 2, ...map((x) => x + 1, [ 2, 3 ]) ]
[ 2, ...[ 2 + 1, ...map((x) => x + 1, [ 3 ]) ] ]
[ 2, ...[ 3, ...map((x) => x + 1, [ 3 ]) ] ]
[ 2, ...[ 3, ...[ 3 + 1, ...map((x) => x + 1, []) ] ] ]
[ 2, ...[ 3, ...[ 4, ...map((x) => x + 1, []) ] ] ]
[ 2, ...[ 3, ...[ 4, ...[] ] ] ]
[ 2, ...[ 3, ...[ 4 ] ] ]
[ 2, ...[ 3, 4 ] ]
[ 2, 3, 4 ]

The JavaScript map’s signature is a bit misleading, since outside the special typed arrays we can never guarantee in JavaScript array items are of the same type. An error will also be thrown if the argument for the array is not iterable.

Why Can’t I map a Set?

I get it: transforming values within a context! But with Set, why not? I mean it’s iterable and list-like… Well, by definition Set includes that fun property of uniqueness. Imagine if we could:

//: [Int]
ints = [ 1, 2, 3, 4 ]

// is it odd?
ints.map((x) => x % 2)
//=> [ 1, 0, 1, 0 ]

// Now imagine that if Set had map
(new Set(ints)).map((x) => x % 2)
//=> ???

Set [ 1, 0, 1, 0 ] isn’t a Set because the values are not unique and Set [ 0, 1 ] makes sense-ish, but if we compare that to our above array map implementation, we can’t transform each value and maintain the same size. Losing values isn’t a part of map. As such, since we cannot guarantee uniqueness with map on Sets, Set is not a Functor. This should further drive home the functor-is-not-iterable point.


A Real World Use of Functors

Let’s say we have some (JSON parsed) data

{
  "characters": [
    {
      "name": "Ganonu",
      "piece": 0
    },
    {
      "name": "Zeldu",
      "piece": 1
    },
    {
      "name": "Linku",
      "piece": 2
    },
    {
      "name": "Impu",
      "piece": -1
    },
    {
      "name": "Midnu",
      "piece": -1
    },
    {
      "name": "Tinglu",
      "piece": -1
    }
  ]
}

This data of a “random” characters, that may or may not have a piece of this thing called the Triforks which can be represented as a tagged union (also known as an enum in some languages). Since JSON can’t represent this structure, our API has returned us an integer representation. Since some characters don’t have a piece, the value needs to be a Maybe TriforksPiece. What we want to do is represent this in some virtual DOM. If the piece exists, add it to the text of a list item, <li>, (i.e. “Zeldu - Wisdom” & “Tinglu”).

So the maps we’ll be using:

And a bimap (essentially passing in two function to be about to map both the error and the success) with default to allow a value to fall out

Result.unpack : (a -> b) -> (e -> b) -> Result a e -> b
Elm
import Html exposing (Html, li, text)
import Html.Keyed exposing (ul)
import Json.Decode as Decode exposing (Decoder)
import Result.Extra as Result


-- Syntax for building unions and ADTs…
type TriforksPiece
    = Power
    | Wisdom
    | Courage


-- For transforming the JSON’s Int
toTriforksPiece : Int -> Maybe TriforksPiece
toTriforksPiece i =
    case i of
        0 ->
            Just Power

        1 ->
            Just Wisdom

        2 ->
            Just Courage

        _ ->
            Nothing


-- For transforming the union back to a String for the view
-- We _could_ run `toString` on Triforks Piece, but this
-- future-proofs us for translations
triforksPieceToString : TriforksPiece -> String
triforksPieceToString tp =
    case tp of
        Power ->
            "Power"

        Wisdom ->
            "Wisdom"

        Courage ->
            "Courage"


type alias Character =
    { name : String
    , piece : Maybe TriforksPiece
    }


-- In Elm we decode and explicitly verify our JSON schema via
-- a Json.Decode.Decoder
-- Note: Decode.map turning our Int into a Maybe TriforksPiece
characterDecoder : Decoder Character
characterDecoder =
    Decode.map2 Character
        (Decode.field "name" Decode.string)
        (Decode.field "piece" Decode.int |> Decode.map toTriforksPiece)


-- Keyed HTML is best used in list-like data like our characters
-- indexedMap was used to get that key
viewCharacter : Int -> Character -> ( String, Html String )
viewCharacter idx { name, piece } =
    let
        -- Use map to compose a transformation of a union type
        -- into a string & then append to " - ", then let the
        -- value fall out with "", then append to the name
        label : String
        label =
            Maybe.map (triforksPieceToString >> (++) " - ") piece
                |> Maybe.withDefault ""
                |> (++) name

    in
        -- Ex. <li>Linku - Courage</li> or <li>Impu</li>
        ( toString idx , li [] [ text label ] )


-- Assume we pass the JSON stringify’d string into the view
-- Unpack an Err’s String into text on failure while
-- putting Ok through the list maker
view : String -> Html String
view =
    Decode.decodeString
        (Decode.field "characters" (Decode.list characterDecoder))
        >> Result.unpack text
           (List.indexedMap viewCharacter >> ul [])
JavaScript + Ramda + Ramda Fantasy + virtual-dom
import R from "ramda"
import { Either, Maybe } from "ramda-fantasy"
import h from "virtual-dom/h"


// As the Ramda docs show, indexedMap isn’t default
//: ((a, Int) -> b) -> [a] -> [b]
const indexedMap =
  R.addIndex(R.map)


// Like Elm’s Dict.get, we need a safe function for getting
// values out of a map, and returning a Maybe since the
// function can fail to retrieve a value. Map.prototype.get
// returns `a | null`.
//: comparable -> Map comparable a -> Maybe a
const mapGet = R.curryN(2, (key, map) =>
  map instanceof Map ? Maybe(map.get(key)) : Maybe.Nothing()
)


// Now that we’re done building general helpers...........


// Use an `Either` to handle JSON parsing errors — it’s similar
// to a `Maybe`, but is `Either a b = Left a | Right b`.
// We will be validating the structure too.
//: String -> Either String [Character]
const decodeCharacterJSON = (j) => {
  let json

  try {
    json = JSON.parse(j)
  } catch(e) {
    // Fail on failed parse
    return Either.Left(`JSON parsing fail: ${e.message}`)
  }

  return R.ifElse(
    // condition for characters
    R.allPass([
      Array.isArray,
      R.all(R.propSatisfies((n) => typeof n === "string", "name"))
    ]),
    // is array and all have string name prop, pipe through & pass
    R.pipe(
      R.project([ "name", "piece" ]),
      Either.Right
    ),
    // else, pipe through & fail
    R.pipe(
      JSON.stringify,
      R.concat("JSON parsed, but characters are misformed: "),
      Either.Left
    )
  )(R.prop("characters", json))
}


// JavaScript doesn’t support ADTs or Enums, so a Map of
// Strings will have to do.
// Haskell: `newtype TriforksPiece = TriforksPiece String`
// Elm: `type alias TriforksPiece = String`
//: Map Int TriforksPiece
const TriforksPieces =
  new Map([
    [ 0, "Power" ],
    [ 1, "Wisdom" ],
    [ 2, "Courage" ]
  ])


// Partially apply in the TriforksPiece Map
//: Int -> Maybe TriforksPiece
const toTriforksPiece =
  R.flip(mapGet)(TriforksPieces)


// Ex. <li>Linku - Courage</li> or <li>Impu</li>
//: (Character, Int) -> VDOM
viewCharacter = ({ name, piece }, idx) => {
  // Remember, piece : Maybe TriforksPiece
  //: String
  const label =
    name + R.map(R.concat(" - "), piece).getOrElse("")

  return h("li", { key: idx }, label)
}


//: [Character] -> VDOM
viewCharacters = (chars) =>
  h("ul", {}, indexedMap(viewCharacter, chars))


// Assume our `view` takes in a JSON.stringify’d string of characters
//: String -> VDOM
const view =
  R.pipe(
    decodeCharacterJSON,
    // map the Either then List to update the Triforks pieces
    R.map(R.map(R.evolve({ piece: toTriforksPiece }))),
    // After our data is transformed into a way we like use
    // `either` to unpack the String error & the List Character
    // into their respective view functions
    R.invoker(2, "either")((e) => h("div", {}, e))(toviewCharacters)
  )

In Part III, we will be looking at the type classes of Semigroup and Moniod which gives us associativity and the ability to concat.