How to implement a list fold in Java

Question

I have a List and want to reduce it to a single value (functional programming term "fold", Ruby term inject), like

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

As I am infected with functional programming ideas (Scala), I am looking for an easier/shorter way to code it than

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

Answer 1

What you are looking for is a string join() method which Java has since 8.0. Try one of the methods below.

1. Static method String#join(delimiter, elements):

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

2. Stream interface supports a fold operation very similar to Scala’s foldLeft function. Take a look at the following concatenating Collector:

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

   You may want to statically import Collectors.joining to make your code clearer.

   By the way this collector can be applied to collections of any particular objects:

   Collection<Integer> numbers = Arrays.asList(1, 2, 3);
   String result = numbers.stream()
           .map(Object::toString)
           .collect(Collectors.joining(","));
   

Answer 2

To answer your original question:

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; }

Where F looks like this:

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

As dfa suggested, Functional Java has this implemented, and more.

Example 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(",")));

Example 2:

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

Example 3:

import static fj.data.Stream.fromString;
import static fj.data.Stream.asString;
...
String abc = asString(fromString("abc").intersperse(','));

Answer 3

Given

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();
}

Then usage just looks like

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(); }
}
);

Answer 4

If you want to apply some functional aspects to plain old Java, without switching language although you could LamdaJ, fork-join (166y) and google-collections are libraries that help you to add that syntactic sugar.

With the help of google-collections you can use the Joiner class:

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

Joiner.on(",") is an immutable object so you might share it freely (for example as a constant).

You can also configure null handling like Joiner.on(", ").useForNull("nil"); or Joiner.on(", ").skipNulls().

To avoid allocating big strings while you are generating a large string, you can use it to append to existing Streams, StringBuilders, etc. through the Appendable interface or StringBuilder class:

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

When writing out maps, you need two different separators for entries and seperation between key+value:

Joiner.on(", ").withKeyValueSeparator(":")
            .join(ImmutableMap.of(
            "today", "monday"
            , "tomorrow", "tuesday"))

Answer 5

What you are looking for is a string "join" function which, unfortunately, Java does not have. You will have to roll your own join function which shouldn't be too hard.

Edit: org.apache.commons.lang.StringUtils seems to have many useful string functions (including join).

Answer 6

unfortunately in Java you can't escape that loop, there are several libraries however. E.g. you can try several libraries:

• lambdaj
• functionaljava
• specifically in your case you can reuse this code of mine

Answer 7

First you'll need a functional library for Java which supplies generic functors and functional projections like fold. I've designed and implemented a powerful (by virtue) yet simple such library here: http://www.codeproject.com/KB/java/FunctionalJava.aspx (I found the other libraries mentioned overly complicated).

Then your solution would look like:

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"

Note that by applying fold, the only part that really needs to be thought out is the implementation for Func2.call, 3 lines of code which define an operator accepting the accumulator and an element and returning the accumulator (my implementation accounts for empty strings and nulls, if you remove that case then it's down to 2 lines of code).

And here's the actual implementation of Seq.foldl, Seq implements Iterable<E>:

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;
}

Answer 8

GS Collections has injectInto (like Ruby), makeString and appendString. The following will work with your example:

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);

Note: I am a developer on GS Collections.

Answer 9

Unfortunately Java is not a functional programming language and does not have a good way to do what you want.

I believe the Apache Commons lib has a function called join that will do what you want though.

It will have to be good enough to hide the loop in a method.

public static String combine(List<String> list, String separator){
    StringBuilder ret = new StringBuilder();
    for(int i = 0; i < list.size(); i++){
        ret.append(list.get(i));
        if(i != list.size() - 1)
            ret.append(separator);
    }
    return ret.toString();
}

I suppose you could do it recursively:

public static String combine(List<String> list, String separator){
    return recursiveCombine("", list, 0, separator);
}

public static String recursiveCombine(String firstPart, List<String> list, int posInList, String separator){
    if (posInList == list.size() - 1) return firstPart + list.get(posInList);

    return recursiveCombine(firstPart + list.get(posInList) + separator, list, posInList + 1, seperator);
}

Answer 10

Now you can use String.join() with Java 8.

    List strings = Arrays.asList("a", "b", "c");
    String joined = String.join(",", strings);
    System.out.println(joined);

Answer 11

With the support of lambdas we could do with the following code:

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()));                  
    }

Answer 12

Below is the code to fold the list, by keeping back the information of the nodes let behind and folding as we move forward.

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;
        }

    }
}

Answer 13

Java 8 style (functional):

// Given
List<String> arr = Arrays.asList("a", "b", "c");
String first = arr.get(0);

arr = arr.subList(1, arr.size());
String folded = arr.stream()
            .reduce(first, (a, b) -> a + "," + b);

System.out.println(folded); //a,b,c

Answer 14

There is no such a function, but you could create something like the following, and invoke it whenever you need to.

import java.util.Arrays;
import java.util.List;

public class FoldTest {
    public static void main( String [] args ) {
        List<String> list = Arrays.asList("a","b","c");
        String s = fold( list, ",");
        System.out.println( s );
    }
    private static String fold( List<String> l, String with  ) {
        StringBuilder sb = new StringBuilder();
        for( String s: l ) {
            sb.append( s ); 
            sb.append( with );
        }
        return sb.deleteCharAt(sb.length() -1 ).toString();

    }
}