They're a good compromise between mutable and fully immutable data structures? "Oh, that? It was always there, we just didn't know about it..." Easy example: Incrementally appending to a list of conses without reversing it in the process.
Better example of working with partial information: Constraint programming.
Better example of working with partial information: Constraint programming.