Best way to generate Unique IDs

[Hassan Hayat]

Hey there,

I was wondering what's the best way to generate Unique IDs in Elm.

My main problem is using them with records. I guess it's a JS habit of using object literals I have, but I find records to be the answer to everything :D

Imagine that you create objects as records and you want each to have a Unique ID. That said, some of your records are inside other records, and you want IDs there too. 

Also, I get into a habit (I dunno if it's good or bad) to declare a default record whenever I create a new record type.

So, when I have something like :

type alias Foo = {
  bar : Int,
  baz : String
}

 

I always like including something like :

foo : Foo
foo = {
  bar = 23,
  baz = "baz"
}
 

so that when I create new objects, I don't have to write every single property of foo and keep things nice and extensible:

fooFighter : Foo
fooFighter = { foo | baz <- "fighter"}
 

but if the Foo type had a field for UniqueIDs:

type alias Foo = {
  bar : Int,
  baz : String,
  id : Int
}

suddenly, my updates go wrong because they will share ids, which is bad.


So, my current solution is to do something like this: 

type alias UniqueID a = {a | id: Int}

type UniqueIDGenerator a = UniqueIDGenerator (Seed -> (UniqueID a, Seed))

generate : UniqueIDGenerator a -> Seed -> (UniqueID a, Seed)

and then batch all my calls to generate at some mystical "create" step.

This is suddenly not ideal, cuz I'm suddenly bouncing back and forth between a world with Unique IDs and a world without.

The upcoming Promise API will allow use to just steal this API from Haskell: http://hackage.haskell.org/package/base-4.3.1.0/docs/Data-Unique.html

type UniqueID = UniqueID Int

newUniqueID : Promise UniqueID

hash : UniqueID -> Int

This is sorta nicer, but now we're dealing in promises when a unique ID is something that usually just gets set once and that's it. The UniqueID is not intended to be mutable nor is it a promise... like, it's not like I want to "wait" for it like an HTTP request or a database query. But uniqueID so have something "global" about them. It's kinda the same problem with random numbers, but slightly nastier.



Any ideas? Are there already good solutions I'm not aware of?

Thanks,
Hassan Hayat

[Max Goldstein]

My best guess would be to use the Random library, generating integers in as wide a range as it allows.

It won't give you a true UUID - not enough bits - but it ought to get you off the ground. It uses the seed pattern that you described above.

[Raoul Duke]

please do not suggest things that are ethically wrong from an
algorithmic point of view. :-)

[Evan Czaplicki]

Hassan, can you explain the goal of this more clearly? Could be an X/Y problem.

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Hassan Hayat]

By the way, yes I do actually use the random library. I was just showing the idea behind it. Another solution could be just to start at 1 and increment....

Ok, I'll try to explain the goal more clearly. 

In my Civ-like game, I have loads of things/entities.

A Game has many Civilizations and a GameMap. A Civilization has many Cities. A City has many buildings and many units. A GameMap is a 2D grid of tiles. 

For numerous reasons, it would be convenient to have most of these things have "unique IDs" such that I may distinguish them. For example, telling one unit from another.

Another big example is how to deal with tiles. The problem of tiles has been discussed in a previous thread : https://groups.google.com/forum/#!searchin/elm-discuss/tiles/elm-discuss/VhT9CFeWBLc/YpZcdy5NMa8J

Basically, cities can "own" tiles. They can grow their borders to include more tiles and such gain wealth and other things from having these tiles. But, the tiles are all part of a "Map" (the 2D grid of tiles). Cities don't own the whole Map. 

One solution would be to have both the Map (as a property of the general "Game" object) and have a list of tiles as a property of the cities. The problem is that any "modification" made to a tile by a City must be duplicated in the Map. This is a duplication of memory and completely error prone. So, the idea is have the cities have a property which is a list of "tileIDs". This would imply that any "modification" or "update" must be made directly on the Map and the "tileID" can be used for querying (this tileID can be as simple the index of the tile for example). So, in essence, I can do the whole thing without Unique IDs, but I did wonder how would I do it with? Could I make every "thing" or "entity" in my game have a "uniqueID"? How would that be acheived? 

This is what has led me to the above question and exploration. Unique IDs are used in loads of settings (databases being a big one). So, I was thinking, how could it be done in Elm?


Now, that said, a seperate question came to mind:

It would be cool if I could get the ID simply by doing "thing.id". 

Like, somehow, if I had a type:

type alias Object = {
  id : ID,
  a : A,
  b : B
}

and I had another type: 

type alias NestedObject = {
  object : Object,
  id : ID,
  c : C
}

I could generate their "IDs" easily (syntactically easily I mean)


I have this habit of creating default "objects" whenever I create a "record type". It makes my APIs easier to use. The problem is that I can't just do:

object1 : Object
object1 = {
  id = generateID,
  ...
}

object2 : Object
object2 = {
  id = generateID,
  ...
}

