Eugene Kirpichov (antilamer) wrote,
Eugene Kirpichov
antilamer

Джава: Читабельность и немного ФП

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

Также речь пойдет о том, как рефакторить код, неосознанно написанный в функциональном стиле (типа new AndFilter(new FieldMatchesPatternFilter(new FieldReference("name"), ".*John.*"), new BlaBlaBlaFilter())), в читаемую и лаконичную форму.

DISCLAIMER:
Большая часть из этого не имеет отношения к собственно ФП. В основном будет про повышение читаемости некоторых часто встречающихся паттернов, которые особенно часто встречаются при использовании функционального стиля, и без которых об ФП не может быть и речи.

Про приемы собственно ФП будет совсем немного, ближе к концу.


Беды наши:
- "kingdom of nouns" (традиция считать все на свете существительным и считать, что вычислить сумму двух чисел можно только, создав экземпляр ЧисленногоСумматора и любезно послав ему сообщение)
- Отсутствие встроенного синтаксиса для конструирования данных - пар, списков итп
- Плохой синтаксис генериков и отсутствие нормального вывода типов и нормального полиморфизма
Орудия наши - import static, varargs и немного пороха в пороховницах.

1. Увеличиваем читаемость данных


Совсем плохо:
private static final Set<String> INTERESTING_TAGS = new HashSet<String>();
Map<String,Integer> WEIGHTS = new HashMap<String,Integer>

static {
    INTERESTING_TAGS.add("A");
    INTERESTING_TAGS.add("FORM");
    INTERESTING_TAGS.add("INPUT");
    INTERESTING_TAGS.add("SCRIPT");
    INTERESTING_TAGS.add("OBJECT");

    WEIGHTS.put("bad", -2);
    WEIGHTS.put("poor", -1);
    WEIGHTS.put("average", 0);
    WEIGHTS.put("nice", 1);
    WEIGHTS.put("outstanding", 3);
}


Плохо:
private static final Set<String> INTERESTING_TAGS = new HashSet<String>(Arrays.asList(new String[] {
    "A","FORM","INPUT","SCRIPT","OBJECT"
    }));


for(double guessedScale : new double[] {0.01, 0.1, 1, 10, 100}) {
    ...
}



Хорошо:
public class CollectionUtils {
    public static T[] ar(T... ts) {return ts;}

    public static Set<T> set(T... ts) {
        return new HashSet<T>(Arrays.asList(ts));
    }

    public static Map<K,V> zipMap(K[] keys, V[] values) {...}
}

import static CollectionUtils.set;
import static CollectionUtils.ar;

private static final Set<String> INTERESTING_TAGS = set("A","FORM","INPUT","SCRIPT","OBJECT");

for(double guessedScale : ar(0.01, 0.1, 1, 10, 100)) {
    ...
}

Map<String,Integer> WEIGHTS = zipMap(
    ar("bad", "poor", "average", "nice", "outstanding"),
    ar(-2,    -1,     0,         1,      3));




Казалось бы, как просто! Обыкновенная абстракция конструкторов данных, вторая глава SICP.
Особенно ярко проявляется в юниттестах, когда надо тестировать на разных сложных структурах данных.
В этом случае очень часто оправдано даже кодирование структур в строке и написание маленького парсера. Например:
assertTrue(GraphAnalyzer.isConnected(graph("1->2 2->3 3->1")));


2. Увеличиваем читаемость комбинаторов


Плохо:
Filter f = new AndFilter(first, second);


Хорошо:
public abstract class Filters {
    public static Filter and(Filter a, Filter b) {return new AndFilter(a,b);}
}

import static Filters.*;

Filter f = and(first,second);


Еще лучше:

public abstract class Filter {
    Filter and(Filter other) {return Filters.and(this,other);}
}
Filter f = first.and(second).and(third);


Совсем хорошо:
public abstract class Filters {
    public static Filter ALWAYS_TRUE = new AlwaysTrue();

    public static Filter and(Filter... filters) {
        Filter res = ALWAYS_TRUE;
        for(Filter f : filters) res = res.and(f);
        return res;
    }
}



Еще пример.

Плохо:
enum StringComparisonKind {EXACT, REGEX, GLOB}
enum StringPosition {ANYWHERE, WHOLE_STRING, STARTS_WITH, ENDS_WITH}
public class StringCondition {
    ...

    public StringCondition(String pattern, StringComparisonKind comparisonKind, StringPosition position) {...}
}


conditions.add(new StringCondition("foo", StringComparisonKind.REGEX, StringPosition.ANYWHERE))



Хорошо:
import static StringComparisonKind.*;
import static StringPosition.*;
public class StringConditions {
    public static regexWhole(String regex) {return new StringCondition(regex, REGEX, WHOLE_STRING);}
    public static regexAnywhere(String regex) {return new StringCondition(regex, REGEX, ANYWHERE);}
    public static exactWhole(String pattern) {return new StringCondition(pattern, EXACT, WHOLE_STRING);}
    ...
}


