Adding Unique Keys to Content


#1

I’m working on a visual email editor which saves and loads JSON representing an email. Editing text is accomplished using Ports and a JavaScript text editor, and these pieces of text can be moved and reordered. When moving these items, to preserve their content, I would like to use Html.Keyed.node. I currently don’t have IDs on anything, so I’m curious if anyone has advice on how I should add them. It’s not straightforward to derive these IDs from the content of the text, because editing the content in JS would change the ID and change the node the JS is using. The best solution here might be to fix the content of a node while it’s being edited, but nodes with identical content might still behave strangely, given that they have the same IDs. The rest of this question explores the assignment of IDs that don’t depend on the content of a node (sorry it’s long :grimacing:).

The model for an email is basically List(List(List(List(Node)))), though each List wrapped in a custom type. For example, the top type is like:

type alias Email =
    { body : List Section }

The basic approach I’m taking to attach IDs to everything is to use an opaque type to store an Int to track the next available ID.
This method takes this opaque type and gives an opaque ID:

generate : IdGenerator -> ( IdGenerator, Id )

and a more general use of the function can apply unique IDs to a list, transforming the list using the first function argument:

addKeys : (Id -> a -> b) -> IdGenerator -> List a -> ( IdGenerator, List b )

This seems fine, but now I’m starting to look at attaching these IDs to the content when it is decoded from JSON, and this seems at least a bit unusual:

decodeEmail : IdGenerator -> Decoder ( IdGenerator, Email )

