Чому програмісти мають вивчити Haskell, навіть якщо нічого не будуть на ньому писати

Привіт. Я Лущик Павло, працюю програмістом в невеликій компанії, що в основному займається приладобудуванням. Тут не буде монад. В цій статті я продемонструю цікавий метод програмування, який я відкрив для себе під час вивчення Haskell.

Оскільки я в основному пишу на С++, то майже весь код буде на С++ і Haskell. Але спробую написати код ідіоматично і він буде без деструкторів, конструкторів копіювання/переміщення та інших специфічних для С++ речей.

Перейдемо до задачі. Вона доволі синтетична і спеціально підібрана для демонстрації методу. Припустимо, у вас є така структура даних.

struct tree {  
  bool is_leaf;  
  union {    
    int leaf_value; 
    struct {
      tree *node_left;
      tree *node_right;
    };
  };
  tree(int value) : is_leaf(true), leaf_value(value) {}
  tree(tree *l, tree *r) : is_leaf(false), node_left(l), node_right(r) {}
};

Як бачимо, це звичайне дерево з цілими числами у листах. Завдання полягає в тому, щоб порахувати суму всіх елементів листів.

Найпростіший розв’язок виглядає так:

int tsum(tree *x) {  
  if (x->is_leaf) return x->leaf_value;  
  return tsum(x->node_left) + tsum(x->node_right);
}

Цей код дуже простий, але використовує рекурсію, що не дуже добре, бо стек має межі. Очевидно, що треба позбутися рекурсії, використовуючи деякий ітеративний алгоритм. Можна написати його з нуля. Але я збираюся показати вам, як магічний Haskell не тільки напише цей ітеративний алгоритм за нас, але ще і надасть математичний доказ еквівалентності рекурсивного й ітеративного коду. Нумо до факторіалів!

1. Факторіал з акумулятором

Почнемо з магічного Haskell. Є факторіал:

fact :: Int -> Int 
fact 0 = 1
fact x = x * fact (x-1)

Як бачимо, ця функція рекурсивна. Для початку зробимо її такою, щоб можна було застосувати оптимізацію хвостового виклику. Для цього визначимо іншу функцію fact_acc, у якій є додатковий параметр (акумулятор) так, що:

fact_acc :: Int -> Int -> Int
fact_acc a x = a * fact x      (визначення)

Перше, що ми можемо побачити, це те, що:

fact_acc 1 x = 1 * fact x

Тобто:

fact x = fact_acc 1 x

Зазначаємо, що fact можна визначити й через fact_acc.

Друге — спробуймо позбутися fact у визначенні fact_acc. Це ніби як схоже на розв’язок звичайних алгебраїчних рівнянь.

Спочатку розглянемо частинний випадок x = 1. за визначенням:

fact_acc a 1 = a * fact 1 = a

А тепер загальний випадок:

fact_acc a x =  a * fact x =  (підставляємо визначення fact)
  a * (x * fact (x-1)) =      (використовуємо асоціативність множення)
  (a*x) * fact (x-1) =        (використовуємо визначення fact_acc)
  fact_acc (a*x) (x-1)

Складемо все до купи й отримаємо повне визначення fact_acc:

fact_acc :: Int -> Int -> Int
fact_acc a 1 = a                      -- (*1)
fact_acc a x = fact_acc (x*a) (x-1)   -- (*2)

А тепер напишемо аналогічний код на C++.

int fact_acc(int a, int x) {
  if (x == 0) return a;         // (випадок 1)
  return fact_acc(a*x, x-1);    // (випадок 2)
}

Такий код можна майже механічно перетворити на ітеративний.

int fact_iter(int a, int x) {
  while (true) {
    if (x == 0) return a;       // (для випадку 1)
    a *= x;                     // (для випадку 2)
    x -= 1;
  }
}

2. Фібоначчі на акумуляторах

Наступний приклад складніший — числа Фібоначчі (неочікувано).

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)

Повторимо попередні дії. Спробуємо знайти функцію fib_acc — таку, щоб для неї можна було б застосувати оптимізацію хвостового виклику. Тут нам знадобиться два акумулятори. Визначимо її так:

fib_acc a b x = a * fib x + b * fib (x-1)

Можна побачити, що:

fib_acc 1 0 x = 1 * fib x + 0 * fib (x-1)

З чого слідує визначення fib через fib_acc.

fib x = fib_acc 1 0 x

Визначимо fib_acc через саму себе. Частинний випадок, коли x = 0 не має розв’язку, бо fib (-1) не визначено, але оскільки ми знаємо, що fib 0 = 0, то можемо прийняти:

fib_acc a b 0 = 0

Для одиниці:

fib_acc a b 1 = a * fib 1 + b * fib 0 = a

Тепер загальний випадок:

fib_acc a b x =  a * fib x + b * fib (x-1) =       (визначення fib для першого додатку)
  a * (fib (x-1) + fib (x-2)) + b * fib (x-1) =    (використовуємо дистрибутивність множення)
  (a + b) * fib (x-1) + a * fib (x-2) =            (за визначенням fib_acc)
  fib_acc (a+b) a (x-1)

Отже:

fib_acc :: Int -> Int -> Int -> Int
fib_acc a b 0 = 0                         -- (*1)
fib_acc a b 1 = a                         -- (*2)
fib_acc a b x = fib_acc (a+b) a (x-1)     -- (*3)

Так це виглядає на C++:

