修改不可变子结构

Question

假设我有一个不可变的包装器：

template<class T>
struct immut {
  T const& get() const {return *state;}
  immut modify( std::function<T(T)> f ) const { return immut{f(*state)}; }
  immut(T in):state(std::make_shared<T>(std::move(in))){}
private:
  std::shared_ptr<T const> state;
};

如果我有一个 immut<Bob> b，我可以将一个 Bob(Bob) 操作变成可以替代我的 b.

的东西

template<class T>
std::function<immut<T>(immut<T>)> on_immut( std::function<void(T&)> f ){
  return [=](auto&&in){ return in.modify( [&](auto t){ f(t); return t; } ); };
}

所以如果 Bob 是 int x,y;，我可以将简单的可变代码 [](auto& b){ b.x++; } 变成 immut<Bob> 更新程序。

现在，如果 Bob 依次有 immut<Alice> 个成员，而后者又有 immut<Charlie> 个成员。

假设我有一个 Charlie 更新程序 void(Charlie&)。而且我知道我要更新的 Charlie 在哪里。在易变的土地上，它看起来像：

void update( Bob& b ){
  modify_charlie(b.a.c[77]);
}

我可能会把它分成：

template<class S, class M>
using get=std::function<M&(S&)>;
template<class X>
using update=std::function<void(X&)>;
template<class X>
using produce=std::function<X&()>;

void update( produce<Bob> b, get<Bob, Alice> a, get<Alice, Charlie> c, update<Charlie> u ){
  u(c(a(b())));
}

甚至去代数并有（伪代码）：

get<A,C> operator|(get<A,B>,get<B,C>);
update<A> operator|(get<A,B>,update<B>);
produce<B> operator|(produce<A>,get<A,B>);
void operator|(produce<A>, update<A>);

让我们根据需要将操作链接在一起。

void update( produce<Bob> b, get<Bob, Alice> a, get<Alice, Charlie> c, update<Charlie> u ){std::
  u(c(a(b())));
}

变成

b|a|c|u;

步骤可以在任何需要的地方缝合在一起。

immuts 的等价物是什么，它有名称吗？理想情况下，我希望这些步骤像在可变情况下一样独立但又可组合，天真 "leaf code" 在可变状态结构上。

Answer 1

What is the equivalent with immuts, and is there a name for it?

IDK 是否存在子状态操作的通用名称。但是在 Haskell 中，有一个 Lens 可以提供您想要的。

在 C++ 中，您可以将 lens 视为一对 getter 和 setter 函数，它们都只关注其直接子部分。然后有一个作曲家将两个镜头组合在一起，专注于结构的更深部分。

// lens for `A` field in `D`
template<class D, class A>
using get = std::function<A const &(D const &)>;

template<class D, class A>
using set = std::function<D(D const &, A)>;

template<class D, class A>
using lens = std::pair<get<D, A>, set<D, A>>;

// compose (D, A) lens with an inner (A, B) lens,
// return a (D, B) lens
template<class D, class A, class B>
lens<D, B>
lens_composer(lens<D, A> da, lens<A, B> ab) {
    auto abgetter = ab.first;
    auto absetter = ab.second;
    auto dagetter = da.first;
    auto dasetter = da.second;

    get<D, B> getter = [abgetter, dagetter]
        (D const &d) -> B const&
    {
        return abgetter(dagetter(d));
    };

    set<D, B> setter = [dagetter, absetter, dasetter]
        (D const &d, B newb) -> D
    {
        A const &a = dagetter(d);
        A newa = absetter(a, newb);
        return dasetter(d, newa);
    };

    return {getter, setter};
};

你可以这样写一个基本镜头：

struct Bob {
    immut<Alice> alice;
    immut<Anna>  anna;
};
auto bob_alice_lens
= lens<Bob, Alice> {
    [] (Bob const& b) -> Alice const & {
        return b.alice.get();
    },
    [] (Bob const& b, Alice newAlice) -> Bob {
        return { immut{newAlice}, b.anna };
    }
};

请注意，此过程可以通过宏自动执行。

那么如果Bob包含immut<Alice>，Alice包含immut<Charlie>，则可以写2个镜头（Bob到Alice和Alice到Charlie），Bob到Charlie镜头可以组成：

auto bob_charlie_lens = 
lens_composer(bob_alice_lens, alice_charlie_lens);

Live Demo

注意：

Below 是一个更完整的示例，具有线性内存增长 w.r.t 深度，没有类型擦除开销 (std::function)，并且具有完整的编译时类型检查。它还使用微距生成基本镜头。

#include <type_traits>
#include <utility>

template<class T>
using GetFromType = typename T::FromType;

template<class T>
using GetToType = typename T::ToType;

// `get` and `set` are fundamental operations for Lens,
// this Mixin will add utilities based on `get` and `set`
template<class Derived>
struct LensMixin {
    Derived &self() { return static_cast<Derived&>(*this); }

