Функциональное мышление: Тонны трансформаций

в 19:55, , рубрики: clojure, functional programming, groovy, java, jruby, scala, функциональное программирование

Нил Форд, Архитектор ПО, ThoughWorks Inc.
25 сентября 2012
перевод статьи Functional thinking: Tons of transformations

В функциональных языках программирования подходы к повторному использованию кода существенно отличаются от ООП языков, эту тему я исследовал в статье Связывание и композиция, часть 2. ООП языки стремятся иметь множество структур данных с различными операциями, в то время как функциональные языки используют несколько с небольшим количеством операций. ООП языки способствуют созданию класс-специфичных методов (class-spesific) и вы можете использовать повторно повторяющиеся части. Функциональные языки помогают достигнуть повторное использование путем поощрения применения общих преобразований в структурах данных, с помощью функций высшего порядка можно преобразовывать операции для частных случаев.

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

Основная цель этой части поспособствовать пониманию этой трансляции. Я возьму простые проблемы, которые требуют определиния и итерации, реализую решение на 5 различных языках (Java, Groovy, Clojure, JRuby и Scala) и двух функциональных фреймворках (Functional Java и Totally Lazy) для Java. Эти реализации одинаковы, однако детали отличаются от языка к языку.

Чистая Java

Проблема следующая — определить является ли число простым, делится только на себя и на 1. Существует несколько алгоритмов для определения простых числе (некоторые альтернативные решения всплывали в статье Связывание и композиция, часть 1). Я буду использовать решение, которое определяет делители числа, затем проверяет или сумма чисел равна исходному числу плюс 1, тогда ясно, что число простое. Это далеко не самый эффективный алгоритм, однако моя цель показать различные реализации общей коллекции методов, а не эффективность.

Чистая Java версия представлена в Листинге 1:

Листинг 1. Чистая Java реализация классификатора простых чисел

public class PrimeNumberClassifier {
    private Integer number;

    public PrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
        Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (Integer i = 2; i < number; i++)
            if (isFactor(i))
                factors.add(i);
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        for (int i : getFactors())
            sum += i;
        return sum;
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

Если вы читали предыдущие части серии Функциональное мышление, вы узнаете алгоритм в методе getFactors() в Листинге 1. Его ядро, метод isFactor(), который просеивает делители.


Groovy

Groovy добавил много различных функциональных конструкций в своем развитии, которые привели к реализации, представленной в Листинге 2, существенно отличающейся от Java реализации:

Листинг 2. Groovy классификатор простых чисел

class PrimeNumberClassifier {
  private int number;

  PrimeNumberClassifier(int number) {
    this.number = number
  }

  public def isFactor(int potential) {
    number % potential == 0;
  }

  public def getFactors() {
    (1..number).findAll { isFactor(it) }.toSet()
  }

  public def sumFactors() {
    getFactors().inject(0, {i, j -> i + j})
  }

  public def isPrime() {
    sumFactors() == number + 1
  }
}

Два метода, которые встречались в Листинге 1 изменились более чем просто синтаксически в Листинге 1. Во-первых, getFactors(), использует Groovy класс Range для представления чисел кандидатов. Метод findAll() применяет часть кода к каждому элементу коллекции и возвращает список, содержащий элементы для которых блок кода вернул значение true. Этот блок кода принимает один параметр, элемент к оценке. Я использую удобную Groovy нотацию для того, чтобы сделать блок кода более ясным. Например, он может быть написан как (1..number).findAdd {i-> isFactor(i) }, но повторение одного параметра избыточно. Groovy предоставляет возможность, представленную в Листинге 2 замены явного(explicit), самого параметра с помощью неявного(implicit) it.

Другой метод, стоящий внимания, представлен в Листинге 2, метод sumFactors(). Используя набор чисел, полученных из метода getFactors(), я вызываю inject(), который является методом коллекций Groovy, осуществляющий операцию fold. Метод inject() сочетает в себе каждый элемент коллекции используя блок кода, предоставленный вторым параметром, используя первый параметр как начальное значение. Параметр блок-кода в Листинге 2 — это {i, j -> i + j}, который возвращает сумму двух чисел. Метод inject() применяет этот блок, последовательно к каждому элементу и суммирует их.

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


Scala

Scala версия классификатора простых чисел представлена в Листинге 3:

Листинг 3. Классификатор простых чисел в Scala.

object PrimeNumberClassifier {
  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) =
    (1 to number) filter (isFactor(number, _))

