Стандартный заголовок algorithm предоставляет определения min, max и minmax (возвращает std::pair). Итак, как выглядит объявление, например, базового варианта std::max?

template <class T>
const T& max(const T& a, const T& b);

Недостатки этого объявления:

• одинаковый тип a и b — наиболее раздражающий недостаток. Например, что-нибудь безобидное вроде max(vec.size(), 100) уже не компилируется, потому что 100 имеет тип int, а не size_t;
• только два параметра, поэтому max(a, b, c) придётся оформить как max(a, max(b, c));
• передача по const-ссылке:
  • для переменных a и b невозможно написать max(a, b) = c;
  • невозможна перемещающая семантика для rvalue: auto v = max(compute_vector1(), compute_vector2()) — всегда копирование;
  • иногда возникает проблема с порождением оптимального кода для значений простых типов.

Что до недостатка 2, то C++2011 предоставляет новые варианты, принимающие initializer_list:

template <class T>
T max(std::initializer_list<T> ilist);

Теоретически такой вариант ликвидирует все недостатки, в том числе, может предоставлять перемещающую семантику, но я не изучал данный вопрос подробно (в msvc2013 выполняется копирование).

Рассмотрим недостаток 1. Простое определение для двух разных типов вызывает затруднение в месте описания возвращаемого типа. C++2014 мог бы позволить написать просто

template <class U, class V> inline
auto max(U u, V v)
{ return u < v? v: u; }

В C++2011 придётся прибегнуть к decltype:

template <class U, class V> inline
auto max(U u, V v)
  -> decltype(u < v? v: u)
{ return u < v? v: u; }

или воспользоваться метафункцией std::common_type из type_traits (также доступна в варианте Boost для ряда старых компиляторов):

template <class U, class V> inline
typename std::common_type<U, V>::type
max(U u, V v)
{ return u < v? v: u; }

Попробуем обобщить данный код, используя универсальные ссылки (std::forward из memory):

template <class U, class V> inline
typename std::common_type<U, V>::type
max(U &&u, V &&v)
{
  return u < v? std::forward<V>(v): std::forward<U>(u);
}

К сожалению, код

int a = 1, b = 2;
max(a, b) = 3;

не компилируется, потому что common_type убирает ссылки (возвращаемый тип данного варианта max будет int, а не int&). Вероятно, простейший вариант исправить этот недостаток — реализовать объединение типов с помощью оператора ?: (сохраняющего ссылочные типы).

template <class U, class V> inline
auto max(U &&u, V &&v)
  -> decltype(u < v? std::forward<V>(v): std::forward<U>(u))
{
  return u < v? std::forward<V>(v): std::forward<U>(u);
}

Обобщим это определение на произвольное число параметров.

template <class U, class V, class ...Tail> inline
auto max(U &&u, V &&v, Tail&&... tail)
  -> decltype(max(std::forward<U>(u),
       max(std::forward<V>(v), std::forward<Tail>(tail)...)))
{
  return max(std::forward<U>(u),
         max(std::forward<V>(v), std::forward<Tail>(tail)...));
}

К сожалению, этот код не компилируется (при попытке вычислить max(1, 2, 3, 4), например) компилятором g++ (хотя компилируется msvc2013). Проблема в рекурсивной зависимости вывода типа — при вычислении max от 4 аргументов вариант для 3-х ещё не сгенерирован. Поэтому желательно отделить вычисление возвращаемого типа в метафункцию.

При использовании имён max/min вместе с объектами стандартных классов возможна «кража функций» (function hijacking) механизмом ADL (а то и срабатывание макросов max и min), поэтому я буду использовать (пусть и непривычные) имена maxi и mini, заведомо не конфликтующие со стандартными определениями. Итак, на примере минимума:

template <class...>
struct commonref_type {};

template <class U>
struct commonref_type<U>
{
  using type = U;
};

template <class U, class V>
struct commonref_type<U, V>
{
private:
  static U make_u();
  static V make_v();
  static bool dummy_condition();

public:
  using type = decltype(dummy_condition()? make_u() : make_v());
};

template <class U, class Head, class ...Tail>
struct commonref_type<U, Head, Tail...>
{
  using type = typename
    commonref_type<U, typename
    commonref_type<Head, Tail...>::type>::type;
};


template <class U, class V> inline
typename commonref_type<U, V>::type
mini(U &&u, V &&v)
{
  return v < u? std::forward<V>(v) : std::forward<U>(u);
}

