Tag Archives: функциональное программирование

Пример функциональной декомпозиции

Задача вроде тех, что решают студенты на нашем экзамене после первого семестра.

«Дана прямоугольная матрица. Найти в ней первую строку, не содержащую нулей, или определить, что таких строк нет.»

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

Решение в стиле C подразумевает прототип функции вроде (матрицу можно оформить по-разному, но предпочтём пока простейший вариант):

float* find_row_without_zero
  (float **a, size_t rows, size_t cols);

— вернуть указатель на соответствующую строку, либо nullptr, если такой нет.

Итак, студент видит слово «матрица», из чего делает вывод, что здесь явно двойной цикл, и пишет что-то такое:

float* find_row_without_zero
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
        // ???
      else
        // ???

Почему-то многим очень хочется поставить else-секцию с возвратом результата. Т.е. ошибочно подменить квантор «все» (не нули) на «существует». Под if в этом случае идёт break. Положим, стало ясно, что else здесь никак не нужен. Что же делать? Типичное неказистое решение имеет следующий вид:

// Bad structured programming (using a flag variable).
float* find_row_without_zero_1
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    bool found = true;
    for (size_t j = 0; j < cols; ++j)
    {
      if (a[i][j] == 0)
      {
        found = false;
        break;
      }
    }

    if (found)
      return a[i];
  }

  return nullptr;
}

В принципе, кто-то может решиться на использование goto, что даёт избавление от лишней переменной. Но это маловероятно: в примерах goto почти не встречается, а в книгах последних десятилетий его использование традиционно порицается.

// I'm not afraid of GOTO!
float* find_row_without_zero_2
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
  {
    for (size_t j = 0; j < cols; ++j)
      if (a[i][j] == 0)
        goto next_row;

    return a[i];
  next_row:;
  }

  return nullptr;
}

На самом деле, данная задача подразумевает применение функциональной декомпозиции (основного метода программирования, кстати). Достаточно понять, что решение по сути является композицией двух линейных поисков.

// Good structured programming:
// applying functional decomposition.
float* find_value
  (float *a, size_t size, float val)
{
  for (size_t i = 0; i < size; ++i)
    if (a[i] == val)
      return a + i;
  return nullptr;
}

float* find_row_without_zero_3
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (!find_value(a[i], cols, 0))
      return a[i];
  return nullptr;
}

Если предполагается использование STL (после первого семестра это ещё не предполагается), то явный цикл можно заменить на вызов std::find, так:

// Ah, std::find does the work in C++.
float* find_row_without_zero_4
  (float **a, size_t rows, size_t cols)
{
  for (size_t i = 0; i < rows; ++i)
    if (std::find(a[i], a[i] + cols, 0.f) == a[i] + cols)
      return a[i];
  return nullptr;
}

или даже так (ещё std::find_if, шаблон по типу данных и значение по умолчанию вместо явного нуля):

// It's not beautiful, I guess...
template <class NT>
NT* find_row_without_zero_5
  (NT **a, size_t rows, size_t cols)
{
  const auto p = std::find_if(a, a + rows,
    [cols](NT *a)
    {
      return std::find(a, a + cols, NT{}) == a + cols;
    });
  return p == a + rows? nullptr: *p;
}

Последний вариант, впрочем, наверно, избыточно «навороченный».

Ну и наконец, можно поразвлекаться в функциональном стиле (требуется C++14), отказавшись от указателей и рассматривая матрицу как диапазон диапазонов. Будем возвращать итератор в стиле STL.

using std::forward;

template <class Item>
auto equals(Item &&item)
{
  return [it = forward<Item>(item)]
  (auto &&other)
  {
    return other == it;
  };
}

template <class Pred>
auto find(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::begin;
    using std::end;

    const auto e = end(rng);
    auto p = begin(rng);
    while (p != e && !pr(*p))
      ++p;

    return p;
  };
}

template <class Pred>
auto none(Pred &&pred)
{
  return [pr = forward<Pred>(pred)]
  (auto &&rng)
  {
    using std::end;
    return find(pr)(rng) == end(rng);
  };
}

Вышеприведённые определения позволяют в итоге записать решение в виде композиции:

