Не так давно, один из авторов этого блога высказал мне свое мнение относительно кода моей библиотеки extmath. Ничего плохого в мнении не было, но он своей фразой “код похож на функциональный стиль” (точную формулировку не вспомню) сподвиг меня на написание этой статьи, чего бы никогда не пришло мне в голову… Так что, добро пожаловать в экскурс в функциональное программирование в Icon !
Начну я с того, что в Icon процедуры являются величинами первого класса, что позволяет присваивать переменным сами процедуры, а не результаты их выполнения. Это утверждение легко проиллюстрировать следующим кодом:
procedure main() local p p := cube write(p(3)) end procedure cube(x) return x * x * x end
Нетрудно понять, что в переменной p оказывается сама процедура cube, и поэтому в результате выполнения этого кода на выходе мы получим куб числа 3. Но и это еще не все.
Icon позволяет создавать чистые процедуры (т.е аналог чистых функций, поскольку в Icon нет ключевого слова для определения функции, а процедуры могут возвращать значения), что открывает возможности для использования чисто функционального стиля программирования.
Однако, не следует думать, что все процедуры в Icon являются чистыми – Icon не является чисто функциональным, да и программисту ничто не мешает определить процедуру с побочным эффектом.
Не одними чистыми процедурами (=функциями) жив функциональный стиль. В функциональном стиле присутствует также определенный набор техник.
Одной из такой техник является использование рекурсии.
Традиционно рекурсию показывают на примере факториала и чисел Фиббоначи, что же, не будем отставать от остальных:
procedure factorial(x) if x < 2 then return 1 else return factorial(x-1) * x end procedure fibbonacci(x) if x = 0 | x = 1 then return 1 else return fibbonacci(x-1) + fibbonacci(x-2) end
Примеры по моему ясны и говорят сами за себя, кроме того рекурсию можно использовать для того, чтобы в Icon ввести некоторые функции (в том числе и функции высшего порядка):
procedure mapf(f,l)
local i,acc
acc := []
every i:= 1 to *l do {
if type(l[i]) ~== "list" then put(acc,f(l[i])) else {
put(acc,mapf(f,l[i]))
}
}
return acc
end
Этот код, позволит ввести в Icon процедуру аналогичную функции map из функциональных языков (напоминаю, функция map(f,l) возвращает список, построенный в результате применения процедуры f к каждому элементу из списка l). Стоит заметить, что процедура mapf работает для функций одного аргумента, однако, в принципе можно построить реализацию для map с двумя аргументами.
Кроме функции map можно и реализовать другие функции высшего порядка, например, очень полезной может быть функция filter(f,l), которая возвращает список элементов списка l для которых функция истинна (дает хоть какой-то результат, отличный от fail). Эта функция известна многим программистам, использующим Python и ее легко можно реализовать, используя код, похожий на код процедуры mapf:
procedure filter(f,l)
local i,acc
acc := []
every i:= 1 to *l do {
if type(l[i]) ~== "list" then {
if f(l[i]) then put(acc,l[i])
} else put(acc,filter(f,l[i]))
}
return acc
end
Эту процедуру испытать можно таким образом:
procedure f1(x) if x % 2 = 0 then return 1 else 0 end procedure f2(x) if x % 2 = 0 then return end procedure f3(x) if x % 2 = 0 then return 1 else fail end procedure main() local a,b,c,d a := [1,2,3,4,5,6,7,8,9,10] b := filter(f1,a) c := filter(f2,a) d := filter(f3,a) every write(!b) every write(!с) every write(!d) end
В результате работы программы получиться несколько списков, в которых присутствуют только четные числа. Процедуры f1,f2,f3 - абсолютно идентичны друг другу и показывают тот факт, что фильтрующую функцию можно описать по-разному.
Во многих функциональных языках присутствует функция свертки списка с помощью некоторой функции (обычно именуется как reduce или accumulate). Иногда эта функция бывает и не одна, а как минимум две: foldl - лево-ассоциативная свертка и foldr - право-ассоциативная свертка. Но к сожалению, в Icon отсутствуют эти функции 🙁
Однако, обе функции легко реалезуемы с помощью чисто императивного кода:
procedure foldl(f,start,l)
local i
every i := 1 to *l do {
if type(l[i]) ~== "list" then start := f(start,l[i]) else start := f(start,foldl(f,start,l[i]))
}
return start
end
procedure foldr(f,start,l)
local i
every i := *l to 1 by -1 do {
if type(l[i]) ~== "list" then start := f(start,l[i]) else start := f(start,foldl(f,start,l[i]))
}
return start
end
Эти процедуры принимают три аргумента - функцию, стартовое значение (по сути дела, начальное значение внутреннего аккумулятора функции) и список. foldl и foldr в большинстве бинарных операций дают один и тот же результат, однако, это выполнимо не всегда (в частности, для функций, где позиции аргументов имеют значение).
Благодаря этим процедурам можно элегантно решать некоторые задачи, например можно осуществить суммирование элементов списка вот таким образом:
procedure plus(a,b) return a + b end procedure summ(l) return foldl(plus,0,l) end
Причем, это будет работать и для вложенных списков.
Icon, как мультипарадигменный язык, позволяет использовать и функциональную парадигму (правда, приходиться вводить некоторые расширения) и активно сочетать ее с императивной.
Не стоит воспринимать описанное в статье как полный обзор, поскольку рассмотрены далеко не все возможности ФП в Icon, однако, были показаны основные идеи по его введению в свои программы.