Tail recursive `map` for Dict.LLRB. Slow, but hey, it works.

LLRBmap.elm

map : (k -> a -> b) -> Dict k a -> Dict k b
map f dict =
    case dict of
        Leaf ->
            Leaf

        Node c k v l r ->
            mapHelper f { key = k, color = c, value = f k v, state = Both l r } []


type Todo k a b
    = Both (Dict k a) (Dict k a)
    | TRight (Dict k b) (Dict k a)
    | Done (Dict k b) (Dict k b)


type Doing k a b
    = DLeft (Dict k a)
    | DRight (Dict k b)


type alias MapAcc k b c =
    { key : k
    , color : Color
    , value : b
    , state : c
    }


type alias TodoMapAcc k a b =
    MapAcc k b (Todo k a b)


type alias DoingMapAcc k a b =
    MapAcc k b (Doing k a b)


mapHelper : (k -> a -> b) -> TodoMapAcc k a b -> List (DoingMapAcc k a b) -> Dict k b
mapHelper f acc stack =
    case acc.state of
        Both Leaf Leaf ->
            let
                node =
                    Node acc.color acc.key acc.value Leaf Leaf
            in
            case stack of
                [] ->
                    node

                top :: rest ->
                    mapHelper f { top | state = markDone node top.state } rest

        Both Leaf (Node c k v l r) ->
            mapHelper f
                { key = k, color = c, value = f k v, state = Both l r }
                ({ acc | state = DRight Leaf } :: stack)

        Both (Node c k v l r) right ->
            mapHelper f
                { key = k, color = c, value = f k v, state = Both l r }
                ({ acc | state = DLeft right } :: stack)

        TRight l Leaf ->
            let
                node =
                    Node acc.color acc.key acc.value l Leaf
            in
            case stack of
                [] ->
                    node

                top :: rest ->
                    mapHelper f { top | state = markDone node top.state } rest

        TRight left (Node c k v l r) ->
            mapHelper f
                { key = k, color = c, value = f k v, state = Both l r }
                ({ acc | state = DRight left } :: stack)

        Done l r ->
            let
                node =
                    Node acc.color acc.key acc.value l r
            in
            case stack of
                [] ->
                    node

                top :: rest ->
                    mapHelper f { top | state = markDone node top.state } rest


markDone : Dict k b -> Doing k a b -> Todo k a b
markDone node state =
    case state of
        DLeft r ->
            TRight node r

        DRight l ->
            Done l node