and expect object1.id to be different from object2.id. Elm is all immutable and that's not possible. 

So, I tried looking for ways.

I realized that the problem of generating Random numbers is a very similar problem. So I took a cue from it and used Extensible types to get what I want. 
Then I went snooping in the Haskell world to see how things are done. They use the IO type, which is kinda like the upcoming Promise type. So, I thought, "hey, that could work".
And then I thought of asking you guys if you have already had this issue to see how you have dealt with it or if you have any ideas on how to do it. Perhaps there's a better solution that I haven't thought of.

I hope to have clarified things. I am sorry, I have probably unconsciously mixed in different questions into one but I was thinking about the whole thing as a unit. Like, the overarching question seemed to me: How best to deal with uniquely identified objects generally? How to deal with objects with an ID as a property? How to deal with objects with an ID as a property and properties who are themselves objects with IDs and so on... How to all this while staying pure an immutable and remaining usable?

If things are still unclear, I'd be glad to continue to clarify things. Again, I'm really sorry with the confusion. While writing my question originally, I had like a million thoughts on the topic going through my head at once and didn't manage to crystallize them appropriately.

[Peter Damoc]

Evan, I think I'm reading your question wrongly.
Are you really asking what is the use (goal) of UUID support in a language?

--

There is NO FATE, we are the creators.
blog: http://damoc.ro/

[Rehno Lindeque]

I hope it's not too rude, but I thought I might suggest a bit of a rethink that doesn't require UUIDs. The current model comes off very object oriented to me, the need for ids especially raises some red flags. I've found that sometimes FP will tend to encourage you to reverse ownership, similar to the sort of thing you'd do in a relational database. I.e. I think about each of your ownership relations and decide whether flipping the arrow in the other direction will simplify things...? This can be helpful for thinking about your game globally, as transformations over collections of things. E.g. perhaps something like this...

type alias GeographyIndex = (Int,Int)
type alias CivilizationIndex = Int

type alias Geography a : Array (Array a)
type alias Tile =
{ owner : Maybe CityIndex
, terrain : Terrain
, ...
}
type alias Entities =
{ allegiance : CivilizationIndex
, ...
} 

type alias City =
{ allegiance   : CivilizationIndex 

, construction : Float             -- percentage completed

, building     : Array Building    -- I didn't flip the ownership here because presumably 

                                   -- cities are created and destroyed dynamically and 

                                   -- buildings would never defect

}

type alias Building =
{ position : GeographyIndex
, ...
} 

type alias Civilization =
{ name : String
}

type alias State =
{ world : Geography Tile
, civilizations : List Civilization
, entities : List Entity
, buildings : List Building
, dt : TimeDelta
}

 

where the stepping functions for the game might look something like this?

update : TimeDelta -> State -> State

Entity.update : State ->  -> Entity -> Entity

Building.update : State -> Building -> Building

etc...

Hope that helps.

[Rehno Lindeque]

Also, should ids be necessary it's unlikely that they really need to include any randomness (unless they're generated on different computers and should not conflict). You could think of ids as simply being auto-incremented integer along with a generator that gets passed into every constructor:

object1 : IdGenerator -> (Object, IdGenerator)

object1 g =

  let (newId, g') = generateId g

  in ( { id = newId,

       , ...
       }

     , g'

     )

The abstract type of this function is sometimes referred to as State in Haskell, not sure about Elm, but I'm guessing it's probably similar to how Random works.

[Evan Czaplicki]

Hassan, no need to apologize!

Peter, yeah, I think my question came out wrong. I'm curious the general thing you want to do. It sounds like there was a general goal "make game X" and that turned into "I need to solve problem Y" and now we are here discussing Y. But maybe if we go back to X we'll see that Z is really the right way to solve it. Perhaps that'll let us find some great Z rather than trying to hack Y together. I think this is what Rehno is getting at.

Sorry for the confusion on this one!

--

[Hassan Hayat]

Cool, Rehno. Thanks. I'll definitely try treating objects as if a relational database.

[Hassan Hayat]

And yeah, I have considered ids as simply numbers that get incremented. I guess my problem is that I was thinking about my models too much in an object oriented way. I guess I still have a long ways to master the art of functional programming. ;) 

But, I feel like the question of dealing with Unique IDs will come back later on. The day Promises get released, I propose we hack together something like Haskell's Data.Unique. This should hopefully solve most future problems regarding Unique IDs.

[Rehno Lindeque]

I'm really looking forward to seeing the end result of this, civ is an old favourite of mine!

[Hassan Hayat]

Thanks. I'm also looking forward to seeing the end result. I'm starting to realize that I've picked a big target but I'm also starting to realize that it's a very good target to pick. Hidden beneath this project is also the question of how to model things with functional programming that are usually done with object oriented programming. My secret hope is that the solution I arrive would be very modular, flexible and would kinda show how to do large apps that require this kind of modeling. You guys have been helpful, now I have tons of ideas of how to do things--ideas I would never have had otherwise.