I was thinking about the applicative AST. I think that's a good solution, and perhaps if you're willing to explicitly compile it then you'll only need to pay once (and maybe even memoize it on later uses?)

There shouldn't be a problem with strictness and van Laarhoven lenses. The particular trouble is just writing the lenses in the first place:

    (def one [inj]
      (fn [p] 
        (fmap (fn [f] (pair f (snd p))) 
              (inj (fst p)))))

where did the `fmap` come from?