template <class U, class V, class ...Tail> inline
typename commonref_type<U, V, Tail...>::type
mini(U &&u, V &&v, Tail&&... tail)
{
  return mini(std::forward<U>(u),
         mini(std::forward<V>(v), std::forward<Tail>(tail)...));
}

Формат, позволяющий передать произвольное количество разнотипных параметров, закрывает возможность с помощью механизма перегрузки функций добавить варианты, принимающие произвольный компаратор (такие есть у стандартных min и max). Но ничто не мешает дать другие имена, например, minc и maxc (от comparator). В отличие от стандартных вариантов, здесь будем передавать компаратор первым параметром.

template <class Comp, class U, class V> inline
typename commonref_type<U, V>::type
minc(Comp &&comp, U &&u, V &&v)
{
  return comp(v, u)? std::forward<V>(v) : std::forward<U>(u);
}

template <class Comp, class U, class V, class ...Tail> inline
typename commonref_type<U, V, Tail...>::type
minc(Comp &&comp, U &&u, V &&v, Tail&&... tail)
{
  return minc(comp, std::forward<U>(u),
         minc(comp, std::forward<V>(v), std::forward<Tail>(tail)...));
}

Последнее, с чем осталось разобраться — реализация «одновременного» поиска минимума и максимума. Следуя стандартному определению, будем возвращать пару (результат min, результат max) [std::tuple].

template <class ...Types>
struct minmax_result
{
  using part = typename commonref_type<Types...>::type;
  using type = std::tuple<part, part>;
};

Корректная реализация функций одновременного выбора минимума и максимума требует большого внимания к деталям. Моя версия:

template <class U, class V> inline
typename minmax_result<U, V>::type
minmaxi(U &&u, V &&v)
{
  using RT = typename minmax_result<U, V>::type;
  return v < u?
    RT(std::forward<V>(v), std::forward<U>(u))
  : RT(std::forward<U>(u), std::forward<V>(v));
}

template <class U, class V, class ...Tail> inline
typename minmax_result<U, V, Tail...>::type
minmaxi(U &&u, V &&v, Tail&&... tail)
{
  using RT = typename minmax_result<U, V, Tail...>::type;
  using R = typename commonref_type<V, Tail...>::type;
  auto tail_result =
    minmaxi(std::forward<V>(v), std::forward<Tail>(tail)...);
  auto &p0 = std::get<0>(tail_result),
       &p1 = std::get<1>(tail_result);
  return u < p1?
        (p0 < u?
             RT(std::forward<R>(p0), std::forward<R>(p1))
           : RT(std::forward<U>(u),  std::forward<R>(p1)))
           : RT(std::forward<R>(p0), std::forward<U>(u));
}

Текущий вариант реализации целиком.

Общее определение: функции, вычисляемые во время компиляции, в том числе, позволяющие вычислять типы.

Механизм шаблонов C++ является чистым функциональным языком (с громоздким синтаксисом), выражения на котором вычисляются во время компиляции, поэтому основной метод реализации метафункций опирается на механизм шаблонов и (частичной) специализации. В C++2011 появился второй метод: на основе constexpr, здесь он не рассматривается.

Я буду выписывать «определения» в псевдокоде, напоминающем Haskell, а затем приводить аналог на C++.

Связывание имени с константой

let x = y
// x -- новое имя для значения y

// применительно к типам в C++
// C++1998
typedef y x;

// C++2011
using x = y;

Вариант 1

Пусть f принимает тип и возвращает тип.

Определение

f :: type -> type
f x = ...

template <class x> class f { ... };

Применение

f x  // или
f(x) // или
(f x)

f<x> // C++

Функции высших порядков

f :: (type -> type) -> type
f x = ...

template <template <class> x> class f { ... };

Достоинство: краткость синтаксиса применения.

Недостатки:

• нельзя сопоставить уже существующие типы (например, нельзя выразить определение f int = float);
• неудобно использовать функции высших порядков.

Вариант 2

Прообраз введён стандартной библиотекой C++, использующей зависимые имена в шаблонах (например, в std::unary_function, классах характеристик std::char_traits, std::iterator_traits, контейнерах).
Популяризован библиотеками Boost.MPL, Boost.TypeTraits (последняя вошла в стандарт C++2011).

Определение

f :: type -> type
f x = expr

template <class x> struct f
{
  typedef expr type;
};

Применение

f x // f(x)

typename f<x>::type // C++

Достоинства:

• можно привязать любой тип;
• можно задать мультифункцию (несколько зависимых имён);
• можно вычислять не только типы, но и значения (традиционно используется вложенное имя value):

