immutable.cs

using System;

namespace Immutable
{
    enum Qux { Qux1, Qux2 }

    class Baz
    {
        public Baz(Qux qux)
        {
            Qux = qux;
        }

        public Qux Qux { get; }
    }

    class Bar
    {
        public Bar(Baz baz)
        {
            Baz = baz;
        }

        public Baz Baz { get; }
    }

    class Foo
    {
        public Foo(Bar bar)
        {
            Bar = bar;
        }

        public Bar Bar { get; }
    }

    static class Extensions
    {
        public static Foo WithBar(this Foo foo, Func<Bar, Bar> f) => new Foo(f(foo.Bar));
        public static Bar WithBaz(this Bar bar, Func<Baz, Baz> f) => new Bar(f(bar.Baz));
        public static Baz WithQux(this Baz bar, Func<Qux, Qux> f) => new Baz(f(bar.Qux));
    }

    static class Program
    {
        private static Foo SetQux(Foo foo, Qux qux) => foo.WithBar(bar => bar.WithBaz(baz => baz.WithQux(_ => qux)));

        public static void Main()
        {
            var it = new Foo(new Bar(new Baz(Qux.Qux1)));
            Console.WriteLine(it.Bar.Baz.Qux);

            var newIt = SetQux(it, Qux.Qux2);
            Console.WriteLine(newIt.Bar.Baz.Qux);
        }
    }
}

immutable2.cs

using System;

namespace Freeze
{
    // If we create a mutable "builder" type for each type
    // you don't have to create all the "With" methods (but you
    // have to duplicate all the public properties).
    
    public interface IFreezable<TImmutable>
    {
        TImmutable Freeze();
    }

    public interface IImmutable<TThis, TMutable>
        where TMutable : IFreezable<TThis>
    {
        TMutable GetBuilder();
    }

    public static class Extensions
    {
        public static TImmutable Update<TImmutable, TMutable>(this TImmutable immutable, Action<TMutable> updater)
            where TImmutable : IImmutable<TImmutable, TMutable>
            where TMutable : IFreezable<TImmutable>
        {
            var builder = immutable.GetBuilder();
            updater(builder);
            return builder.Freeze();
        }
    }

    class Foo : IImmutable<Foo, Foo.Builder>
    {
        public class Builder : IFreezable<Foo>
        {
            public int X { get; set; }

            public Bar.Builder Bar { get; set; }

            public Foo Freeze() => new Foo(X, Bar.Freeze());
        }

        public Foo(int x, Bar bar)
        {
            X = x;
            Bar = bar;
        }

        public int X { get; }

        public Bar Bar { get; }

        public Builder GetBuilder() => new Builder { X = X, Bar = Bar.GetBuilder() };
    }

    class Bar : IImmutable<Bar, Bar.Builder>
    {
        public class Builder : IFreezable<Bar>
        {
            public Baz.Builder Baz { get; set; }

            public Bar Freeze() => new Bar(Baz.Freeze());
        }

        public Bar(Baz baz)
        {
            Baz = baz;
        }

        public Baz Baz { get; }

        public Builder GetBuilder() => new Builder { Baz = Baz.GetBuilder() };
    }

    class Baz : IImmutable<Baz, Baz.Builder>
    {
        public class Builder : IFreezable<Baz>
        {
            public Qux Qux { get; set; }

            public Baz Freeze() => new Baz(Qux);
        }

        public Baz(Qux qux)
        {
            Qux = qux;
        }

        public Qux Qux { get; }

        public Builder GetBuilder() => new Builder { Qux = Qux };
    }

    enum Qux
    {
        Qux1,
        Qux2
    }

    class Program
    {
        static void Main(string[] args)
        {
            var foo = new Foo(1, new Bar(new Baz(Qux.Qux1)));
            Console.WriteLine(foo.Bar.Baz.Qux);

            // note that "Foo.Builder" is required in the next line - this is a bit ugly.
            // see next version for how this requirement can be removed.
            var foo2 = foo.Update((Foo.Builder f) => f.Bar.Baz.Qux = Qux.Qux2);
            Console.WriteLine(foo2.Bar.Baz.Qux);
        }
    }
}

immutable3.cs

using System;

namespace Freeze
{
    // Using an abstract class as base allows us to drop the interfaces.
    // Requiring a base class should be okay as the Update method would have a hard
    // time working with polymorphism!

    public abstract class Immutable<TThis, TBuilder>
        where TBuilder : Immutable<TThis, TBuilder>.BuilderBase
    {
        public abstract class BuilderBase
        {
            public abstract TThis Freeze();
        }

        public abstract TBuilder GetBuilder();

        public TThis Update(Action<TBuilder> updater)
        {
            var builder = GetBuilder();
            updater(builder);
            return builder.Freeze();
        }
    }

    class Foo : Immutable<Foo, Foo.Builder>
    {
        public sealed class Builder : BuilderBase
        {
            public int X { get; set; }

            public Bar.Builder Bar { get; set; }

            public override Foo Freeze() => new Foo(X, Bar.Freeze());
        }

        public Foo(int x, Bar bar)
        {
            X = x;
            Bar = bar;
        }

        public int X { get; }

        public Bar Bar { get; }

        public override Builder GetBuilder() => new Builder { X = X, Bar = Bar.GetBuilder() };
    }

    class Bar : Immutable<Bar, Bar.Builder>
    {
        public sealed class Builder : BuilderBase
        {
            public Baz.Builder Baz { get; set; }

            public override Bar Freeze() => new Bar(Baz.Freeze());
        }

        public Bar(Baz baz)
        {
            Baz = baz;
        }

        public Baz Baz { get; }

        public override Builder GetBuilder() => new Builder { Baz = Baz.GetBuilder() };
    }

    class Baz : Immutable<Baz, Baz.Builder>
    {
        public sealed class Builder : BuilderBase
        {
            public Qux Qux { get; set; }

            public override Baz Freeze() => new Baz(Qux);
        }

        public Baz(Qux qux)
        {
            Qux = qux;
        }

        public Qux Qux { get; }

        public override Builder GetBuilder() => new Builder { Qux = Qux };
    }

    enum Qux
    {
        Qux1,
        Qux2
    }

    class Program
    {
        static void Main(string[] args)
        {
            var foo = new Foo(1, new Bar(new Baz(Qux.Qux1)));
            Console.WriteLine(foo.Bar.Baz.Qux);

            var foo2 = foo.Update(f => f.Bar.Baz.Qux = Qux.Qux2);
            Console.WriteLine(foo2.Bar.Baz.Qux);
        }
    }
}