import static StringConditions.*;
conditions.add(regexAnywhere("foo"));


Абстракция, абстракция и еще раз абстракция. Удивительно, насколько ее обычно недооценивают.

3. Увеличиваем читаемость анонимных классов


Выносим их в константы или хотя бы локальные переменные:

Плохо:
List<Order> orders = CollectionUtils.flatten(CollectionUtils.map(customers, new Function<Customer, List<Order>>() {
    public List<Order> apply(Customer customer) {
        return customer.getOrders();
    }
}));


Хорошо:
import static CollectionUtils.*;

private static final Function<Customer, List<Order>> GET_ORDERS = new Function<Customer, List<Order>>() {
    public List<Order> apply(Customer customer) {
        return customer.getOrders();
    }
};

List<Order> orders = flatten(map(customers, GET_ORDERS));


4. Увеличиваем читаемость "просто классов"


Плохо:
    CustomerProcessor taxes = new ComputeTaxesCustomerProcessor();


Эти суффиксы не дают вообще ничего. Если бы у джавы не было package'ей или статической типизации, то это было бы оправдано, чтобы не засорять глобальный namespace или случайно не перепутать один And с другим - но они есть, и суффиксы не нужны - так же как, например, венгерская нотация.

Хорошо:
    CustomerProcessor taxes = new ComputeTaxes();



5. Увеличиваем читаемость генериков - poor man's typedef


Плохо:
class FooEverythingDoer {
    ...
    Map<String, String> getProperties(Foo foo) {...}
    void putProperties(Foo foo, Map<String, String> properties) {...}
    Map<Foo, Map<String, String>> getPropertiesBatch(Iterable<Foo> foos) {...}
    Foo findByProperties(Map<String, String> partOfProperties) {...}
    ...
}


Хорошо:
class Properties extends Map<String,String> {
    (constructors matching super here)
}


class FooEverythingDoer {
    ...
    Properties getProperties(Foo foo) {...}
    void putProperties(Foo foo, Properties properties) {...}
    Map<Foo, Properties> getPropertiesBatch(Iterable<Foo> foos) {...}
    Foo findByProperties(Properties partOfProperties) {...}
    ...
}




Плохо:
class MagicBarMerger {
    public void mergeIntoDb(List<MagicBar> bars) {
        List<MagicBar> existingBars = barDao.getAllBars();
        Map<Integer, List<Pair<MagicBar, MagicBar>>> pairsById = joinOnId(bars, existingBars);
        List<MagicBar> merged = new ArrayList<MagicBar>();
        for(Pair<MagicBar, MagicBar> pair : pairsById) {
            merged.add(merge(pair));
        }
        barDao.removeAllBars():
        barDao.putBarsBatch(merged);
    }

    private Map<Integer, Pair<MagicBar, MagicBar>> joinOnId(List<MagicBar> as, List<MagicBar> bs) {
        ....
    }

    private MagicBar merge(Pair<MagicBar, MagicBar> bars) {
        ....
    }
}



Хорошо:
class MagicBarMerger {
    private static class Bars extends Pair<MagicBar,MagicBar> {(constructor matching super)}

    public void mergeIntoDb(List<MagicBar> bars) {
        List<MagicBar> existingBars = barDao.getAllBars();
        Map<Integer, Bars> pairsById = joinOnId(bars, existingBars);
        List<MagicBar> merged = new ArrayList<MagicBar>();
        for(Bars bars : pairsById) {
            merged.add(merge(bars));
        }
        barDao.removeAllBars():
        barDao.putBarsBatch(merged);
    }

    private Map<Integer, Bars> joinOnId(List<MagicBar> as, List<MagicBar> bs) {
        ....
    }

    private MagicBar merge(Bars bars) {
        ....
    }
}


6. Увеличиваем читаемость генериков-2, используем вывод типов джавы


Плохо:
Map<Integer, List<String>> namesById = new HashMap<Integer, List<String>>();


Хорошо:
public class CollectionUtils {
    public static <K,V> Map<K,V> newMap() {
        return new HashMap<K,V>();
    }
}

import static CollectionUtils.newMap;
Map<Integer, List<String>> namesById = newMap();



Функции ar(T... ts) и set(T... ts) в правиле 1 - из этой же оперы.


7. Увеличиваем отлаживаемость этого хозяйства


В отладчике неприятно бывает, забравшись в кишки объекту, увидеть, что его класс называется FooProcessor$3$1, а у его полей с именами innerProcessor и value - класс FooProcessor$4$2 и значение "1".
Поэтому следует все классы, объекты которых "уплывают" из локальной области видимости метода (а таких - абсолютное большинство, согласно правилу №3), делать неанонимными и давать им осмысленные имена.
Еще лучше - писать им toString. Это совсем недолго, а при отладке помогает неимоверно.