    // f has type: A& -> void
    template<class D, class Mutation>
    auto modify(D const &d, Mutation f)
    {
        auto a = self().get(d);
        f(a);
        return self().set(d, a);
    }
};

template<
    class Getter, class Setter,
    class D, class A
    >
struct SimpleLens : LensMixin<SimpleLens<Getter, Setter, D, A>> {
    static_assert(std::is_same<
            std::invoke_result_t<Getter, const D&>, const A&>{},
            "Getter should return const A& for (const D&)");

    static_assert(std::is_same<
            std::invoke_result_t<Setter, const D&, A>, D>{},
            "Setter should return D for (const D&, A)");
    using FromType = D;
    using ToType = A;

    SimpleLens(Getter getter, Setter setter)
        : getter(getter)
        , setter(setter)
    {}

    A const &get(D const &d) { return getter(d); }
    D set(D const &d, A newa) { return setter(d, newa); }
private:
    Getter getter;
    Setter setter;
};

template<
    class LensDA, class LensAB
    >
struct ComposedLens : LensMixin<ComposedLens<LensDA, LensAB>> {
    static_assert(std::is_same<
            GetToType<LensDA>, GetFromType<LensAB>
        >{}, "Cannot compose two Lens with wrong intermediate type");

    using FromType = GetFromType<LensDA>;
    using ToType = GetToType<LensAB>;

private:
    using intermediateType = GetToType<LensDA>;
    using D = FromType;
    using B = ToType;
    LensDA da;
    LensAB ab;
public:

    ComposedLens(LensDA da, LensAB ab) : da(da), ab(ab) {}

    B const &get(D const &d) { return ab.get(da.get(d)); }
    D set(D const &d, B newb) {
        const auto &a = da.get(d);
        auto newa = ab.set(a, newb);
        return da.set(d, newa);
    }
};

namespace detail {
    template<class LensDA, class LensAB>
    auto MakeComposedLens(LensDA da, LensAB ab) {
        return ComposedLens<LensDA, LensAB> { da, ab };
    }

    template<class D, class A, class Getter, class Setter>
    auto MakeSimpleLens(Getter getter, Setter setter)
    {
        return SimpleLens<Getter, Setter, D, A> {
            getter, setter
        };
    }
}

template<class LensDA, class LensAB>
auto lens_composer(LensDA da, LensAB ab) {
    return detail::MakeComposedLens (da, ab);
}


#include <memory>

template<class T>
struct immut {
  T const& get() const {return *state;}
  immut(T in):state(std::make_shared<T>(std::move(in))){}
private:
  std::shared_ptr<T const> state;
};

#define MAKE_SIMPLE_LENS(D, A, Aname)   \
    detail::MakeSimpleLens<D, A>(       \
        +[] (D const &d) -> A const & { \
            return d . Aname . get();   \
        },                              \
        +[] (D const &d, A newa) -> D { \
            D newd = d;                 \
            newd . Aname = newa;        \
            return newd;                \
        })




struct Charlie {
    int id = 0;
};

struct Alice{
    immut<Charlie> charlie;
};
struct Anna {};
struct Bob {
    immut<Alice> alice;
    immut<Anna>  anna;
};

auto alice_charlie_lens = MAKE_SIMPLE_LENS(Alice, Charlie, charlie);
auto bob_alice_lens     = MAKE_SIMPLE_LENS(Bob, Alice, alice);
auto bob_charlie_lens   = lens_composer(bob_alice_lens, alice_charlie_lens);

static_assert(std::is_same<GetFromType<decltype(bob_charlie_lens)>, Bob>{});
static_assert(std::is_same<GetToType<decltype(bob_charlie_lens)>, Charlie>{});

#include <iostream>

int main() {
    immut<Charlie> charlie{Charlie{77}};
    immut<Alice> alice{Alice{charlie}};
    immut<Anna>  anna{Anna{}};

    Bob bob{alice, anna};
    std::cout << "bob     -> anna: " << static_cast<void const*>(&bob.anna.get()) << "\n";
    std::cout << "bob     -> charlie: " << bob_charlie_lens.get(bob).id << "\n";

    // Bob newbob = bob_charlie_lens.set(bob, Charlie{148});
    Bob newbob = bob_charlie_lens.modify(bob, [] (auto &charlie) {
            charlie.id += (148 - 77);
            });
    std::cout << "new bob -> anna: " << static_cast<void const*>(&bob.anna.get()) << "\n";
    std::cout << "old bob -> charlie: " << bob_charlie_lens.get(bob).id << "\n";
    std::cout << "new bob -> charlie: " << bob_charlie_lens.get(newbob).id << "\n";
}

修改不可变子结构

Modifying immutable substructures

c++

monads

immutability

algebraic-data-types

c++17