Pragmatic Perl

Выпуск 11. Январь 2014

Обход дерева директорий на Perl и Haskell (часть 1)

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

Функциональное программирование неизбежно проникает в массы. Даже такие безнадежные языки, как Java и C++ больше не могут сопротивляться здравому смыслу и обзаводятся анонимными функциями (или «лямбда-выражениями»).

Что уж говорить о Perl, в котором анонимные функции ($subref = sub { ... }) и классические комбинаторы вроде map и grep уже давно не новость.

С другой стороны, наличие в языке функциональных элементов побуждает программистов на этом языке считать «Зачем мне функциональные языки, я и на своем языке могу писать в функциональном стиле».

И действительно, Perl достаточно выразителен, чтобы на нем можно было реализовать множество функциональных идиом, что блестяще демонстрирует книга «Higher-order Perl» авторства Mark Jason Dominus.

Все же, есть ли какая-то выгода от написания кода на Haskell по сравнению с Perl? Чтобы это выяснить, я решил взять пример из Higher-Order Perl и переписать его на Haskell.

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

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

Пример, который мы будем рассматривать, описывается в главе 1.6 и представляет собой рекурсивный обход дерева директорий. Задача здесь — не просто обойти дерево с конкретной целью, а написать «обобщенный» обход, который можно использовать, например, для:

• получения дерева в виде структуры данных;
• поиска файла в дереве;
• печати списка директорий;
• поиска поломанных символических ссылок.

и т.д.

Чтобы наша функция могла совершать разные действия, мы параметризуем ее двумя коллбеками — для файлов и директорий. Вот функция dir_walk, написанная Марком на Perl:

# From Higher-Order Perl by Mark Dominus, published by Morgan Kaufmann Publishers
# Copyright 2005 by Elsevier Inc
# LICENSE: http://hop.perl.plover.com/LICENSE.txt

sub dir_walk {
  my ($top, $filefunc, $dirfunc) = @_;
  my $DIR;

  if (-d $top) {
    my $file;
    unless (opendir $DIR, $top) {
      warn "Couldn't open directory $code: $!; skipping.\n";
      return;
    }

    my @results;
    while ($file = readdir $DIR) {
      next if $file eq '.' || $file eq '..';
      push @results, dir_walk("$top/$file", $filefunc, $dirfunc);
    }
    return $dirfunc->($top, @results);
  } else {
    return $filefunc->($top);
  }
}

Вот довольно близкая трансляция этого кода на Haskell:

import System.FilePath
import System.Directory

dir_walk :: FilePath -> (FilePath -> IO a) -> (FilePath -> [a] -> IO a) -> IO a
dir_walk top filefunc dirfunc = do
  isDirectory <- doesDirectoryExist top
  
  if isDirectory
    then do
      files <- getDirectoryContents top
      let nonDotFiles = filter (not . (`elem` [".", ".."])) files
      results <- mapM (\file -> dir_walk (top </> file) filefunc dirfunc) nonDotFiles
      dirfunc top results
    else
      filefunc top

Поскольку это может быть вашим первым знакомством с Haskell, давайте потратим немного времени и сравним версии на Perl и на Haskell.

Первое, что бросается в глаза в коде на Haskell — сигнатура типа (строка 4). Сигнатуры типов в Haskell в большинстве случаев, включая этот, опциональны — компилятор достаточно умен, чтобы самостоятельно вывести тип. Тем не менее, обычно программисты выписывают сигнатуры, потому что это дополняет документацию и упрощает чтение и понимание кода. Никто не возбраняет сначала написать тело функции, а затем спросить у компилятора сигнатуру и скопировать ее в код, хотя при написании сколь-нибудь сложных функций сигнатуру обычно пишут еще до кода самой функции — это позволяет сразу ответить себе на вопрос: «Что эта функция должна делать?».

Давайте попробуем расшифровать эту сигнатуру. Когда мы видим последовательность типов, разделенных стрелочками, мы должны интерпретировать это как функцию, у которой последний тип является типом возвращаемого значения, а все предыдущие — типами аргументов. Как вы догадываетесь, такая нотация возникла не просто так — на то есть глубокие причины, но мы сейчас на них останавливаться не будем.

Итак, dir_walk — функция, возвращающая IO a и принимающая три аргумента, типы которых FilePath, FilePath -> IO a и FilePath -> [a] -> IO a соответственно.

Здесь a — переменная типа, обозначающая тип результата, который мы хотим получить в результате обхода. Например, если мы хотим узнать суммарный размер директории, то при вызове функции вместо a будет подставлен тип Integer.