This turns out to be impossible (as far as I can tell) for the inner lists of content, because the addKeys function shown above can’t generalize to work inside of decoders: it is implemented using List.foldr, and there’s no ability to fold over a list in a decoder (there’s only . The main alternative I can think of is to decode a List (Id -> Section), and then Decode.map the addKeys function over that list. Is this the best option?

I was trying to avoid this, because there are four nested levels in our Email type, and each of these levels needs Ids supplied to it. We’d need to maintain a data structure alongside our Email data structure where each type has an identical type declared that differs only in its missing an Id. Does anyone have any ideas for a design here?


#2

One thought, do you need separate Ids on all of the nested elements within an email? Perhaps your html keys could be of the form (emailId ++ "sectionOfEmail") or even (emailId ++ "path/to/section/of/email")?

Including the email id when encoding/decoding to/from json also seems quite reasonable. If you’re worried about collisions you could consider using https://package.elm-lang.org/packages/TSFoster/elm-uuid/latest/ instead of using incremental ids.


#3

Thanks for your thoughts on this! Using the position of the content in the email unfortunately won’t work: the goal is to tell Elm not to change the contents of nodes when reordering them, so the keys have to move along with the content when it is moved.

As for UUIDs, we still end up with the same problem when decoding the model: instead of our custom IdGenerator, we’d need to pass a Random.Seed into the Decode.list in order to give UUIDs to each decoded value. Because getting a UUID has an external dependency, and because there’s no way to fold to pass that dependency to each item of the decoded list, I don’t see a way to do this in the context of a decoder :confused:.


#5

I slept on this and I’m leaning towards the decoders returning functions waiting for IdGenerators, so hopefully I shouldn’t have to change every level of the core data structure in the app. I didn’t want to make my original post too long, but I think maybe this more concrete example will help: Here’s the function I wanted to write, but can’t seem to figure out:

type alias IdentifiedDecoder a =
    IdGenerator -> Decoder ( IdGenerator, a )

identifiedDecoderList : IdentifiedDecoder a -> IdentifiedDecoder (List a)
identifiedDecoderList = ...

Should this be possible using Decode.andThen and Decode.list? I think the signature for IdentifiedDecoder won’t really work, so I’ll try changing it to Decoder ( IdGenerator -> ( IdGenerator, a )). Somehow this morning that seems more promising.


#6

tl;dr: Here is an API cloned from elm/json and NoRedInk/elm-json-decode-pipeline that allows you to do:

type alias Email =
    { address : String
    , id : Id
    , tags : List Tag
    }


type alias Tag =
    { id : Id
    , name : String
    }

decodeTag : IndexedDecoder Tag
decodeTag =
    Decode.succeed Tag
        |> Decode.index
        |> Decode.required "name" Decode.string


decodeTags : IndexedDecoder (List Tag)
decodeTags =
    Decode.list decodeTag


decodeEmail : IndexedDecoder Email
decodeEmail =
    Decode.succeed Email
        |> Decode.required "address" Decode.string
        |> Decode.index
        |> Decode.required "tags" decodeTags


decodeEmails : IndexedDecoder (List Email)
decodeEmails =
    Decode.list decodeEmail


json : String
json =
    """
[
  { "address": "foo@mail.com",
    "tags": [
      {"name": "tag1"},
      {"name": "tag2"}
    ]    
  },
  { "address": "bar@mail.com"
  , "tags": [
      {"name": "tag3"}
    ]    
  }
]
"""

main =
    case Decode.decodeString decodeEmails json 0 of
        Ok ( emails, id ) ->
            viewEmails emails

        Err err ->
            text (Decode.errorToString err)

to produce:

foo@mail.com[2]
  tag1[0]
  tag2[1]
bar@mail.com[4]
  tag3[3]

Basically, you have an additional Decode.index function that you can place in the pipeline where the generated id is needed.

Ellie all-in-one dirty example: https://ellie-app.com/43dX7qnC6Csa1

Details:
I think this is an interesting problem that could deserve an official package, and your last approach seems close to mine.

Here is a start using a random positive id with Random.int and an API close to NoRedInk/elm-json-decode-pipeline:

Given the following (incomplete but working) Indexed.Decode module:

module Indexed.Decode exposing
    ( Id
    , IndexedDecoder
    , decodeString
    , decoder
    , errorToString
    , index
    , list
    , map
    , map2
    , required
    , string
    , succeed
    )

import Json.Decode as Decode exposing (Decoder)
import Json.Decode.Pipeline as Pipeline
import Random exposing (Generator, Seed)
import Random.Extra as Random


type alias Id =
    Int


type alias Error =
    Decode.Error


type alias IndexedDecoder a =
    Decoder (Generator a)


custom : IndexedDecoder a -> IndexedDecoder (a -> b) -> IndexedDecoder b
custom =
    Decode.map2 (Random.map2 (|>))


decoder : Decoder a -> IndexedDecoder a
decoder dec =
    Decode.map Random.constant dec


decodeString : IndexedDecoder a -> String -> Seed -> Result Decode.Error ( a, Seed )
decodeString dec str seed =
    Decode.decodeString (step dec seed) str


errorToString : Error -> String
errorToString =
    Decode.errorToString


field : String -> IndexedDecoder a -> IndexedDecoder a
field key dec =
    Decode.field key dec


index : IndexedDecoder (Id -> a) -> IndexedDecoder a
index dec =
    let
        genId =
            Random.int 0 Random.maxInt
    in
    Decode.map (\gen -> Random.map2 (|>) genId gen) dec


list : IndexedDecoder a -> IndexedDecoder (List a)
list dec =
    Decode.map Random.combine (Decode.list dec)


map : (a -> value) -> IndexedDecoder a -> IndexedDecoder value
map f dec =
    Decode.map (Random.map f) dec


map2 : (a -> b -> value) -> IndexedDecoder a -> IndexedDecoder b -> IndexedDecoder value
map2 f dec1 dec2 =
    Decode.map2 (Random.map2 f) dec1 dec2


required : String -> IndexedDecoder a -> IndexedDecoder (a -> b) -> IndexedDecoder b
required key valDecoder dec =
    custom (field key valDecoder) dec


step : IndexedDecoder a -> Seed -> Decoder ( a, Seed )
step dec seed =
    Decode.map (\gen -> Random.step gen seed) dec


string : IndexedDecoder String
string =
    decoder Decode.string


succeed : a -> IndexedDecoder a
succeed a =
    Decode.succeed (Random.constant a)

You can use it like the Json pipeline API with the addition of the index function where an index is needed:

module Main exposing (main)

import Html exposing (Html, div, span, text)
import Html.Attributes exposing (style)
import Indexed.Decode as Decode exposing (Id, IndexedDecoder)
import Json.Encode as Encode
import Random


type alias Email =
    { address : String
    , id : Id
    , tags : List Tag
    }


type alias Tag =
    { id : Id
    , name : String
    }


viewEmails : List Email -> Html msg
viewEmails emails =
    div [] (List.map viewEmail emails)


viewEmail : Email -> Html msg
viewEmail email =
    div []
        [ text email.address
        , viewId email.id
        , viewTags email.tags
        ]


viewTags : List Tag -> Html msg
viewTags tags =
    div [ style "margin-left" "8px" ]
        (List.map viewTag tags)


viewTag : Tag -> Html msg
viewTag tag =
    div []
        [ text tag.name
        , viewId tag.id
        ]


viewId : Id -> Html msg
viewId id =
    text ("[" ++ String.fromInt id ++ "]")


json : String
json =
    """
[
  { "address": "foo@mail.com",
    "tags": [
      {"name": "tag1"},
      {"name": "tag2"}
    ]    
  },
  { "address": "bar@mail.com"
  , "tags": [
      {"name": "tag3"}
    ]    
  }
]
"""


decodeTag : IndexedDecoder Tag
decodeTag =
    Decode.succeed Tag
        |> Decode.index
        |> Decode.required "name" Decode.string


decodeTags : IndexedDecoder (List Tag)
decodeTags =
    Decode.list decodeTag


decodeEmail : IndexedDecoder Email
decodeEmail =
    Decode.succeed Email
        |> Decode.required "address" Decode.string
        |> Decode.index
        |> Decode.required "tags" decodeTags


decodeEmails : IndexedDecoder (List Email)
decodeEmails =
    Decode.list decodeEmail


main =
    case Decode.decodeString decodeEmails json (Random.initialSeed 0) of
        Ok ( emails, seed ) ->
            viewEmails emails

        Err err ->
            text (Decode.errorToString err)

This produces the following output:

foo@mail.com[884571026]
  tag1[1348153153]
  tag2[1613638464]
bar@mail.com[1382093769]
  tag3[1707621207]

It is then possible to have an incremental id instead of a random one by replacing the Random API by a custom Indexed one. Let’s add the Indexed module exposing the Indexer type:

module Indexed exposing
    ( Id
    , Indexer
    , combine
    , constant
    , id
    , map
    , map2
    , step
    )


type alias Id =
    Int


type Indexer a
    = Indexer (Id -> ( a, Id ))


combine : List (Indexer a) -> Indexer (List a)
combine indexers =
    case indexers of
        [] ->
            constant []

        g :: gs ->
            map2 (::) g (combine gs)


constant : a -> Indexer a
constant value =
    Indexer (\i -> ( value, i ))


id : Indexer Id
id =
    Indexer (\i -> ( i, i + 1 ))


map : (a -> b) -> Indexer a -> Indexer b
map func (Indexer indexA) =
    Indexer
        (\id0 ->
            let
                ( a, id1 ) =
                    indexA id0
            in
            ( func a, id1 )
        )


map2 : (a -> b -> c) -> Indexer a -> Indexer b -> Indexer c
map2 func (Indexer indexA) (Indexer indexB) =
    Indexer
        (\id0 ->
            let
                ( a, id1 ) =
                    indexA id0

                ( b, id2 ) =
                    indexB id1
            in
            ( func a b, id2 )
        )


step : Indexer a -> Id -> ( a, Id )
step (Indexer generator) i =
    generator i

then add a Indexed.IncDecode.elm module almost identical to our previous Indexed.Decode (that we could rename to Indexed.RandomDecode or something), but using Indexed instead of Random:

module Indexed.IncDecode exposing
    ( Id
    , IndexedDecoder
    , decodeString
    , decoder
    , errorToString
    , index
    , list
    , map
    , map2
    , required
    , string
    , succeed
    )

import Indexed exposing (Indexer)
import Json.Decode as Decode exposing (Decoder)
import Json.Decode.Pipeline as Pipeline


type alias Id =
    Indexed.Id


type alias Error =
    Decode.Error


type alias IndexedDecoder a =
    Decoder (Indexer a)


custom : IndexedDecoder a -> IndexedDecoder (a -> b) -> IndexedDecoder b
custom =
    Decode.map2 (Indexed.map2 (|>))


decoder : Decoder a -> IndexedDecoder a
decoder dec =
    Decode.map Indexed.constant dec


decodeString : IndexedDecoder a -> String -> Id -> Result Decode.Error ( a, Id )
decodeString dec str seed =
    Decode.decodeString (step dec seed) str


errorToString : Error -> String
errorToString =
    Decode.errorToString


field : String -> IndexedDecoder a -> IndexedDecoder a
field key dec =
    Decode.field key dec


index : IndexedDecoder (Id -> a) -> IndexedDecoder a
index dec =
    Decode.map (\gen -> Indexed.map2 (|>) Indexed.id gen) dec


list : IndexedDecoder a -> IndexedDecoder (List a)
list dec =
    Decode.map Indexed.combine (Decode.list dec)


map : (a -> value) -> IndexedDecoder a -> IndexedDecoder value
map f dec =
    Decode.map (Indexed.map f) dec


map2 : (a -> b -> value) -> IndexedDecoder a -> IndexedDecoder b -> IndexedDecoder value
map2 f dec1 dec2 =
    Decode.map2 (Indexed.map2 f) dec1 dec2


required : String -> IndexedDecoder a -> IndexedDecoder (a -> b) -> IndexedDecoder b
required key valDecoder dec =
    custom (field key valDecoder) dec


step : IndexedDecoder a -> Id -> Decoder ( a, Id )
step dec seed =
    Decode.map (\gen -> Indexed.step gen seed) dec


string : IndexedDecoder String
string =
    decoder Decode.string


succeed : a -> IndexedDecoder a
succeed a =
    Decode.succeed (Indexed.constant a)

Our Main is identical except the imports and the main function:

module Main exposing (main)

import Html exposing (Html, div, span, text)
import Html.Attributes exposing (style)
import Indexed.IncDecode as Decode exposing (Id, IndexedDecoder)
import Json.Encode as Encode
import Random


type alias Email =
    { address : String
    , id : Id
    , tags : List Tag
    }


type alias Tag =
    { id : Id
    , name : String
    }


viewEmails : List Email -> Html msg
viewEmails emails =
    div [] (List.map viewEmail emails)


viewEmail : Email -> Html msg
viewEmail email =
    div []
        [ text email.address
        , viewId email.id
        , viewTags email.tags
        ]


viewTags : List Tag -> Html msg
viewTags tags =
    div [ style "margin-left" "8px" ]
        (List.map viewTag tags)


viewTag : Tag -> Html msg
viewTag tag =
    div []
        [ text tag.name
        , viewId tag.id
        ]


viewId : Id -> Html msg
viewId id =
    text ("[" ++ String.fromInt id ++ "]")


json : String
json =
    """
[
  { "address": "foo@mail.com",
    "tags": [
      {"name": "tag1"},
      {"name": "tag2"}
    ]    
  },
  { "address": "bar@mail.com"
  , "tags": [
      {"name": "tag3"}
    ]    
  }
]
"""


decodeTag : IndexedDecoder Tag
decodeTag =
    Decode.succeed Tag
        |> Decode.index
        |> Decode.required "name" Decode.string


decodeTags : IndexedDecoder (List Tag)
decodeTags =
    Decode.list decodeTag


decodeEmail : IndexedDecoder Email
decodeEmail =
    Decode.succeed Email
        |> Decode.required "address" Decode.string
        |> Decode.index
        |> Decode.required "tags" decodeTags


decodeEmails : IndexedDecoder (List Email)
decodeEmails =
    Decode.list decodeEmail


main =
    case Decode.decodeString decodeEmails json 0 of
        Ok ( emails, id ) ->
            viewEmails emails

        Err err ->
            text (Decode.errorToString err)

and we get:

foo@mail.com[2]
  tag1[0]
  tag2[1]
bar@mail.com[4]
  tag3[3]

Edit:
Here is a very dirty all-in-one ellie example to play with it: https://ellie-app.com/43dX7qnC6Csa1.
But this should really be properly splitted in several modules as lots of function names are identical.


#7

This is more than I could have possibly hoped for! It’s going to take me a bit to digest, but I’m thrilled that you’ve taken this on. The Ellie looks fantastic :open_mouth:. I’d love to see this in an official package! Thank you!


#8

I may make an official package in the following weeks/months if nobody does it before as I will most likely need it (probably with strong Uuid support).

Ping me on slack if you are stuck.


#9

This worked for me! All the models are the same, just they now have Id fields, and when a model had something like an init function to get a new value, it’s now an Indexer. All the Decoders for the main data structure in the app are IndexedDecoders.

In this app, there are some Fuzz tests that check to make sure encoders and decoders work together well, like this:

        describe "JSON Persistence"
            [ fuzz fuzzEmailIndexer "decodeEmail complements encodeEmail" <|
                \emailIndexer ->
                    let
                        email =
                            runIndexer emailIndexer
                    in
                    Expect.equal
                        (email
                            |> Data.Email.encodeEmail
                            |> Decode.decodeValue Data.Email.decodeEmail
                            |> Result.map runIndexer
                        )
                        (Ok email)
            ]

runIndexer : Indexer a -> a
runIndexer indexer =
    indexerStep indexer 0
        |> Tuple.first

So I had to figure out how to get consistent IDs in test. I expect there’s a more clever solution, but in the spirit of getting things working, I just copied your IndexedDecoder interface wholesale, and made IndexedFuzzers for all the models involved in these sorts of tests.

module IndexedFuzzers exposing (IndexedFuzzer, custom, fuzzer, index, list, mapFuzzerIndexer, succeed)

import Fuzz exposing (..)
import Fuzzers exposing (fuzzList)
import Indexed exposing (..)


type alias IndexedFuzzer a =
    Fuzzer (Indexer a)


mapFuzzerIndexer : (a -> b) -> Fuzzer (Indexer a) -> Fuzzer (Indexer b)
mapFuzzerIndexer =
    indexerMap >> map


list : IndexedFuzzer a -> IndexedFuzzer (List a)
list fuzzer_ =
    map combine (fuzzList fuzzer_)


custom : IndexedFuzzer a -> IndexedFuzzer (a -> b) -> IndexedFuzzer b
custom =
    map2 (indexerMap2 (|>))


index : IndexedFuzzer (Id -> a) -> IndexedFuzzer a
index dec =
    map (\gen -> indexerMap2 (|>) id gen) dec


fuzzer : Fuzzer a -> IndexedFuzzer a
fuzzer dec =
    Fuzz.map Indexed.constant dec


succeed : a -> IndexedFuzzer a
succeed a =
    Fuzz.constant (Indexed.constant a)

Creating an IndexedFuzzer is just like creating an IndexedDecoder:

fuzzEmailWithIdIndexer =
    succeed EmailWithId
        |> custom (fuzzer Fuzz.int)
        |> custom fuzzEmailIndexer
        |> custom (fuzzer <| Fuzz.map Just Fuzz.string)

I’m really grateful for your work on this, @dmy! It works great and you saved me many hours!