int fib_acc(int a, int b, int x) {
  if (x == 0) return 0;                // (для випадку 1)
  if (x == 1) return a;                // (для випадку 2)
  return fib_acc(a+b, a, x-1);         // (для випадку 3)
}

Майже механічно перетворюємо цей код на ітеративний:

int fibi(int a, int b, int x) {
  if (x == 0) return 0;             // (для випадку 1)
  while (true) {
    if (x == 1) return a;           // (для випадку 2)
    a = a + b;                      // (для випадку 3)
    b = a - b;
    x -= 1;
  }
}

Сподіваюся, тут все зрозуміло. А тепер повернемося до нашої першої задачі з деревами.

3. Задача про дерева на акумуляторах

Почнемо з магічного Haskell, визначивши спочатку тип дерева і функцію tsum.

data Tree =
    Leaf Int
  | Node Tree Tree

tsum :: Tree -> Int
tsum (Leaf x) = x
tsum (Node l r) = tsum l + tsum r

Спробуємо знайти таку функцію tsum_acc, до якої можна б було застосувати оптимізацію хвостового виклику. Цей випадок складніший за два попередні, тому скористаємося трюком з допоміжною функцією:

reduce :: [Tree] -> Int
reduce [] = 0
reduce (x:ys) = tsum x + reduce ys

А тепер визначимо tsum_acc як функцію з двома акумуляторами:

tsum_acc :: Int -> [Tree] -> Tree -> Int
tsum_acc a xs x = a + reduce xs + tsum x

Як і у попередніх випадках, одразу можна побачити, що:

tsum_acc 0 [] x = 0 + reduce [] + tsum x = tsum x

Тобто:

tsum x = tsum_acc 0 [] x

Проаналізуємо частинні випадки:

tsum_acc a [] (Leaf x) = a + reduce [] + tsum (Leaf x) = a + x

Далі випадок для непустого списку:

tsum_acc a (y:ys) (Leaf x) =
  a + reduce (y:ys) + tsum (Leaf x) =       (визначення reduce і tsum)
  a + tsum y + reduce ys + x =              (комутативніть додавання)
  (a + x) + reduce ys + tsum y =            (визначення tsum_acc)
  tsum_acc (a+x) ys y

Випадок для Node:

tsum_acc a ys (Node l r) =
  a + reduce ys + tsum (Node l r) =         (визначення tsum)
  a + reduce ys + tsum l + tsum r =         (комутативніть додавання)
  a + tsum l + redure ys + tsum r =         (визначення reduce)
  a + reduce (y:ys) + tsum r =              (визначення tsum_acc)
  tsum_acc a (y:ys) r

Отже, маємо:

tsum_acc a [] (Leaf x) = a + x                     -- (*1)
tsum_acc a (y:ys) (Leaf x) = tsum_acc (a+x) ys y   -- (*2)
tsum_acc a ys (Node l r) = tsum_acc a (l:ys) r     -- (*3)

Телепортуємося у С++. Тут як список я використаю перевернутий std::vector.

int tsum_acc(int a, std::vector<tree *> xs, tree *x) {
  if (x->is_leaf) {
    if (xs.empty()) return a + x->leaf_value;             // (випадок 1)
    a += x->leaf_value;                                   // (випадок 2)
    x = xs.back(); xs.pop_back();
    return tsum_acc(a, xs, x);
  }
  xs.push_back(x->node_left);                             // (випадок 3)
  x = x->node_right;
  return tsum_acc(a, xs, x);
}

Що знову ж таки майже механічно можна перетворити на ітеративний код:

int tsum_iter(int a, std::vector<tree *> xs, tree *x) {
  while (true) {
    if (x->is_leaf) {
      if (xs.empty()) return a + x->leaf_value;     // (випадок 1)
      a += x->leaf_value;                           // (випадок 2)
      x = xs.back(); xs.pop_back();
      continue;
    }
    xs.push_back(x->node_left);                     // (випадок 3)
    x = x->node_right;
  }
}

Який і є розв’язком. Зверніть увагу, ми почали з доволі простого та очевидного рекурсивного визначення tsum, і закінчили не дуже очевидним і дещо складним для сприйняття ітеративним кодом. Маючи, до того ж математичний доказ того, що цей код еквівалентний нашому простому, з якого ми починали.

Історія успіху та висновки

Вперше цей метод я застосував, коли шукав помилку в якомусь своєму коді, що оперував деревом віджетів. Баг був не дуже складний, але я був доволі втомлений і пошук забрав вже досить багато часу. Але помилку, яка була доволі очевидна, я не помічав, напевно, з ментальних причин. Можна було б просто залишити рекурсивну версію, бо кількість віджетів все одно була невеликою, але я не здавався.

Застосувавши подібну методику, отримав визначення ітеративної функції, який алгоритмічно відрізнялася від першої версії, але працювала при цьому бездоганно. А помилка була легко знайдена порівнянням двох версій коду. Маю також сказати, що я рідко використовую цей метод, але часто написати рекурсивну версію якогось алгоритму доволі просто, а от ітеративна часто не очевидна. Сподіваюся, цей метод стане у пригоді й вам.

Дізнався я про цей метод з книжки Programming in Haskell від Graham Hutton. Також рекомендую Calculating Correct Compilers того ж автора. Надзвичайно цікава стаття, яка використовує цей метод для складніших задач.

Дякую за увагу.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті