Categories: Функциональное программирование

perl-fp/

Спустя некоторое время после знакомства с Haskell , я заметил, что некоторые задачи уж больно легко решаются при помощи функционального подхода. Возник вполне закономерный (для меня) вопрос. А можно ли применить этот подход в Perl?

Одно из возможных решений, которое приходит на ум, заключается в том, чтобы написать динамическую библиотеку на Haskell и подгрузить ее в Perl-скрипт с помощью DynaLoader . Однако это не совсем ФП на Perl , так что думаем дальше. Вообще-то, в нашем распоряжении уже есть списки, grep, map, «лямбды» и, возможно, еще что-то, о чем я забыл. Пожалуй, для полного счастья не хватает разве что нескольких функций, вроде foldl, flip и тп.

Примечание: Вообще-то, для полного счастья не хватает еще многих вещей (о чем еще будет сказано ниже), в частности каррирования. Если вам нужно каррирование в Perl, обратите внимание на модуль Sub::Curried , а также раздел «see also» из его описания. Можно обойтись и без модулей , но это не очень удобно.

Судя по некоторым наработкам, найденным в CPAN, я далеко не первый, кто задался вопросом о функциональном программировании в Perl. Помимо традиционных модулей для работы со списками в лице List::Util и List::MoreUtils, были найдены List::Gen::Haskell , Set::Functional , Language::Functional , а также fp . Модуль List::Gen::Haskell выглядит очень интересно за счет того, что имена функций в нем заимствованы из Haskell. Тем не менее, в рамках этой заметки я воспользуюсь модулем fp. Он постарше, да и функций в нем, кажется, побольше.

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

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

Решение на Haskell:

— (с) Alexandr A Alexeev 2011 | http://remontka.com/
import Data . List

{-
nub $ map (x -> day $ sysAdminDayInYear x) [2000..2100]
[28,27,26,25,30,29,31]

nub $ map (x -> day $ softwareFreedomDayInYear x) [2000..2100]
[16,15,21,20,18,17,19]
-}

data Date = Date { year :: Int , month :: Month , day :: Int }
deriving ( Show , Eq )

— дата, когда отмечается день сисадмина в заданном году
sysAdminDayInYear y =
last $ filter ( x -> getDayOfWeek x == Friday ) [
Date { year = y , month = July , day = d } | d <- [ 1 .. 31 ]
]

— дата, когда отмечается день СПО в заданном году
softwareFreedomDayInYear y =
flip ( !! ) 2 $ filter ( x -> getDayOfWeek x == Saturday ) [
Date { year = y , month = September , day = d } | d <- [ 1 .. 30 ]
]

— определить день недели
getDayOfWeek :: Date -> DayOfWeek
getDayOfWeek x =
toEnum $ daysFromEpoch x ` mod ` 7

— преобразуем дату в кортеж
getYMD x = ( year x , month x , day x )

— число дней с 1-го января 1-го года (не включая)
daysFromEpoch :: Date -> Int
daysFromEpoch x = — TODO: проверка isValidDate ?
( sum $ map daysInYear [ 1 .. ( y — 1 ) ] )
+ ( sum $ map ( flip daysInMonth ( isLeapYear y ) ) ( monthsBefore m ) )
+ ( d — 1 )
where
monthsBefore January = [ ]
monthsBefore x = ( pred x ) : ( monthsBefore $ pred x )
( y , m , d ) = getYMD x

daysInMonth :: Month -> Bool -> Int
daysInMonth month leapYear
| month ` elem ` [ April , June , September , November ] = 30
| month == February = if leapYear then 29 else 28
| otherwise = 31

daysInYear year =
if isLeapYear year then 366 else 365

isLeapYear year
| year ` mod ` 400 == 0 = True
| year ` mod ` 100 == 0 = False
| year ` mod ` 4 == 0 = True
| otherwise = False

Кто сказал, что работать с датами сложно?

Теперь, имея прототип, попробуем написать аналогичный Perl-скрипт. Для удобства, помимо fp, я также использовал модули Method::Signatures::Simple и enum . Вот, что у меня получилось:

#!/usr/bin/env perl

# (c) Alexandr A Alexeev 2011 | http://remontka.com/

use strict ;
use warnings ;
use fp ;
use Method :: Signatures :: Simple ;