template <class Rng2>
auto find_row_without_zero_6(Rng2 &&rows)
{
  return find(none(equals(0)))(rows);
}

Забавно, что такая конструкция применима не только, например, к вектору векторов, но и к статическому двумерному массиву:

float m[3][4]
{
  { 1, 1, 1, 0 },
  { 0, 1, 1, 1 },
  { 1, 0, 1, 1 },
};

assert(find_row_without_zero_6(m) == std::end(m));
Реклама

Перегрузка замыканий

Расширение арсенала C++ анонимными функциями и замыканиями в стандарте 2011 года сделало существенно более удобным использование алгоритмов STL и подобных им функций-шаблонов.

Пример. Удалить из вектора v все числа вне диапазона [-a, a].

v.erase(remove_if(v.begin(), v.end(),
    [a](double x) { return a < abs(x); }), v.end());

В случае C++14 не обязательно указывать конкретный принимаемый тип, что позволяет обобщить некоторые случаи. Например, в духе карринга

template <class Pred>
inline auto erase_remove_if(Pred pred)
{
  return [pred](auto &v)
  {
    v.erase(remove_if(begin(v), end(v), pred), end(v));
  };
}

// удалить из v все значения вне [-a, a]
erase_remove_if([a](auto x) { return a < abs(x); })(v);

С формальной точки зрения, замыкания (даже в варианте C++14) являются не расширением возможностей C++03, а своего рода «синтаксическим сахаром». Код, приведённый выше, можно переписать как

// C++03 version
template <class T>
class Outside_symsegment
{
  T a;
public:
  
  explicit Outside_symsegment(const T &a)
      : a(a) {}

  template <class X> // *
  bool operator()(const X &x) const
  {
    return a < abs(x);
  }
};

template <class T>
inline Outside_symsegment<T>
  make_outside_symsegment(const T &a)
{
  return Outside_symsegment<T>(a);
}

template <class Pred>
class Erase_remove_if
{
  Pred pred;
public:
  explicit Erase_remove_if(const Pred &pred)
      : pred(pred) {}

  template <class T>
  void operator()(T &v) const
  {
    v.erase(remove_if(v.begin(), v.end(), pred), v.end());
  }
};

template <class Pred>
inline Erase_remove_if<Pred>
  erase_remove_if(Pred pred)
{
  return Erase_remove_if<Pred>(pred);
}

// удалить из v все значения вне [-a, a]
erase_remove_if(make_outside_symsegment(a))(v);

* Замечание. Вариант для C++14 предоставляет возможность автоматического вывода возвращаемых типов (в лямбда-выражении можно не указывать возвращаемый тип), что во многих случаях можно имитировать средствами C++03, но здесь рассматриваться не будет. С другой стороны, можно использовать ещё одно нововведение C++11: decltype.

Таким образом, лямбда-выражение может создавать новый тип функтора с функцией-шаблоном operator(). Одним из возможных применений функторов является реализация паттерна «Посетитель» (Visitor) с использованием статической диспетчеризации для обработки разнотипных объектов.

Пример. В задаче сериализации структур данных можно предложить разные форматы, одновременно поддерживающие структуры «массив» и «множество» (набор уникальных элементов).

template <class Ostream>
class Writer
{
  Ostream &os;
  template <class... Any>
  void print(Any&&... any)
  {
    // это "трюк", дающий небольшое удобство:
    // возможность писать в print подряд набор значений;
    int _[] = { ((*this)(forward<Any>(any)), 0)... };
    // ну и маленькая демонстрация variadic templates :)
  }

  template <class Name, class Lit, class Cont>
  void prints
  (
    const Name &name,
    const Cont &cont, 
    Lit open,
    Lit delim,
    Lit close
  )
  {
    print(name, open);
    auto p = begin(cont), e = end(cont);
    if (p != e)
    {
      print(*p);
      while (++p != e)
        print(delim, *p);
    }
    print(close);    
  }
  
public:
  explicit Writer(Ostream &os)
      : os(os) {}

  // общий вариант, полагается на оператор <<
  template <class Any>
  void operator()(const Any &x)
  {
    os << x;
  }