factorial :: unsigned -> unsigned
factorial n = n * factorial (n - 1)
factorial 0 = 1

template <unsigned n> struct factorial
{
  enum { value = n * factorial<n - 1>::value };
};

template <> struct factorial<0> { enum { value = 1u }; };

Другой классический пример такого рода: числа Фибоначчи.

• можно задавать через наследование (используется std::conditional из type_traits):

uint :: unsigned -> type
uint bits = if bits < 9  then uint8_t  else
            if bits < 17 then uint16_t else
            if bits < 33 then uint32_t else
            uint64_t ;

template <unsigned bits> struct uint
  : conditional<(bits < 9),  uint8_t,  typename
    conditional<(bits < 17), uint16_t, typename
    conditional<(bits < 33), uint32_t,
    uint64_t >::type>::type> {};

Недостатки:

• длинный синтаксис применения (причём typename требуется в контексте определения шаблона при использовании имён, зависящих от параметров шаблона, но запрещено в противном случае);
• неудобно передавать в функции высшего порядка.

Замечание
С++2011 позволяет сократить синтаксис применения с помощью template-using объявления:

template <unsigned bits> using uint_t = typename uint<bits>::type;
uint_t<19> counter; // OK

Данный подход применяется в type_traits C++2014.

Замыкания и карринг

mul a b = a * b
mul5 = mul 5
thirty = mul5 6

Карринг в C++ напрямую не поддерживается. Его можно имитировать, разделив параметры шаблона.

template <int a>
struct mul
{
  template <int b>
  struct curried { enum { value = a * b }; };
};

using mul5 = mul<5>;
const auto thirty = mul5::curried<6>::value;

Обработка списков (C++2011 variadic templates)

len :: [type] -> int
len x:xs = 1 + len xs
len [] = 0

template <class ...xs>
struct len {};

template <class x, class ...xs>
struct len<x, xs...> { enum { value = 1 + len<xs...>::value }; };

template <>
struct len<> { enum { value = 0 }; };

Использование одновременно значений и типов в качестве параметров может быть затруднено отсутствием перегрузки метафункций. Поэтому для целочисленных типов в type_traits введена обёртка integral_constant (увы, писать выражения с помощью обычных арифметических и логических операций становится невозможно). Определим factorial на её основе (вариант с «хвостовой» рекурсией).

factorial n f = factorial (n - 1) (n * f)
factorial 0 f = f

template <uint64_t n>
using Uint = integral_constant<uint64_t, n>;

using Zero = Uint<0>;
using One = Uint<1>;

template <class N, class M>
struct Sub
  : Uint<N::value - M::value> {};

template <class N, class M>
struct Mul
  : Uint<N::value * M::value> {};

template <class N, class F = One>
struct factorial
  : factorial<Sub<N, One>, Mul<F, N>> {};

template <class F>
struct factorial<Zero, F>
  : F {};

Увы, приведённый код не компилируется. Дело в том, что подстановка шаблонов выполняется немедленно, ленивые вычисления для типов не используются, поэтому компилятор не способен «дойти» до template < class F > struct factorial. Следующий вариант также не будет компилироваться:

template <class N, class F = One>
struct factorial
{
  using base = factorial<Sub<N, One>, Mul<F, N>>;
  using type = typename base::type;
  enum { value = base::value };
};

Впрочем, обойти эту проблему можно, сразу включив условие в определение:

template <class N, class F = One>
struct factorial
  : conditional<N::value != 0,
      factorial<Sub<N, One>, Mul<N, F>>,
      F>::type {};

Вариант 3

Отделение имени от параметров шаблона с помощью вложенных определений. Первый известный мне подобный пример — стандартные аллокаторы C++1998 (rebind). Также применяется в Boost.MPL.

Определение

f x = expr

struct f
{
  template <class T> struct apply { typedef expr type };
};

Применение

f x

typename f::template apply<x>::type

Достоинства:

• все из варианта 2;
• удобно передавать в функции высшего порядка (универсальность: достаточно оперировать именами метафункций, являющимися обычными типами, а не шаблонами), в частности, такую метафункцию можно передать саму себе в качестве параметра;

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

Перечисленные варианты могут быть скомбинированы ради удобства, однако очень легко (особенно, учитывая тяжёлый синтаксис) залезть в такие дебри, что и компилятор может зависнуть или завершиться с ошибкой при попытке это разобрать, поэтому к использованию метафункций C++ следует подходить прагматически, не бросаясь в абстракции и не пытаясь достичь степени общности более высокой, чем требуется текущей задачей.