Комбинаторы высшего порядка типа AND или OR часто применяются для склеивания заранее неизвестного числа "слагаемых". При этом в памяти создается рекурсивная структура объектов - AND(x, AND(y, And(z, AND(...)))). Такую структуру неприятно просматривать в отладчике, и еще неприятней отлаживать ее пошагово.
Поэтому иногда оправдано сделать, чтобы класс AND склеивал не 2, а произвольное число фильтров, а статический factory-метод Filters.and(first, second) (вы ведь не забыли абстрагировать в него конструктор, не так ли? ;) ) проверял, не является ли first или second уже и так AND'ом и, по возможности, склеивал их в один большой AND.
Тогда рекурсивная структура превратится в итеративную и будет одно удовольствие смотреть ее в отладчике, сериализовывать в XML и шастать отладчиком по циклу над слагаемыми.


****
Теперь тяжелая артиллерия, имеющая отношение к собственно ФП:

0. Прочитайте J vocabulary ;)


И поймите, что делают примитивные функции и комбинаторы. Применять необязательно, достаточно просто понять, что они делают. http://www.jsoftware.com/help/dictionary/vocabul.htm
J - уникальный пример функционального языка без статической типизации и даже без замыканий. По сути, это означает, что большинство комбинаторов J можно реализовать и использовать и на джаве, не скатываясь на анонимные классы.
Мои любимые комбинаторы - "&." (f &. g = f^-1 . g . f), "/." (x f/. y = вектор значений f(g) для каждой группы g вектора x по ключу y) и "/:" (x /: y - вектор x, отсортированный по вектору y)



8. Карринг по последнему аргументу


(Напомню a rule of thumb: последний аргумент должен быть самым часто изменяющимся - тогда его будет удобно каррить)
Плохо:
public class CollectionUtils {
    public static <T> List<T> filter(Filter<T> filter, List<T> ts) {...}
    public static <K, V> List<V> map(Function<K, V> fun, List<K> ts) {...}
}


Хорошо:
public class CollectionUtils {
    public static <T> Function<List<T>, List<T>> filter(Filter<T> filter) {...}
    public static <K, V> Function<List<K>, List<V>> map(Function<K, V> fun) {...}
}


Почему:
Потому что теперь комбинаторам высшего порядка есть что комбинировать:
public class FP {
    public static <A,B,C> Function<A,C> chain(Function<A,B> first, Function<B,C> second) {...}
}

или так:

public abstract class Function<K,V> {
    public abstract V apply(K argument);
    
    public Function<K,U> then(Function<V,U> second) {return FP.chain(this, second);}
}


А теперь можно писать что-нибудь такое

Пусть Order = (Customer, Product, Time)

public abstract class Aggregate<K,V> extends Function<Collection<K>, V> {}

// select K,V from S group by K
public abstract class Partitioned<S,K,V> extends Function<Collection<S>, Map<K, V>> {}

Function<Order,Product> getProduct() {..}
Function<Product,Price> getPrice() {..}
Filter<Product> categoryEquals(String pat) {..}
Partitioned<Order,Month,T> byMonth(Aggregate<Order, T> inner) {..}


И далее

public Partitioned<Order,Month,Customer> mostGenerousCustomerByMonth() {
    Function<Order, Price> ORDER_PRICE = getProduct().then(getPrice());
    Aggregate<Order, Order> MOST_EXPENSIVE_ORDER = 
        over(getProduct().then(categoryEquals("Cars")), maximizeBy(ORDER_PRICE));
    return byMonth(MOST_EXPENSIVE_ORDER.then(Order.GET_CUSTOMER));
}

{
    ...
    Map<Month, Customer> goodGuysIn2007 = filter(timeBetween(year(2007), year(2008)))
                                    .then(mostGenerousCustomerByMonth())
                                    .apply(ourOrders);
    ...                                    
}
    


9. Пары и бинарные отношения


Не так-то легко найти проект, в котором нету самописного класса Pair и не используются какие-нибудь List<Pair<Foo,Bar>>.
Мне, лично, довольно часто хочется то собрать значения функции foo над левыми частями пар, то собрать пары из foo на левой части и bar на правой, то оставить только пары, у которых правая часть удовлетворяет предикату qux, то еще что.
Было бы возмутительным не учредить для этого комбинаторы и не присобачить к злосчастному List<Pair<Foo,Bar>> возможность иметь их в качестве member methods:

class BiRelation<L,R> {
    ...
    List<Pair<L,R>> allEntries() {..}
    static BiRelation<L,R> rel(List<Pair<L,R>> pairs) {..}
    BiRelation<R,L> flip() {..}
    BiRelation<L,R> filterL(Predicate<L> p) {..}
    BiRelation<R,L> filterR(Predicate<R> p) {return flip().filterL(p).flip();}
    BiRelation<L,List<R>> compressL() {..}
    BiRelation<List<L>,R> compressR() {return flip().compressL().flip();}
    BiRelation<P,Q> fmap(Function<L,P> f, Function<R,Q> g) {return rel(map(pair(f,g)).apply(allEntries()));}
    List<T> map(Function<Pair<L,R>, T> fun) {...}
    ...
}


Здесь также иллюстрируется еще одна классная штука - "worker/wrapper" (я про flip()/.../flip())

Теперь можно, например, написать поиск в ширину:
    private static BiRelation<Node, Node> bfs(BiRelation<Node, Node> graph, Node root) {
        Set<Node> roots = singleton(root);
        Set<Node> reached = new LinkedHashSet<Node>();
        reached.add(root);
        List<Pair<Node,Node>> res = newList();
        while(true) {
            BiRelation<Node,Node> nextLayer = graph.filterL(memberOf(roots)).filterR(not(memberOf(reached)));
            if(nextLayer.isEmpty())
                break;
            res.addAll(nextLayer.allEntries());
            reached.addAll(roots = nextLayer.rightSet());
        }
        return rel(res);
    }


Или преобразование Шварца (при сортировке массива по значению функции применяется для того, чтобы не считать функцию от одного и того же элемента несколько раз. Суть - приклеиваем к списку элементов список значений функции на них, сортируем по второй части и отклеиваем обратно):
public static Function<T,Pair<T,U>> attach(Function<T,U> fun) {..}
public static Function<Pair<T,U>,T> detachR() {..}
public static Function<Pair<T,U>,U> detachL() {..}

public static <U extends Comparable<? super U>> 
Function<List<T>,List<T>> schwartzSortBy(Function<T,U> fun) 
{
    return map(attach(fun)).then(sortBy(second())).then(map(detachR()));
}


Или вот:
BiRelation<Customer, Order> customer_order = ...
BiRelation<Product, Integer> product_buyersCount = customer_order.fmap(ID, GET_PRODUCT).compressR().fmap(SIZE, ID).flip();


И много чего другого можно написать.
Вообще, обожаю flip() - есть много симметричных вещей - пары, отношения, обратимые функции, Map'ы...
А тройные отношения можно поворачивать - TriRelation<A,B,C>.rotate213() и т.п. Но злоупотреблять этим не стоит.

10. Крупные комбинаторы


Есть такая архитектура процессоров - VLIW, Very Large Instruction Word. В одной инструккции помещается сразу несколько действий - например, перемножить и сложить с аккумулятором; поделить и вычислить квадратный корень; отправить e-mail и переключить разрешение экрана :) Там это делается для повышения паралеллизма на уровне команд и вообще повышения быстродействия.
В случае ФП на джаве это можно делать для повышения читаемости и понижения количества скобок. Ну и для быстродействия тоже - крупный комбинатор можно реализовать не через мелкие, а более эффективно.

Вместо:
Aggregate<Customer, Order> everyonesOrdersIn2008 = map(GET_ORDERS).then(concat()).then(filter(timeBetween(year(2007), year(2008))))


Делаем так:
public static <K,V> Aggregate<K,V> concatMapOver(Function<K,V> fun, Filter<K> filter) {...}


Aggregate<Customer, Order> everyonesOrdersIn2008 = concatMapOver(GET_ORDERS, timeBetween(year(2007), year(2008)));



Так-то.
Subscribe

  • The Dataflow Model

    В VLDB вышла статья от нашей команды про унификацию streaming/batch, event-time processing, windowing, triggers, вот это все. The Dataflow Model: A…

  • Коллеги рассказали задачку

    Есть бесконечная река с пристанями, пронумерованными всеми целыми числами (..., -2, -1, 0, 1, 2, ...). По реке плывет корабль-призрак, из неизвестной…

  • Про подкаст DevZen

    С большой радостью, благодаря gliv, послушал подкаст http://devzen.ru/episode-0038, где обсуждался в т.ч. и Cloud Dataflow (начало…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 64 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →

  • The Dataflow Model

    В VLDB вышла статья от нашей команды про унификацию streaming/batch, event-time processing, windowing, triggers, вот это все. The Dataflow Model: A…

  • Коллеги рассказали задачку

    Есть бесконечная река с пристанями, пронумерованными всеми целыми числами (..., -2, -1, 0, 1, 2, ...). По реке плывет корабль-призрак, из неизвестной…

  • Про подкаст DevZen

    С большой радостью, благодаря gliv, послушал подкаст http://devzen.ru/episode-0038, где обсуждался в т.ч. и Cloud Dataflow (начало…