  // вариант для строк, берёт содержимое в кавычки
  template <class Char, class Traits, class Alloc>
  void operator()(const basic_string<Char, Traits, Alloc> &s)
  {
    os << quoted(s);
  }

  template <class Name, class Item, class Alloc>
  void operator()(const Name &name, const vector<Item, Alloc> &v)
  {
    prints(name, v, ": [", ", ", "]");
  }

  template <class Name, class Item, class Comp, class Alloc>
  void operator()(const Name &name, const set<Item, Comp, Alloc> &s)
  {
    prints(name, s, ": {", ", ", "}");
  }
  
  // можно продолжить для других контейнеров
};

template <class Ostream>
inline auto make_writer(Ostream &os)
{
  return Writer<Ostream>(os);
}

(результат работы данного кода на ideone.com)

Можно ли сделать конструкцию, позволяющую создавать подобные перегруженные функторы на месте использования, например, из замыканий? Как нетрудно догадаться, ответ на этот вопрос положительный.

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

Для этого определим метафункцию Functor_caller, позволяющую получить нужный базовый класс.

template <class F>
struct Functor_caller
{
  using type = F;
};

template <class R, class... Args>
struct Functor_caller<R (*)(Args...)>
{
  struct type
  {
    using ftype = R (*)(Args...);
    const ftype ptr;
    type(ftype ptr): ptr(ptr) {}

    R operator()(Args... args) const
    {
      return ptr(forward<Args>(args)...);
    }
  };
};

Для комбинирования пары классов в один производный класс через наследование определим вспомогательный шаблон Compose

template <class Base1, class Base2>
struct Compose : Base1, Base2
{
  template <class Init1, class Init2>
  Compose(Init1&& init1, Init2&& init2)
    : Base1(forward<Init1>(init1)),
      Base2(forward<Init2>(init2))
      {}

  Compose(Compose<Base1, Base2>&&) = default;
  using Base1::operator();
  using Base2::operator();
};

Теперь, наконец, можно определить функцию make_switch, создающую комбинированный функтор из набора функторов

template <class Functor>
inline auto make_switch(Functor&& functor)
{
  return typename Functor_caller<decay_t<Functor>>::
    type(forward<Functor>(functor));
}

template <class Functor, class... Tail>
inline auto make_switch(Functor&& functor, Tail&&... tail)
{
  auto head_object = make_switch(forward<Functor>(functor));
  auto tail_object = make_switch(forward<Tail>(tail)...);

  using head_type = decay_t<decltype(head_object)>;
  using tail_type = decay_t<decltype(tail_object)>;

  return Compose<head_type, tail_type>
    (move(head_object), move(tail_object));
}

(код целиком вместе с простеньким тестом)

Данная функция использует рекурсию времени компиляции — достаточно естественный приём при работе с шаблонами с переменным числом параметров. Шаблон decay_t введён стандартом C++14.

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

Во-первых, созданный составной объект хранит во время исполнения все переданные make_switch указатели/ссылки на функции, даже если эти функции заданы во время компиляции (как в примере по ссылке выше), и вместо «прошитого» вызова совершает вызов по указателю, что в некоторых случаях чревато заметными дополнительными расходами процессорного времени.

Во-вторых, это решение не предоставляет возможность легко реализовать аналог рассмотренного выше класса Writer на основе замыканий, так как их возможности создания шаблонов operator() ограничены словом auto, не позволяющим «на месте» отделить произвольный vector от произвольного set, т.е. имеем ситуацию или полностью заданный тип или произвольный тип, без возможности сопоставить параметры шаблона образцу.

C++: список типов

Данный пост посвящён созданию списков типов в C++11 и работе с ними.
Список — это линейная рекурсивная структура данных. Условно её можно представить как

type List = Nil | (type, List)

Здесь Nil — вспомогательный тип, означающий пустой список (или конец списка).

// выбор первой части пары
head x = x
head (h, t) = h

// выбор второй части пары
tail x = Nil
tail (h, t) = t

Теперь на C++.

struct Nil {};

template <class H, class T = Nil>
struct Cons {};

template <class L>
struct Head { using type = L; };

template <class H, class T>
struct Head<Cons<H, T>> { using type = H; };

template <class L>
struct Tail { using type = Nil; };