use enum qw / January February March April May June
July August September October November December /;
use enum qw / Monday Tuesday Wednesday Thursday Friday
Saturday Sunday /;

func isLeapYear ( $year ) {
return true if $year % 400 == 0 ;
return false if $year % 100 == 0 ;
return true if $year % 4 == 0 ;
false ;
}

func daysInYear ( $year ) {
isLeapYear ( $year ) ? 366 : 365 ;
}

func daysInMonth ( $month , $leapYear ) {
return 30 if member $month , ( April , June , September , November ) ;
return $leapYear ? 29 : 28 if $month == February ;
31 ;
}

func monthsBefore ( $month ) {
return ( ) if $month == January ;
return append $month — 1 , monthsBefore ( $month — 1 ) ;
}

# func daysFromEpoch($date) {
# my $rslt = sum ( map { daysInYear($_) }
# (1 .. $date->{year} — 1) );
# my $isLeap = isLeapYear($date->{year});
# $rslt += sum ( map { daysInMonth($_, $isLeap) }
# monthsBefore($date->{month}) );
# $rslt + $date->{day} — 1;
# }

func daysInYearsFromOneTo ( $year ) {
no warnings ‘recursion’ ;
return 0 if $year < 1 ;
return daysInYear ( $year ) + daysInYearsFromOneTo ( $year — 1 ) ;
}

# число дней с 1-го января 1-го года (не включая)
func daysFromEpoch ( $date ) {
my $isLeap = isLeapYear ( $date -> { year } ) ;
my $rslt = daysInYearsFromOneTo ( $date -> { year } — 1 ) ;
$rslt += sum ( map { daysInMonth ( $_ , $isLeap ) }
monthsBefore ( $date -> { month } ) ) ;
$rslt + $date -> { day } — 1 ;
}

func getDayOfWeek ( $date ) {
daysFromEpoch ( $date ) % 7 ;
}

func sysAdminDayInYear ( $year ) {
my @yulyDays = map { {
year => $year ,
month => July ,
day => $_ } } ( 1 .. 31 ) ;
end ( grep { getDayOfWeek ( $_ ) == Friday } @yulyDays ) ;
}

func softwareFreedomDayInYear ( $year ) {
my @septemberDays = map { {
year => $year ,
month => September ,
day => $_ } } ( 1 .. 30 ) ;
my @saturdays = grep { getDayOfWeek ( $_ ) == Saturday } @septemberDays ;
$saturdays [ 2 ] ;
}

# … your code here …

Обратите внимание на закомментированную версию daysFromEpoch($date) . Изначально я написал функцию именно таким образом и она даже работала, вот только код в строчке…

my $rslt = sum ( map { daysInYear ( $_ ) } ( 1 .. $date -> { year } — 1 ) ) ;

… очень сильно тормозил и выдавал кучу варнингов:

Deep recursion on subroutine «fp::sum» at path/to/fp.pm line 123.

У вас это не должно вызывать удивления, если вы посмотрите код функции fp::sum (хотя и так несложно догадаться, какой он), а также вспомните о том, что Perl, в отличие от Haskell, не является ленивым языком. Проблему можно обойти, например, заранее посчитав сумму первых 1900 элементов списка, но это не очень красиво. Оказывается, что требуемого эффекта можно добиться, заменив приведенную строку на вызов функции daysInYearsFromOneTo($year) :

func daysInYearsFromOneTo ( $year ) {
no warnings ‘recursion’ ; # не ругаемся на глубокую рекурсию
return 0 if $year < 1 ;
return daysInYear ( $year ) + daysInYearsFromOneTo ( $year — 1 ) ;
}

Кстати, работает эта функция подозрительно быстро. Проделки оптимизатора кода?

Как видите, писать на Perl в функциональном стиле совсем не сложно. Однако остается открытым вопрос о ленивых вычислениях и мемоизации . Ведь Perl, в отличие от Haskell, не умеет автоматизировать эти вещи (ровно как и параллелизм), хотя соответствующие модули есть на CPAN. См к примеру Data::Lazy (ленивость), Cache::LRU (кэширование/мемоизация), Scalar::Defer (ленивость + мемоизация) и subs::parallel (параллелизм).

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

Дополнение: Как выяснилось, не все так здорово и замечательно .

admin