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

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 2

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 3

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 recusriveCombine("", 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 4

Given

public static <T,Y> Y fold(Collection<? super 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 5

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 6

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

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

    }
}