Уроки программирования F#. Урок 1: Дух функционального программирования


Итак, приступим. Сегодня нам нужно будет сделать самое главное – понять основные принципы функционального программирования и проникнуться его духом. Заранее прошу прощения у тех, кто ждет более содержательных уроков – но мне хотелось начать с начала. Соответственно, для начала, история из жизни:


Когда я был молодым и преподавал программирование на первом курсе факультета Прикладной математики МАИ, один из студентов никак не мог понять, что значит X:=X+1. “Как же так, как X может быть равен X+1?”. Мне пришлось объяснить ему, как такое возможно, и в этот момент в нем умер функциональный программист…


Почему? Давайте разберемся. Название “функциональное программирование” происходит от слова “функция”. Функциональная программа строится из функций. Собственно, сама программа – это тоже функция, которую можно применить к входным данным и получить результат.


“Ну и что?”- скажете вы. – программа на Паскале тоже состоит (или может состоять) из функций. Правильно, только в программе на Паскале, помимо функций, есть еще операторы, управляющие конструкции типа циклов, и, самое главное, оператор присваивания. Программа на Паскале задает набор шагов, каждый из которых изменяет некоторое состояние памяти компьютера, вычисляя выражения и присваивая их переменным.

В функциональном программировании всё не так. Тут есть только функции, и все данные являются неизменяемыми (immutable). Вся программа строится из комбинации функций, которые оперируют данными, перерабатывая одни значения в другие.

Рассмотрим пример: функцию вычисления факториала. На императивном языке, например, C#, функция будет выглядеть так:

public int fact(int n)
{
int f = 1;
for (int i = 2; i <= n; i++)
{
f = f * i;
}
return f;
}

Мы заводим аккумулятор, и в цикле последовательно домножаем его на очередное натуральное число. В случае с F# у нас нет понятия переменной, и мы должны построить определение лишь используя комбинацию функций:

let rec fact n =
if n = 1 then 1
else n*fact(n-1)
in fact 5;;

Данное выражение вычисляет факториал 5. Основным вычисляемым выражением тут является fact 5, а все, что написано до него, определяет значение символа fact.

Вообще говоря, смысл конструкции let – дать имя-синоним некоторому выражению. Например,

let x = 1 in
let
y = 2+x in
x+5*y;;

Здесь имена x и y определяются только в контексте выражения, расположенного после слова in – поэтому такое выражение полностью аналогично выражению 1+5*(2+1).

В нашем случае, после let идет ещё и rec, чтобы показать, что определение функции рекурсивно. Сама же функция определяется как чистая композиция других функций: условной функции (действительно, в данном случае оператор if можно было бы заменить функцией if от трех аргументов, как это сделано, например, в Excel), умножения, вычитания и самой функции fact. На самом деле можно переписать определение так (здесь я для ясности опускаю некоторые моменты связанные с порядком вычисления условного выражения):

let rec fact n = iff ((=) n 1) 1 ((*) n (fact ((-) n 1)));;

Из такой записи видно, что ничего, кроме композиции функций, тут нет. На самом деле, в чистом функциональном программировании есть всего две операции: аппликация (применение функции к агрументу) и абстракция (возможность построения функции из выражения). Последовательная запись нескольких функций вида f g u v означает ((f g) u) v, т.е. аппликация проводится слева направо, сначала f применяется к g, в результате должна получиться функция, которая применяется к u и так далее. Абстракция позволяет получить функцию по выражению, иными словами, записать функциональную константу. Например, запись fun x -> x*2 означает функцию, которая по целому аргументу возвращает его удвоенное значение.

Рассмотрим еще одно важное понятие – каррирование. Все функции в функциональном программировании – одноместные, т.е. имеют один аргумент. Интересно, как в этом случае быть с такими операциями, как сложение?

Есть два варианта. Можно рассматривать сложение как функцию от упорядоченной пары, например

let plus’ (x,y) = x+y;;

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

let plus x y = x+y;;

Если в первом случае тип функции будет int*int -> int (т.е. отображение из пары в целый тип), то во втором – int -> (int -> int), т.е. это будет функция от целого типа, которая возвращает функцию из целого в целое. Например, выражение (plus 1) будет означать функцию инкремента, т.е. увеличения аргумента на 1. Запись plus 1 2 будет рассмативаться как (plus 1) 2, т.е. сначала мы получим функцию инкремента, а потом применим её к числу 2, получив требуемый результат. Функция plus называется каррированной функцией сложения, и в функциональном программировании принято использовать именно такие функции. В частности, все стандартные операции могут быть использованы в каррированной форме путем заключения операции в скобки и использовании префиксной записи, например:

(+) 1 2;;
let incr = (+)1;;

Итак, мы поняли следующие основные принципы функционального программирования: всё является функцией, ничего кроме функции не существует, нет оператора присваивания и переменных. Давайте поймём ещё один принцип: функции являются полноправными сущностями (first-class citizens), можно передавать функции как параметры, описывать функциональные константы и оперировать функциями. Например:

let double x = x*2.0;;

описывает функцию умножения на 2, примерно такую:

public double doub(double x)
{
return x * 2.0;
}

Что приятно – в F# почти никогда не возникает необходимость указывать типы параметров и значений – они получаются автоматически благодаря работе системы вывода типов. В частности, если мы введем приведенное выше определение функции double в интерпретатор F#, мы получим:

val double : float -> float

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

Рассмотрим следующее выражение:

let double x = x*2.0 in
let
quad = (double >> double) in quad 5.0;;

Здесь мы сначала описываем функцию double, затем другую функцию quad, представляющую собой композицию двух функций double, обозначаемую как >>.

В завершение урока, я хотел бы предложить вам несколько задач и вопросов в качестве домашнего задания на размышление.

Домашнее задание:


  1. Определите функцию для нахождения корней квадратного уравнения.

  2. Реализуйте функциональную программу для нахождения суммы числел от 1 до 100. Суммы квадратов этих чисел.

  3. Как вы думаете, какая из функций вычисления факториала, приведенных в этом уроке, «лучше» – реализованная на C# или на F#?

  4. Опишите функцию каррирования, которая по двухместной некаррированной функции (т.е. функции от пары значений) возвращает соответствующую функцию в каррированном виде.

  5. Опишите функцию декаррирования, обратную тому, что требовалось в п.4

Comments (3)

  1. Имеет ли смысл учить не-#light синтаксису, если сам Дон сказал, что он будет deprecated в релизе, и #light будет по умолчанию? Уже сейчас на последней версии отсутствие #light дает warning.

  2. По-моему, изначально использование let … in позволяет правильнее понять смысл конструкции let. Дальше поговорим о #light-синтаксисе.

  3. Romul says:

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

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

    Хотя можно свести к хвостовой рекурсии с помощью аккумулятора:

    let rec fact n acc =

     match n with

     | 0   -> acc

     | n   -> fact (n-1) (acc*n)

    let rec factorial n =

     fact n 1

    print_any(factorial 5)

    кстати как в F# сделать карринг типа fact n -> fact n 1 ?

Skip to main content