Как реализовать сложение списка в Java - PullRequest
Новая
       38

Как реализовать сложение списка в Java

22 голосов
/ 04 июня 2009

У меня есть список, и я хочу уменьшить его до одного значения (термин функционального программирования «сложить», термин Ruby inject), например 

Arrays.asList("a", "b", "c") ... fold ... "a,b,c"

Поскольку я заражен идеями функционального программирования (Scala), я ищу более простой / короткий способ его кодирования, чем 

sb = new StringBuilder
for ... {
  append ...
}
sb.toString

Ответы [ 14 ]

13 голосов
/ 04 июня 2009

Чтобы ответить на ваш оригинальный вопрос: 

public static <A, B> A fold(F<A, F<B, A>> f, A z, Iterable<B> xs)
{ A p = z;
  for (B x : xs)
    p = f.f(p).f(x);
  return p; }

Где F выглядит так: 

public interface F<A, B> { public B f(A a); }

Как предположил dfa, Функциональная Java это реализовала и многое другое.

Пример 1: 

import fj.F;
import static fj.data.List.list;
import static fj.pre.Monoid.stringMonoid;
import static fj.Function.flip;
import static fj.Function.compose;

F<String, F<String, String>> sum = stringMonoid.sum();
String abc = list("a", "b", "c").foldLeft1(compose(sum, flip(sum).f(",")));

Пример 2: 

import static fj.data.List.list;
import static fj.pre.Monoid.stringMonoid;
...
String abc = stringMonoid.join(list("a", "b", "c"), ",");

Пример 3: 

import static fj.data.Stream.fromString;
import static fj.data.Stream.asString;
...
String abc = asString(fromString("abc").intersperse(','));
10 голосов
/ 04 июня 2009

Дано 

public static <T,Y> Y fold(Collection<? extends T> list, Injector<T,Y> filter){
  for (T item : list){
    filter.accept(item);
  }
  return filter.getResult();
}

public interface Injector<T,Y>{
  public void accept(T item);
  public Y getResult();
}

Тогда использование выглядит как 

fold(myArray, new Injector<String,String>(){
  private StringBuilder sb = new StringBuilder();
  public void Accept(String item){ sb.append(item); }
  public String getResult() { return sb.toString(); }
}
);
8 голосов
/ 09 июня 2009

Если вы хотите применить некоторые функциональные аспекты к простой старой Java, без переключения языка , хотя вы можете LamdaJ , fork-join (166y ) и google-collection - это библиотеки, которые помогут вам добавить этот синтаксический сахар.

С помощью google-collection вы можете использовать класс столярных изделий : 

Joiner.on(",").join("a", "b", "c")

Joiner.on(",") является неизменным объектом, поэтому вы можете свободно делиться им (например, как константа).

Вы также можете настроить обработку нуля, например Joiner.on(", ").useForNull("nil"); или Joiner.on(", ").skipNulls().

Чтобы избежать выделения больших строк при генерации большой строки, вы можете использовать ее для добавления к существующим потокам, StringBuilders и т. Д. Через интерфейс Appendable или StringBuilder класс: 

Joiner.on(",").appendTo(someOutputStream, "a", "b", "c");

При написании карт вам нужны два разных разделителя для записей и разделения между ключом + значением: 

Joiner.on(", ").withKeyValueSeparator(":")
            .join(ImmutableMap.of(
            "today", "monday"
            , "tomorrow", "tuesday"))
6 голосов
/ 04 июня 2009

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

Редактировать: org.apache.commons.lang.StringUtils , кажется, имеет много полезных строковых функций (включая объединение).

5 голосов
/ 17 марта 2015

То, что вы ищете, это строковый join() метод, который есть в Java с 8.0. Попробуйте один из способов ниже.

  1. Статический метод String#join(delimiter, elements): 

    Collection<String> source = Arrays.asList("a", "b", "c");
String result = String.join(",", source);

  2. Интерфейс Stream поддерживает операцию сгиба, очень похожую на функцию foldLeft в Scala Взгляните на следующее объединение Collector : 

    Collection<String> source = Arrays.asList("a", "b", "c");
String result = source.stream().collect(Collectors.joining(","));

    Возможно, вы захотите статически импортировать Collectors.joining, чтобы сделать ваш код более понятным.

    Кстати, этот коллектор можно применять к коллекциям любых конкретных объектов: 

    Collection<Integer> numbers = Arrays.asList(1, 2, 3);
String result = numbers.stream()
        .map(Object::toString)
        .collect(Collectors.joining(","));
2 голосов
/ 08 января 2013

GS Collections имеет injectInto (как Ruby), makeString и appendString. Следующее будет работать с вашим примером: 