  def sum(factors: Seq[Int]) =
    factors.foldLeft(0)(_ + _)

  def isPrime(number: Int) =
    sum(factors(number)) == number + 1
}

В дополнение к тому, что реализация в Scala выглядит короче, она отличается во многих вещах. Реализация представлена в виде object, а не class, так как мне нужен будет только один экземпляр. Метод factors() использует ту же реализацию, что и в Groovy, в Листинге 2, но используя другой синтаксис. Я применяю метод filter(аналог findAll() из Groovy) к диапазону числе от 1 до number, использую метод isFactor(), определенный в начале Листинга 3 как предикат. Scala позволяет использовать заполнители параметров, _ в нашем случае.

Метод sum() в Листинге 3 использует метод foldLeft() из Scala, который синонимически аналогичен inject() из Groovy. В этом случае, я использую ноль как начальное значение и заполнители для обоих параметров.


Clojure

Clojure — это современная реализация Lisp на базе JVM, имеющая довольно необычный синтаксис, представленный в Листинге 4:

Листинг 4. Классификатор простых чисел в Clojure

(ns prime)

(defn factor? [n, potential]
  (zero? (rem n potential)))

(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

(defn sum-factors [n]
  (reduce + (factors n)))

(defn prime? [n]
  (= (inc n) (sum-factors n)))

Все методы в Листинге 4 выглядят необычно для Java разработчиков, тем не менее это все тот же алгоритм. Метод (factor?) проверяет равен ли остаток (функция rem в Clojure) нулю. Метод (factors) использует метод (filter), который принимает 2 параметра. Первый параметр это предикат, блок кода, который необходимо выполнить над каждый элементом, ожидает логический результат (true/false) в том случае, если параметр проходит по критерию. Синтаксис #(factor? n %) представляет анонимные функции в Clojure, используя % как параметр-заменитель. Второй параметр в функции (filter) это непосредственно коллекция, которую необходимо отфильтровать, в данном случае набор чисел от 1 до target плюс 1; диапазон исключает последний элемент.

Метод (sum-factors) в Листинге 4, использует (reduce) метод, синоним inject() из Groovy и foldLeft() из Scala. В этом случае, операция простой оператор +, который в Clojure неотличим от других методов, принимающих 2 параметра и возвращающих результат.

Несмотря на то, что синтаксис может быть показаться сложным, после того как вы к нему привыкните код в Clojure будет выглядеть выразительно. Так же как и в версии Groovy, хорошее именование методов имеет значение, несмотря на то что функции однострочники.


JRuby

JRuby — это реализация Ruby на базе JVM, получившая много различных функциональных конструкций в процессе развития. Рассмотрим следующую (J)Ruby реализацию классификатора простых чисел в Листинге 5:

Листинг 5. Классификатор простых чисел в JRuby

class PrimeNumberClassifier
  def initialize(num)
    @num = num
  end

  def factor?(potential)
    @num % potential == 0
  end

  def factors
    (1..@num).select { |i| factor?(i) }
  end
    
  def sum_factors
    factors.reduce(0, :+)
  end

  def prime?
    (sum_factors == @num + 1)
  end
end

Метод factors в Листинге 4 добавляет синоним select для findAll из Groovy и filter из Scala и Clojure. Одна из замечательных возможностей JRuby это возможность легко использовать псевдонимы методов, используя более удобные имена для методов в разных конекстах. Действительно JRuby включает псевдоним find_all для select, но это не является общей практикой в идиоматическом коде.

Для метода sum_factors в Листинге 5, я использую метод reduce из JRuby, мимикрируя другие языки. В JRuby, как и в Clojure, операторы это методы с забавными именами; Ruby позволяет мне специфицировать метод plus по символу, :+. В целях улучшения читаемости, Ruby как и Clojure позволяет добавлять знак вопроса в конце метода, ожидая возврата логического значения. И, в соответствии со своей природой, Ruby включает в себя метод inject псевдоним для reduce.


Functional Java

Не будем пропускать тех, кто использует Java, есть несколько функциональных библиотек, которые расширяют Java функциональными конструкциями. Functional Java как раз такой фреймворк. Реализация классификатора простых чисел, в Java c Functional Java, представлена в Листинге 6:

Листинг 6. Классификатор простых чисел в Functional Java

public class FjPrimeNumberClassifier {
    private int number;

    public FjPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public List<Integer> getFactors() {
        return range(1, number + 1)
                .filter(new F<Integer, Boolean>() {
                    public Boolean f(final Integer i) {
                        return isFactor(i);
                    }
                });
    }

    public int sumFactors() {
        return getFactors().foldLeft(fj.function.Integers.add, 0);
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

Метод getFactors() в Листинге 6, использует метод filter() на диапазоне (так же исключающий, как и в Clojure, поэтому number + 1 в определении диапазона). Так как Java пока не имеет в наличии функций высшего порядка, Functional Java мошенничает используя экземпляры анонимных внутренних классов, встроенного класса F, параметризируя типы используя дженерики.

Как и в Scala, Functional Java имеет метод foldleft(), принимающий в этом случае предопределенный блок кода, которые суммирует значения чисел и начальное значение.


Totally Lazy

Totally lazy (прим. перев.: абсолютно ленивый) — это функциональная библиотека для Java, которая добавляет несколько ленивых коллекций в Java. Ленивые структуры данных не предопределяют элементов, а кодируют правила, как генерировать следующее значение всякий раз, когда оно будет запрошено. Классификатор простых чисел реализованный в Totally Lazy представлен в Листинге 7:

Листинг 7. Классификатор простых числе в Totally Lazy

public class TlPrimeNumberClassifier {
    private int number;

    public TlPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(Integer potential) {
        return (number % potential) == 0;
    }

    private List<Integer> listOfPotentialFactors() {
        List<Integer> results = new ArrayList<Integer>();
        for (int i = 1; i <= number + 1; i++)
            results.add(i);
        return results;
    }

    public boolean isPrime() {
        return (this.number + 1) ==
            Sequences.init(listOfPotentialFactors())
                     .filter(new Predicate<Integer>() {
                         @Override
                         public boolean matches(Integer other) {
                             return isFactor(other);
                      }})
                     .foldLeft(0, sum())
                     .intValue();
    }
}

Метод isPrime() в Листинге 7, использует класс Sequences, инициализированный список потенциальных делителей(это все числа от 1 до целевого), потом применяет метод filter(). В Totally Lazy, метод filter() ожидает подкласс класса Predicate, многие из которых реализованы для общих классов. В моем примере, я перегружаю метод matches(), обеспечивая мой метод isFactor() возможностью определить исключения. После того как у меня есть список делителей, я использую foldLeft() метод, используя метод sum() для операции свертки.

В примере, показанном в Листинге 7, метод isPrime() выполняет основную нагрузку. Тот факт, что все структуры данных в Totally Lazy ленивые добавляет сложности когда вы пытаетесь их комбинировать. Рассмотрим версию метода getFactors(), показанную в Листинге 8:

Листинг 8. getFactors с ленивым итератором

public Iterator<Integer> getFactors() {
    return Sequences
            .init(listOfPotentialFactors())
            .filter(new Predicate<Integer>() {
                @Override
                public boolean matches(Integer other) {
                    return isFactor(other);
                }
            })
            .iterator();
}

В методе getFactors тип возвращаемого значения Iterator, однако это ленивый итератор, а это значит, что коллекция не будет иметь значения до тех пор пока вы не выполните итерацию. Это вносит сложности в тестирование. Рассмотрим юнит тест для примера из Листинга 8, показанный в Листинге 9:

Листинг 9. Тестирование ленивых коллекций в Totally Lazy

@Test
public void factors() {
    TlPrimeNumberClassifier pnc = new TlPrimeNumberClassifier(6);
    List<Integer> expected = new ArrayList<Integer>() {{
        add(1);
        add(2);
        add(3);
        add(6);
    }};
    Iterator<Integer> actual = pnc.getFactors();
    assertTrue(actual.hasNext());
    int count = 0;
    for (int i = 0; actual.hasNext(); i++) {
        assertEquals(expected.get(i), actual.next());
        count++;
    }
    assertTrue(count == expected.size());
}

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

Несмотря на то, что это вполне реально написать с помощью Totally Lazy версию такую же хорошую как и другие, однако вы можете застать себя погруженным в борьбу все с более витиеватыми и витиеватыми структурами данных, чудными конструкциями типа

<Iterator<Iterator<Number>>>


Вывод

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

<Iterator<Iterator<Number>>>

).

В следующей части, я продолжу исследование сходных качеств в трансформациях, рассмотрев map.

Автор: Sigrlami

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js