I'm not sure if this is what you're looking for, but vinyl + lens state monad combinators let you write something like this:
foo :: State (Rec Foo [B,C,F]) Bar
foo = ...
bar = State (Rec Foo [A,B,C,D,E,F]
bar = do
...
x <- zoom rsubset foo
...
rlens SA .= 3
...
Unfortunately Vinyl has O(n) lookup (unless it gets optimized away by sufficiently glorious haskell compiler, I guess, but I have no idea whether it actually can happen). But I'm not sure if the speed impact is noticeable, compared to using monad transformer stacks, for example.