Удаление дублирования кода - PullRequest
9 голосов
/ 14 сентября 2010

Я пытаюсь создать небольшую функциональную библиотеку программирования для Java (просто почесать свой собственный зуд). При определении функций высшего порядка для List с, Set с и Map с я столкнулся с такой проблемой: функции, которые принимают коллекцию и возвращают коллекцию того же типа, имеют почти такая же реализация, и все же ее необходимо переопределить для каждой структуры данных - List s, Set s и Map s.

Например, вот реализация функции map для List с и Set с:

public static <A, B> List<B> map(
  List<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  List<B> ys = new ArrayList<B>();
  for(A a : xs) {
    ys.add(transformer.apply(a));
  }
  return ys;
}

public static <A, B> Set<B> map(
  Set<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  Set<B> ys = new HashSet<B>();
  for(A a : xs) {
    ys.add(transformer.apply(a));
  }
  return ys;
}

A filter Функция:

public static <A> List<A> filter(
  List<? extends A> xs, 
  Func1<? super A, Boolean> predicate
) {
  List<A> ys = new ArrayList<A>();
  for(A a : xs) {
    if(predicate.apply(a)) {
      ys.add(a);
    }
  }
  return ys;
}

public static <A> Set<A> filter(
  Set<? extends A> xs, 
  Func1<? super A, Boolean> predicate
) {
  Set<A> ys = new HashSet<A>();
  for(A a : xs) {
    if(predicate.apply(a)) {
      ys.add(a);
    }
  }
  return ys;
}

Как видно из этого примера, тела реализаций для Set и List почти одинаковы.

В моей библиотеке много функций, таких как map и filter, и каждая из них определяется трижды для каждого типа коллекций, которые меня интересуют (например, List, Set и Map ). Это приводит к большому дублированию кода и запаху кода. Я хотел знать, есть ли какой-нибудь способ в Java, который помог бы мне избежать всего дублирования кода.

Любая помощь будет принята с благодарностью. Спасибо.

EDIT:

Func1 - это интерфейс, определяемый как:

interface Func1<A, B> {
  public B apply(A a);
}

Ответы [ 5 ]

6 голосов
/ 14 сентября 2010
public static <A, B> List<B> map(
  List<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  List<B> ys = new ArrayList<B>();
  map(xy, transformer, ys);
  return ys;
}

public static <A, B> Set<B> map(
  Set<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  Set<B> ys = new HashSet<B>();
  map(xy, transformer, ys);
  return ys;
}
private static <A, B> map(
  Collection<? extends A> xs, 
  Func1<? super A, ? extends B> transformer,
  Iterable<B> ys
) {
  for(A a : xs) {
    ys.add(transformer.apply(a));
  }
}

Работа выполнена.

Обратите внимание, что для API Java характерно передавать изменяемую коллекцию, а не создавать новую в методе. Лично я не фанат изменчивости на уровне коллекций, но это то, с чем мы должны работать (на Java).

(мне не нравятся A и B как общие параметры для такого рода вещей.)

Или вы можете использовать фабрику:

public static <A, B> List<B> map(
  List<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  return map(xs, transformer, new CollectionFactory<B, List<B>>() {
      public List<B> create() { return new ArrayList<B>(); }
  });
}

public static <A, B> Set<B> map(
  Set<? extends A> xs, 
  Func1<? super A, ? extends B> transformer
) {
  return map(xs, transformer, new CollectionFactory<B, Set<B>>() {
      public Set<B> create() { return new HashSet<B>(); }
  });
}

private interface CollectionFactory<E, C extends Collection<E>> {
    C create();
}

private static <A, B, C extends Collection<B>> C map(
  Iterable<? extends A> xs, 
  Func1<? super A, ? extends B> transformer,
  CollectionFactory<B, C> factory
) {
  C ys = factory.create();
  for(A a : xs) {
    ys.add(transformer.apply(a));
  }
  return ys;
}

(Если вы можете мириться с бессмысленным многословием анонимных внутренних классов.)

Если бы не Collection, вам нужно было бы вставить какой-нибудь (некрасивый) адаптер.

Для полноты (хотя и не проверенного, можно сделать с несколькими настройками), неприятное решение с использованием наследования:

Set<String> strs = hashSets().map(things, formatter);

...

public static <E> Functions<E, Set<E>> hashSets() {
    return new Functions<E, Set<E>>() {
        protected Set<E> createCollections() {
            return new HashSet<E>();
        }
    };
}

public abstract class Functions<E, C extends Collection<E>> {
    protected abstract C createCollection();

    public <S> C map(
      Set<? extends S> xs, 
      Func1<? super S, ? extends E> transformer
    ) {
      C ys = createCollection();
      for(S a : xs) {
        ys.add(transformer.apply(a));
      }
      return ys;
    }

    public <S> C filter(
      List<? extends S> xs, 
      Func1<? super S, Boolean> predicate // Predicate<? super S> might be nicer!!
    ) {
      C ys = createCollection();
      for(A a : xs) {
        if(predicate.apply(a)) {
          ys.add(a);
        }
      }
      return ys;
    }
}
4 голосов
/ 15 сентября 2010

У Java нет полиморфизма высшего порядка (он же более высокого вида), поэтому это невозможно в системе типов.Многие Java-программисты прибегают к XML и / или рефлексии (т.е. избегают системы типов) для устранения этого недостатка.

Scala может справиться с этим, и то, что вы описываете, называется ковариантным функтором.Этот довольно фундаментальный тип данных (наряду со многими другими) был реализован в библиотеке Scalaz и включает в себя реализации для java.util. *.

Кроме того, есть еще много ковариантных функторов, которые не являются коллекциями, и много других функторов.которые не являются ковариантными.

Вы можете использовать Google для «20 промежуточных упражнений Scala», если хотите продолжить изучение этой конкретной концепции.

4 голосов
/ 15 сентября 2010

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

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

Два снимка экрана из вышеупомянутой статьи:


alt text


alt text

2 голосов
/ 15 сентября 2010

Я не верю, что система типов Java достаточно сложна, чтобы справиться с этим, но Scala есть. В версии 2.8 библиотеки коллекций они создали систему для автоматического создания коллекции соответствующего типа на основе коллекции, с которой вы работаете. Таким образом, если вы позвоните filter на List, он вернет новый List. Позвоните filter на Set, и вы получите Set обратно. Он делает это, хотя пока имеет только одну реализацию filter.

Чтобы узнать больше, взгляните на Traversable и материал, который его использует. Я верю, что CanBuildFrom - это место, где происходит много магии.

1 голос
/ 14 сентября 2010

Фактически список - это просто монада для типа T, позволяющая хранить несколько экземпляров типа. Вот почему здесь применяются все обычные законы монад, поэтому вы можете реализовать все операции, используя элементы bind и return.

Извините, у меня пока нет времени объяснять дальше, но в пространстве .NET у нас есть SelectMany и Enumerable.Repeat (1, element) для тех же целей. Об этом доступно много информации.

Любой оператор (например, filter в вашем примере) может быть реализован с использованием SelectMay соответственно bind.

...