Comment by pwm

I would love to read more about all this, especially how overlays came from "object-oriented" programming. To me, the interesting part is their self-referential nature, for which lazy eval is indeed a great fit!

For anyone interested, this is how I'd illustrate Nix's overlays in Haskell (I know I know, I'm using one obscure lang to explain another...):

  data Attr a = Leaf a | Node (AttrSet a)
    deriving stock (Show, Functor)

  newtype AttrSet a = AttrSet (HashMap Text (Attr a))
    deriving stock (Show, Functor)
    deriving newtype (Semigroup, Monoid)

  type Overlay a = AttrSet a -> AttrSet a -> AttrSet a

  apply :: forall a. [Overlay a] -> AttrSet a -> AttrSet a
  apply overlays attrSet = fix go
    where
      go :: AttrSet a -> AttrSet a
      go final =
        let fs = map (\overlay -> overlay final) overlays
        in foldr (\f as -> f as <> as) attrSet fs

Which uses fix to tie the knot, so that each overlay has access to the final result of applying all overlays. To illustrate, if we do:

  find :: AttrSet a -> Text -> Maybe (Attr a)
  find (AttrSet m) k = HMap.lookup k m

  set :: AttrSet a -> Text -> Attr a -> AttrSet a
  set (AttrSet m) k v = AttrSet $ HMap.insert k v m

  overlayed =
    apply
      [ \final prev -> set prev "a" $ maybe (Leaf 0) (fmap (* 2)) (find final "b"),
        \_final prev -> set prev "b" $ Leaf 2
      ]
      (AttrSet $ HMap.fromList [("a", Leaf 1), ("b", Leaf 1)])

we get:

  λ overlayed
  AttrSet (fromList [("a",Leaf 4),("b",Leaf 2)])

Note that "a" is 4, not 2. Even though the "a = 2 * b" overlay was applied before the "b = 2" overlay, it had access to the final value of "b." The order of overlays still matters (it's right-to-left in my example tnx for foldr). For example, if I were to add another "b = 3" overlay in the middle, then "a" would be 6, not 4 (and if I add it to the end instead then "a" would stay 4).