Чем отличается IO a от a? IO a — тип действий, которые, будучи исполненными, возвращают значение типа a. Действие можно исполнить (и получить его результат) только в контексте другого действия, используя следующий синтаксис:

action_b :: IO b
action_b = do
  result_of_a <- action_a :: IO a
  -- отсюда и до конца do-блока result_of_a имеет тип a
  ...

Функцию, у которой тип возвращаемого значения имеет вид IO a, можно упрощенно понимать как функцию, возвращающую a и при этом совершающую какие-либо побочные эффекты (ввод-вывод, работа с файловой системой и сетью, и т.д.). Разница в том, что, в отличие от Perl, соответствующие действия не выполняются каждый раз, когда вызов функции встретился в коде. Например, мы можем написать

action_b :: IO b
action_b = do
  let x = action_a :: IO a
  -- отсюда и до конца do-блока x имеет тип IO a
  ...

Здесь мы дали действию action_a альтернативное имя x, но от этого само действие не выполнилось, и его результата мы не получили. Чтобы выполнить действие как часть другого действия, мы должны использовать синтаксис <-, как показано выше.

В скомпилированной программе действие выполняется только если оно (прямо или косвенно) является частью главного действия программы — действия под именем main (по аналогии с языком C).

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

Перейдем теперь к собственно коду функции dir_walk. На строке 6 мы видим пример работы с действиями с использованием уже знакомого нам синтаксиса <-. Дело в том, что функция doesDirectoryExist (аналог оператора -d из Perl) имеет тип FilePath -> IO Bool, поскольку для получения ответа требуется доступ к файловой системе. Строчка isDirectory <- doesDirectoryExist top является аналогом $isDirectory = -d $top; — она выполняет действие doesDirectoryExist top :: IO Bool и записывает результат в переменную isDirectory. Однако, если бы мы наивно написали

if doesDirectoryExist top
  then ...
  else ...

то получили бы ошибку типов, потому что конструкция if ожидает выражение типа Bool, а не IO Bool.

Аналогично, в строке 10 выполняется действие getDirectoryContents top типа IO [FilePath], и результат записывается в переменную files.

В строке 11 мы отбрасываем «виртуальные» директории . и .. (по аналогии со строкой 18 из кода на Perl). Обратите внимание, что функция filter не требует выполнения каких-либо побочных эффектов, поэтому мы используем синтаксис let, а не <-. В общем случае, чтобы выяснить, требует ли функция выполнения действий, надо посмотреть на ее тип. Так, функция filter имеет тип

filter :: (a -> Bool) -> [a] -> [a]

В строке 12 мы рекурсивно вызываем функцию dir_walk, по аналогии со строкой 19 кода на Perl, для каждого файла или поддиректории в нашей директории. Для этого используется функция

mapM :: (a -> IO b) -> [a] -> IO [b]

которая применяет функцию к каждому элементу списка nonDotFiles, выполняет получившиеся действия и объединяет результаты в новый список.

Наконец, в строках 13 и 15 мы вызываем коллбеки, подобно строкам 21 и 23 кода на Perl. Здесь мы не использовали синтаксис <-, чтобы записать результат в переменную — вместо этого, результат действия становится возвращаемым значением нашей функции, прямо как в Perl. Альтернативно, блок вида

do
  ...
  dirfunc top results

можно заменить на

do
  ...
  result <- dirfunc top results
  return result

Здесь result имеет тип a (поскольку это результат действия типа IO a), а функция return (тип которой a -> IO a) делает из значения «тривиальное» действие, которое возвращает результат без каких-либо побочных эффектов.

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

Как мы видим, код на Haskell лишь слегка отличается от функционального кода на Perl. Различия обсусловлены тем, что в Haskell функции осуществляют доступ к файловой системе не напрямую, а через действия, а также мелкими различиями в стандартных библиотеках наших языков.

На первый взгляд, морока с «действиями» не оправдывает себя и лишь запутывает. Однако, в следующем выпуске журнала мы познакомимся с типами действий помимо IO, которые позволят решить слегка модифицированную задачу по обходу дерева гораздо проще, чем без них.

Чтобы узнать больше о Haskell и попробовать его в действии, рекомендую слайды со встречи одесской группы пользователей Haskell. Там вы найдете ссылки на учебные материалы, инструкции по установке и другую полезную информацию.

Если вам кажется, что вы не поняли что-то важное в этой статье, пожалуйста, мне, и я постараюсь прояснить это в следующем номере. Дальше будет сложней и интересней!

■ Роман Чепляка