Functional programming -- changing correlating elements during list mapping

Question

Consider I have a list. I want to iterate over it and map it's elements -- but the mapping might also require to change others than the element I'm currently iterating over.

Let's say I have a switch (has a field of list of light id's it controls, and bool field if its switched on) and light (has an id field, and a bool field if its shining) structure types defined. I want to update list by turning off all switches, and correspondingly turning off all lights related to them. E.g. I'd want to perform mapping, so that list like this

(list
  (light 'd #t)
  (switch '(c) #f)
  (light 'a #t)
  ...
  (switch '(a b) #t)
  ...
  (light 'b #t)
  (light 'c #f))

becomes

(list
  (light 'd #t)
  (switch '(c) #f)
  (light 'a #f)
  ...
  (switch '(a b) #f)
  ...
  (light 'b #f)
  (light 'c #f))

This is a trivial example, but in actual use the list could be big, the predicate of which exactly other elements should be changed not obvious, and the coupling might depend on the function -- i.e. light might be depending not from a switch, but from some other element in the different context.

What's the best approach in functional, immutable way?

---

I guess turning lights all off is bad example, as it makes it too trivial. I'm looking for a more general solution, where actions may be different across elements depending on their (and their controller's) data.

The initial and result items must be in a flat structure (though I'm not sure how many there are besides lists / vectors)

The solution shouldn't assume that elements are easy to categorize (e.g. because categorization wildly varies depending on the context the same data is used)

Answer 1

Part of what you're doing is basically some kind of join (think sql or relational model) to query for some subset of data that is stored in a flat list.

You also have a data structure that is not particularly friendly toward doing this join.

Here are some options:

• If you want to keep the flat lists with no particular ordering among elements, make two passes over the list:  The first pass over the list generates a new list — of id's of lights to turn off — and the second pass (the map) over the original list (also takes the intermediate id list) and turns them off.

• Separate items by their type into different lists.  The advantage here is that lists (e.g. of switches) will be smaller than the whole list was before, which can be beneficial for a very large data set.  Then apply something from above.

• If the data is strictly hierarchical (a light belongs to only one switch), then store it that way to make the joins super simple.  For a list data structure, this means (as needed) storing lists within lists.

• If the data is partially hierarchical, e.g. a light belongs to a set of switches (e.g. for three-way switches), then create a type or structure that represents a set of related switches, which then holds the switches & the lights — such a type could support modeling with hierarchy.