Чистые функции

Article
04/26/2011

На первый взгляд с чистыми функциями все просто. Функция называется чистой, если она удовлетворяет двум требованиям:

Функция всегда возвращает одно и то же значение для одних и тех аргументов. Т.е. если мы один раз вызвали чистую функцию с аргументами, к примеру, 12 и 42, то когда нам потребуется вызвать ее еще раз, с точно такими же аргументами, мы можем попросту использовать предыдущее значение, которое вернула эта функция.
Функция не изменяет состояние, внешнее по отношению к этой функции, и не зависит от этого состояния. Функция, которая удаляет файл из файловой системы, очевидно не является чистой (и неудивительно, ведь она удаляет целый файл!). Точно так же, как не является чистой функция, которая читает данные из файла. Функция так же не должна изменять переданные в нее аргументы - ведь эти аргументы были переданы извне и, соответственно, не принадлежат функции.

Также надо понимать, что если одна функция, которая не делает ничего предосудительного, вызывает другую функцию, не соответствующую высоким стандартам чистоты, то она автоматически тоже становится нечистой. Нечистота - как заразная инфекция, переходит от одной функции к другой.

Ну и приведем для убедительности яркий пример чистой функции на Хаскелл:

 add x y = x + y

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

Прежде всего следует понимать, что чистые функции никакого отношения к программированию в функциональном стиле не имеют. К примеру, является ли такая функция чистой:

 int sum(int[] arr)
{
  int res = 0;

  for (int i = 0; i < arr.Length; i++)
    res += arr[i];

  return res;
}

Правильный ответ - да, она такая же чистая, как и ее аналог на Хаскелле:

 sum [] = 0
sum (x:xs) = x + sum xs

Да, наша реализация на C# написана в императивном стиле, более того, она всерьез "налегает" на изменяемые переменные - но все эти переменные локальные для функции, мы не изменяем никакого внешнего состояния и не зависим от него, мы всегда возвращаем один и тот же результат для тех же аргументов.

И тут возникает второй нюанс. Давайте вспомним функцию filter, которую мы уже рассматривали ранее:

 filter _ [] = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

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

Так почему же мы считаем функцию filter чистой? Да и вообще - чистая ли она?

Ответ прост. Мы считаем ее чистой, потому что списки в функциональных языках сравниваются не ссылочно (как, к примеру, массивы в C#), а структурно. Поэтому результаты двух вызовов этой функции эквивалентны, что несложно проверить в GHCi:

 Prelude>filter (>5) [1..10] == filter (>5) [1..10]
True

Скажете, мы пошли на хитрость? И да, и нет. Так как список является неизменяемой структурой данных, то мы имеем полное право применять к нему те же правила при сравнении, что и, к примеру, для целых чисел. И с чистой душой игнорировать такие низкоуровневые детали, как размещение списка в памяти. Ведь с точки зрения пользователя два списка с одинаковыми элементами - это по сути один и тот же список.

А как быть с изменяемыми структурами данных? Попробуем написать отдаленный аналог функции filter на С#:

 List<int> filter(Func<int,bool> p, List<int> list)
{
  var newList = new List<int>();

  foreach (var e in list)
    if (p(e))
      newList.Add(e);

  return newList;
}

Является ли эта функция чистой? Боюсь, что на сей раз придется ответить "нет". List<int>, вопреки своему названию, представляет собой изменяемый массив, поэтому считать два экземпляра List<int> с одинаковым набором элементов одним и тем же "списком" мы уже не можем. Почему? Только ли потому что в C# для List<int> или обычных массивом структурное сравнение не используется по умолчанию, а сравниваются ссылки?

Вовсе нет. Давайте представим, что массивы в C# сравниваются именно структурно. Таким образом, два массива с одинаковым набором элементов будут считаться равными. И тогда мы сможем написать такой код:

 var arr1 = new int[] { 1,2,3 };
var arr2 = new int[] { 1,2,3 };


if (arr1 == arr2)
  Console.WriteLine("arr1 и arr2 это один и тот же массив.");

arr1[0] = 10;

if (arr1 != arr2)
  Console.WriteLine("arr1 и arr2 это разные массивы.");

В результате выведется:

 arr1 и arr2 это один и тот же массив.
arr1 и arr2 это разные массивы.

Как же так? Мгновение назад массивы были одинаковыми, а теперь они разные?

Как вы понимаете, во всем виновата "изменчивая природа" массивов. Так как вы можете поменять значения "по месту" (в отличие от связных списков в Хаскелле, любая операция над которыми приводит к созданию нового списка), то структурная эквивалетность уже не годится.

Другое дело - строки в C#. Ведь строки по сути это те же индексированные массивы, только на сей раз неизменяемые. Но говоря, что две строки равны, мы прежде всего подразумеваем, что эти строки состоят из одного и того же набора символов, при этом нас совершенно не волнует, занимают ли они одни и те же байты в оперативной памяти.

Чистые функции

Additional resources