Здравствуйте, Sinclair, Вы писали:

V>>Если тебе интересно закрыть эту тему раз и навсегда — распишу весь код целиком.
S>Да, было бы интересно. Брать прямо словарь не обязательно — там много нюансов. Можно использовать какую-то более простую структуру.
S>Но, сдаётся мне, что иммутабельность будет там обеспечена дизайном типа, а не ключевым словом const.

Ключевое слово const даст гарантии сильнее "вербальных соглашений", которые в реальной жизни не обеспечиваются ничем, кроме добросовестности программиста. ))
Даже правильно спроектированный под конкретную задачу тип затем может быть поломан из-за невнимательности, при добавлении мутабельных методов.

Общая идея при конструировании иммутабельных типов от неиммутабельных с использованием паттерна Decorator — это сочетания конструктора перемещения с константным хранением перемещённых данных.

template<typename T>
class ImmutableValue {
    const T value_;

public:
    ImmutableValue(T && value) : value_(value) {}

Добавим делегирующие операторы сравнения для ключей словарей на основе дерева:

    bool operator==(const ImmutableValue<T> & other) const {
        return value_ == other.value_;
    }

    bool operator!=(const ImmutableValue<T> & other) const {
        return value_ != other.value_;
    }
    

    bool operator<(const ImmutableValue<T> & other) const {
        return value_ < other.value_;
    }

Добавим делегирущее вычисление хеша для ключей хеш-таблиц:

    operator const T &() const { return value_; }
};

template<typename T>
struct std::hash<ImmutableValue<T>> {
    size_t operator()(const ImmutableValue<T> & ikey) const {
        return hash<T>()(ikey);
    }    
};

Проверяем:

template<typename T>
size_t hash_value(const T & value) {
    return std::hash<T>()(value);
}

int main() {
    ImmutableKey<int> i = 42;
    std::cout << hash_value(i) << endl;

    return 0;
}

Для оберток типов-отображений (назовём ImmutableMap) общая структура типа будет такая же.
По твоей просьбе опускаю часть контракта (typedef-ы), вот целевой делегирующий метод:

const TValue & operator[](const TKey & key) const { return map_[key]; }

Далее в своём коде используешь шаблонный ImmutableMap.


S>То есть в лучшем случае вы получите решение, изоморфное System.Collections.Immutable.

В С++ ключевое слово const применимо так же к полям структур/классов.
Такие поля могут быть инициализированы только в конструкторе.
Это аналог readonly в C#.

И зря ты ссылаешься на Collections.Immutable.
Это не столько про саму иммутабельность, сколько про специальные алгоритмы на иммутабельных графах и списках.
Соответственно, ценностью этого раздела библиотеки является уже готовая функциональность, а не какие-то там гарантии.
(никаких гарантий та система типов не даёт)

Для сравнения, в С++ можно расписать аналогичную функциональность с "железобетонными" гарантиями иммутабельности.

Основные пляски вокруг иммутабельности в ФП, насколько я на них натыкался, они происходят не из-за агоритмов навроде Collections.Immutable (это лишь узкий частный случай), а из-за более широкой задачи — из-за статической и динамической альфа-бета-эта-редукции в процессе компиляции и исполнения программ.

Смотрим, что происходит при частичном связывании аргументов для некоей ф-ии/лямбд:

Func<double, double, double> fn1 = (x, y) => sin(x) + sin(y);
Func<double, double> fn2 = (x) => fn1(x, Math.Pi);

В C# после связывания, тело fn2 будет честно вызывать тело fn1, где снова и снова будет вызываться sin(Math.Pi).

В функциональных языках есть принципиальная возможность бета-эта-редуцировать не только в compile-time, но и в рантайме при связывании переменных.
В Хаскеле это делается через мемоизацию ленивых вычислений, что является достаточно убогой реализацией, ес-но — обслуживается структура из флага и поля для целевого значения, страдает поток вычислений в стеке и на конвейере проца.

В идеале предпочтительна трансформация самого тела fn2 в рантайм, т.е. порождение редуцированного кода на-лету (например, в параллельном потоке), т.е. целевой код может вызывать некоторое время нередуцированную fn, пока в фоне из ее тела не породят оптимизированный редуцированный вариант, а далее тело подменяется безопасно на лету опять же из-за природы иммутабельности всего и вся.

Для данного выражения имеем sin(Math.Pi)==0, тогда fn2=(x)=>sin(x), тогда через эта-преобразование вызовы fn2(x) заменяются на вызовы просто sin(x).
В С++ подобное редуцирование выполняется лишь для констант времени компиляции и только на некую ограниченную грубину распространения констант.

Вдогонку, возвращаясь к иммутабельным графам — распространение констант (связывание термов) возможно не только в тривиальных случаях, но и по всем данным.
Вплоть до подмены и стирания типов (это про альфа-преобразование — идентично описанные с точностью до "раскрытия скобок" термы-типы можно считать одинаковыми "унутре").
Вплоть до того, что целые куски таких иммутабельных графов, по которым бегает некий вычислитель, могут подменяться просто на значение. ))