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

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


  (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)

1 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.

  • Assuming data isn't hierarchical (or rather the hierarchy varies wildly on the context for same objects), AND the operation isn't identical (i.e. the action on the light is unknown without knowing exact instance of the switch), wouldn't that force to make a pass for each switch, and make the complexity O(n^2)? In which case, is it still worth doing it in immutable way? Dec 25, 2018 at 0:41
  • 1
    Second point seems good, but not exactly applicable at least my case, where each element is actually a set of components of various types, so it isn't obvious how to split them into different lists. Maybe have lists by component type that the element has inside (and so element belongs to as many lists, as how many types of components it contains)? But that sounds like it'd introduce enormous headache with making sure it's updated across all lists it belongs to. Dec 25, 2018 at 0:45
  • I'm not satisfied with the answer, because it isn't performant (though maybe it's literally impossible to make it better). I'm not accepting your answer, but I award the bounty for your effort, just so it doesn't disappear into the void. Dec 31, 2018 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.