Concept for "equal but unknown"

Hello all, there is a problem which popped up a number of times recently and I wondered if there is a general concept to tackle this kind of problems. It goes like this: I book a hotel room. At this time it becomes known that the hotel has one fewer room available, but it is not known which room it is. Likewise I know, that I have a reservation for "a room", but I don't know which one it is. It is however known, that the room in my reservation is the same room the hotel has removed from the list of available rooms. Another example: In air-cargo the cargo company has reserverd space in an aircraft for two containers. One for high-priority parcels and one for low-priority parcels. In the cargo hub, they plan to pack these two containers. At this point in time it is only known that there will be two containers one labelled "high-prio" and the other labelled "low-prio" but their physical identity is not known. Only when you actually do the packing you have a physical container at hand, which has identity. At this moment it becomes clear to which physical containers the reservations refer to and which physical containers are used for packing. I think I can handle this in an imparative style using an extra indirection (think pointers), though even there I would be happy if someone told me something like "this is an example of covariant unification" or something like this. But in haskell I cannot see a solution at all? So: how can I express that two things are equal to each other without knowing the exact value and how do I manage to make both assume a value once one of them becomes known. Do these kind of problems have a name?

how can I express that two things are equal to each other without knowing the exact value and
how do I manage to make both assume a value once one of them becomes known.
I'm sure there are fancier ways to express such things, but you could use a placeholder (an Integer for instance, wrapped in a newtype) for the room reservation, together with a Map from Integer to Room to look up the room assigned to each reservation. As long as no room is assigned to a reservation number, a lookup in the map yields Nothing. Once a room is assigned, a lookup yields the room. All this should probably be wrapped up in the State Monad (the Map with the reservations being the state), so you don't have to carry around the Map explicitly. Hope this is helps.

Am 10/02/2015 um 04:02 PM schrieb Stefan Höck:
how can I express that two things are equal to each other without knowing the exact value and
how do I manage to make both assume a value once one of them becomes known.
I'm sure there are fancier ways to express such things, but you could use a placeholder (an Integer for instance, wrapped in a newtype) for the room reservation, together with a Map from Integer to Room to look up the room assigned to each reservation. As long as no room is assigned to a reservation number, a lookup in the map yields Nothing. Once a room is assigned, a lookup yields the room. All this should probably be wrapped up in the State Monad (the Map with the reservations being the state), so you don't have to carry around the Map explicitly.
Yes, this is what I would have done in imperative code and from your suggestion I understand that in haskell I'll have to carry that map around. So far so good. Here is another thought: In math it is terribly easy to express what I am after a simple "x=y" states that x and y are equal, but unknown. As soon as I add x=25, there is no more choice on the value of y. I guess I am after values which become more and more defined in the course of computation.

Hello, Do you mean something like variable unification in Prolog or Oz? Maybe something like this could help you: https://hackage.haskell.org/package/monad-unify-0.2.2/docs/Control-Monad-Uni... or https://hackage.haskell.org/package/unification-fd Disclaimer: I've never used either of those packages. Best regards, Marcin Mrotek

Am 10/02/2015 um 04:45 PM schrieb Marcin Mrotek:
Hello,
Do you mean something like variable unification in Prolog or Oz? Maybe something like this could help you: https://hackage.haskell.org/package/monad-unify-0.2.2/docs/Control-Monad-Uni... or https://hackage.haskell.org/package/unification-fd Disclaimer: I've never used either of those packages.
Well it was no coincidence that I invented the joke term "covariant unification", because I had a hunch that this has something to do with unification. Thanks for the links.

On Fri, Oct 2, 2015 at 9:37 PM, martin
I guess I am after values which become more and more defined in the course of computation.
One way to simulate incremental binding is by extending with multiple Maybes: Nothing would mean 'no reservation' Just Nothing -> 'reservation but unassigned room' Just (Room 123) -> 'reservation with assigned room' The type used is Maybe (Maybe Room). -- Kim-Ee

In the context of logic, the usual way to capture these sorts of things is to introduce some notion of an event/eventuality which you can use to index everything by. Then you can say that there exists some index (e.g., hotel reservation) with such and such properties (e.g., consumes a free room, provides the same room to the reservation holder, etc). The connection between this semantic model and how you write your program is, of course, up to you. Both the pointer-indirection approach and the unification-variable approach can be seen as ways of implementing this semantics. As for a general concept, you may want to look into "constraint satisfaction"/"constraint programming" (e.g., ECLPS Prolog http://eclipseclp.org). The big idea here is that you can give each variable a domain of possible values (which need not be the same for all variables), and then you introduce a set of constraints on what those values can be. This allows for capturing things like "I have three reservations X, Y, and Z for three rooms A, B, and C such that no room is booked twice and no reservation takes more than one room". -- Live well, ~wren
participants (5)
-
Kim-Ee Yeoh
-
Marcin Mrotek
-
martin
-
Stefan Höck
-
wren romano