Suppose I create a simple functional Domain-specific language (DSL) using an imperative language, in this case C++. Here is a simple implementation of a DSL that can has the notion of a simple value and operator (in this case the addition operator):

// some operator
template <typename LHS, typename RHS>
struct OpImpl
{
    Op(LHS lhs, RHS rhs) : mLhs(lhs), mRhs(rhs) {}
    auto operator()() const
    {
      return mLhs() + mRhs(); // let's say it's a non-trivial operation, and can't be optimised away but also has no side effects.
    }
    LHS mLhs;
    RHS mRhs;
};

template <typename LHS, typename RHS>
auto Op(LHS&& lhs, RHS&& rhs) { return Op<LHS, RHS>(lhs, rhs); }

struct Value
{
    Value(int value) : mValue(value) {}
    auto operator()() const
    {
        return mValue;
    }
    const int mValue;
};

Disregarding other problems with this, if I try to create a nested expression using this "language" I will very quickly end up with redundant leaf nodes:

int main()
{
    auto Res0 = Op(Value(1), Value(2)); // 1 + 2
    auto Res1 = Op(Res0, Res0); // (1 + 2) + (1 + 2)
    auto Res2 = Op(Res1, Res1); // ((1 + 2) + (1 + 2) + (1 + 2) + (1 + 2))
    auto Res3 = Op(Res2, Res2); // etc.
    auto Res4 = Op(Res3, Res3);
    auto Res5 = Op(Res4, Res4);
    auto Res6 = Op(Res5, Res5);
    auto Res7 = Op(Res6, Res6);
    auto Res8 = Op(Res7, Res7);
    auto Res9 = Op(Res8, Res8);
    auto Res10 = Op(Res9, Res9);
    auto Res11 = Op(Res10, Res10);
    auto Res12 = Op(Res11, Res11);
    auto Res13 = Op(Res12, Res12);
    auto Res14 = Op(Res13, Res13);
    auto Res15 = Op(Res14, Res14);
    auto Res16 = Op(Res15, Res15);
    auto Res17 = Op(Res16, Res16);
    auto Res18 = Op(Res17, Res17);
    auto Res19 = Op(Res18, Res18);
    auto Res20 = Op(Res19, Res19);
}

The above code in any normal language will have linear complexity on the number of "Res" depths (in this case 21), and presumably functional language implementations do as well.

However, in the above example, my program will call the () operator on the Value class 2^21 times. If Value is not trivial to calculate, this could make my program tremendously inefficient!

I can reduce the number of calls to Value by introducing a cache:

template <
struct OpImpl
{
    Op(LHS lhs, RHS rhs) : mLhs(lhs), mRhs(rhs) {}   
    auto operator()() const
    {
        // some unique identifier
        auto cacheIndex = findMyIndex(this) // this could be a typeid, etc.

        if (!cache.count(cacheIndex))
            cache[cacheIndex] = mLhs() + mRhs();
        return cache[cacheIndex];
    }

    LHS mLhs;
    RHS mRhs;
};

The above reduces the number of calls to the parenthesis operator of Value to 2 and the number of calls to OpImpl to 21. With some tweaking (figuring out the cache position at construction, using an efficient lookup, memory pools, etc.) we can probably make these lookups quite cheap, but we're still doing 21 lookups / pointer indirection for a series of operations that would be much more efficient in bespoke c++ or with a real functional language.

So, to get to my question; how do functional languages solve this problem, and, more importantly, how do I apply such a solution to the simple DSL example given above, such that the code exhibits a reasonable amount of efficiency?

Note that I am not asking about making the above algorithm perform more quickly, I want to find a better algorithm.