String result1 = FastList.newListWith("a", "b", "c").makeString(",");
StringBuilder sb = new StringBuilder();
FastList.newListWith("a", "b", "c").appendString(sb, ",");
String result2 = sb.toString();
Assert.assertEquals("a,b,c", result1); 
Assert.assertEquals(result1, result2);

Примечание: я разработчик коллекций GS.

2 голосов
/ 21 мая 2010

Сначала вам понадобится функциональная библиотека для Java, которая снабжает универсальные функторы и функциональные проекции, такие как сложение. Я спроектировал и реализовал мощную (в силу этого) простую, но такую ​​библиотеку: http://www.codeproject.com/KB/java/FunctionalJava.aspx (другие библиотеки, упомянутые выше, оказались слишком сложными).

Тогда ваше решение будет выглядеть так: 

Seq.of("","a",null,"b","",null,"c","").foldl(
    new StringBuilder(), //seed accumulator
    new Func2<StringBuilder,String,StringBuilder>(){
        public StringBuilder call(StringBuilder acc,String elmt) {
            if(acc.length() == 0) return acc.append(elmt); //do not prepend "," to beginning
            else if(elmt == null || elmt.equals("")) return acc; //skip empty elements
            else return acc.append(",").append(elmt);
        }
    }
).toString(); //"a,b,c"

Обратите внимание, что при применении сгиба единственной частью, которая действительно должна быть продумана, является реализация Func2.call, 3 строки кода, которые определяют оператора, принимающего аккумулятор и элемент и возвращающего аккумулятор (моя реализация учитывает пустые строки и нули, если вы удалите этот регистр, то это будет до 2 строк кода).

А вот фактическая реализация Seq.foldl, Seq реализует Iterable : 

public <R> R foldl(R seed, final Func2<? super R,? super E,? extends R> binop)
{
    if(binop == null)
        throw new NullPointerException("binop is null");

    if(this == EMPTY)
        return seed;

    for(E item : this)
        seed = binop.call(seed, item);

    return seed;
}
2 голосов
/ 04 июня 2009

к сожалению, в Java вы не можете избежать этого цикла, однако есть несколько библиотек. Например. Вы можете попробовать несколько библиотек:

1 голос
/ 10 сентября 2016

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

public class FoldList {
    public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        Node h = new Node(8);
        Node i = new Node(9);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        e.next = f;
        f.next = g;
        g.next = h;
        h.next = i;

        foldLinkedList(a);

    }

    private static void foldLinkedList(Node a) {
        Node middle = getMiddleNodeOfTheList(a);
        reverseListOnWards(middle);
        foldTheList(a, middle);

    }

    private static Node foldTheList(Node a, Node middle) {
        Node leftBackTracePtr = a;
        Node leftForwardptr = null;
        Node rightBackTrack = middle;
        Node rightForwardptr = null;
        Node leftCurrent = a;
        Node rightCurrent = middle.next;
        while (middle.next != null) {
            leftForwardptr = leftCurrent.next;
            rightForwardptr = rightCurrent.next;
            leftBackTracePtr.next = rightCurrent;
            rightCurrent.next = leftForwardptr;
            rightBackTrack.next = rightForwardptr;
            leftCurrent = leftForwardptr;
            leftBackTracePtr = leftCurrent;
            rightCurrent = middle.next;
        }
        leftForwardptr = leftForwardptr.next;
        leftBackTracePtr.next = middle;
        middle.next = leftForwardptr;

        return a;

    }

    private static void reverseListOnWards(Node node) {
        Node startNode = node.next;
        Node current = node.next;
        node.next = null;
        Node previous = null;
        Node next = node;
        while (current != null) {
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        node.next = previous;

    }

    static Node getMiddleNodeOfTheList(Node a) {
        Node slowptr = a;
        Node fastPtr = a;
        while (fastPtr != null) {
            slowptr = slowptr.next;
            fastPtr = fastPtr.next;
            if (fastPtr != null) {
                fastPtr = fastPtr.next;
            }
        }
        return slowptr;

    }

    static class Node {
        public Node next;
        public int value;

        public Node(int value) {
            this.value = value;
        }

    }
}
1 голос
/ 17 ноября 2015

С поддержкой lambdas мы можем сделать следующий код: 

static <T, R> R foldL(BiFunction<R, T, R> lambda, R zero, List<T> theList){

     if(theList.size() == 0){
      return zero;
     }

     R nextZero = lambda.apply(zero,theList.get(0));

     return foldL(lambda, nextZero, theList.subList(1, theList.size()));                  
    }
Страница:
...