template <class H, class T>
struct Tail<Cons<H, T>> { using type = T; };

Cons (сокращение от construct) позволяет собирать пару типов в новый тип. Фактически, например, список [char, short, int, long] записывается как Cons<char, Cons<short, Cons<int, Cons<long, Nil>>>>. Это не слишком удобно. Добавим вспомогательные определения, позволяющие сократить запись.

// *T -- синоним выборки зависимого имени type
template <class L>
using HeadT = typename Head<L>::type;

template <class L>
using TailT = typename Tail<L>::type;

template <class... Types>
struct List {};

template <>
struct List<> { using type = Nil; };

template <class H, class... T>
struct List<H, T...> 
{ using type = Cons<H, typename List<T...>::type>; };

template <class... Types>
using ListT = typename List<Types...>::type;

Теперь тот же список типов, что был приведён выше, можно записать как ListT<char, short, int, long>.
Обработка списка распадается на обращение к голове и рекурсивную обработку хвоста. Напишем функцию, выводящую в консоль названия типов, зафиксированных в списке (я воспользуюсь частичной специализацией шаблонов функций, появившейся в C++11).

template <class List>
void print_typelist()
{
  std::cout << typeid(HeadT<List>).name() << ' ';
  print_typelist<TailT<List>>();
}

template <>
void print_typelist<Nil>() {}

Предположим, что есть метафункция f : type -> type и требуется получить список результатов применения данной функции к исходному списку (операция map). Как это реализовать?

map f Nil = Nil
map f (h, t) = (f h, map f t)

Чтобы оформить это на C++, необходимо решить, на какой вариант представления метафункций при этом ориентироваться. В данном случае, я выбрал вариант 2 как основной, применяемый Стандартной библиотекой.

template <template <class A> class F, class L>
struct Map
{ using type = typename F<L>::type; };

template <template <class A> class F, class H, class T>
struct Map<F, Cons<H, T>>
{
  using type = Cons<typename F<H>::type,
                    typename Map<F, T>::type>;
};

template <template <class A> class F>
struct Map<F, Nil> { using type = Nil; };

Предположим, есть метафункция b(x, y), принимающая два параметра. Тогда можно поставить задачу о свёртке списка, т.е. вычисления выражения вида b(start, b(item1, b(item2, …, b(itemN-1, itemN)…))). В функциональных языках функцию, позволяющую выполнить такую свёртку списка для произвольных функции b и начального значения start, обычно называют foldr (правоассоциативная свёртка). Я буду использовать следующее определение на C++.

template <
  template <class A, class B> class F,
  class S, class L>
struct Fold
{
  using type = S;
  static const auto value = type::value;
};

template <
  template <class A, class B> class F,
  class S, class H, class T>
struct Fold<F, S, Cons<H, T>>
{
  using type = typename
    F<S, typename Fold<F, H, T>::type>::type;
  static const auto value = type::value;
};

Воспользуемся Fold для определения операций проверки выполнения некоторого предиката на каком-либо или на всех элементах списка.

template <bool B>
using Bool = std::integral_constant<bool, B>;

using False = Bool<false>;
using True = Bool<true>;

template <class A, class B>
struct Or: Bool<A::value || B::value> {};

template <class A, class B>
struct And: Bool<A::value && B::value> {};

template <class L>
using ExistsTrue = typename Fold<Or, False, L>::type;

template <class L>
using AllTrue = typename Fold<And, True, L>::type;

Например, мы хотим проверить, принадлежит ли некоторый тип заданному списку. Определим для этого метафункцию Belongs тип список:

template <
  template <class A, class B> class F,
  class A>  // карринг
struct Bind
{
  template <class B>
  using apply = typename F<A, B>::type;
};

template <class T, class L>
struct Belongs
  : ExistsTrue<typename 
      Map<Bind<std::is_same, T>::template apply, L>::type> {};

На данной основе не сложно определить и другие операции, обычно определяемые для списков (например, вычисление длины).

Исходный код

Метафункции C++

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

Механизм шаблонов 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++ следует подходить прагматически, не бросаясь в абстракции и не пытаясь достичь степени общности более высокой, чем требуется текущей задачей.