Javaでリストの折り畳みを実装する方法
https://stackoverflow.com/questions/950751
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
リストがあり、それを単一の値に減らしたい（関数型プログラミング用語「フォールド」、Ruby 用語） inject）、 のように
Arrays.asList("a", "b", "c") ... fold ... "a,b,c"
私は関数型プログラミング (Scala) のアイデアに感染しているため、それをコーディングするより簡単で短い方法を探しています。
sb = new StringBuilder
for ... {
append ...
}
sb.toString
解決
探しているのは文字列です join() Java 8.0以降に搭載されたメソッド。以下のいずれかの方法を試してください。
静的メソッド
String#join(delimiter, elements):Collection<String> source = Arrays.asList("a", "b", "c"); String result = String.join(",", source);ストリーム インターフェイスは、Scala と非常によく似たフォールド操作をサポートします。
foldLeft関数。次の連結を見てください。 コレクタ: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(","));
他のヒント
あなたの元の質問に答えるために：
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(','));
を考える
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(); }
}
);
言語を切り替えることなく、いくつかの機能面をプレーンな古い Java に適用したい場合 できても ラムダJ, フォークジョイン (166y) そして グーグルコレクション は、構文糖衣を追加するのに役立つライブラリです。
の助けを借りて グーグルコレクション を使用できます ジョイナークラス:
Joiner.on(",").join("a", "b", "c")
Joiner.on(",") は不変オブジェクトなので、(たとえば定数として) 自由に共有できます。
次のように null 処理を設定することもできます Joiner.on(", ").useForNull("nil"); または Joiner.on(", ").skipNulls().
大きな文字列の生成中に大きな文字列が割り当てられるのを避けるために、それを使用して既存の Streams、StringBuilders などに追加できます。を通って Appendable インターフェイスまたは StringBuilder クラス：
Joiner.on(",").appendTo(someOutputStream, "a", "b", "c");
マップを書き出すときは、エントリとキーと値の間の区切りに 2 つの異なる区切り文字が必要です。
Joiner.on(", ").withKeyValueSeparator(":")
.join(ImmutableMap.of(
"today", "monday"
, "tomorrow", "tuesday"))
の編集の org.apache.commons.lang.StringUtils には（参加を含む）多くの有用な文字列関数を持っているようだ。
まず、一般的なファンクタや折り目などの機能的な予測を提供する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の実際の実装だ、配列は、反復処理可能
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;
}
（ルビーなど）injectIntoを有するのGSコレクション、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コレクションの開発者です。
。残念ながら、Java は関数型プログラミング言語ではないため、必要なことを実行するための適切な方法がありません。
Apache Commons libには 結合という関数 それはあなたが望むことを行うでしょう。
メソッド内のループを非表示にするのに十分な機能が必要です。
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();
}
再帰的に実行できると思います。
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);
}
これは、Java 8でString.join()を使用することができます。
List strings = Arrays.asList("a", "b", "c");
String joined = String.join(",", strings);
System.out.println(joined);
私たちは、次のコードで行うことができますラムダの支援を受けてます：
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()));
}
以下のコードは、我々が前進するとしましょう背後にあるノードの情報をバック維持して折り曲げることにより、リストを折り畳むことです。
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;
}
}
}
Javaの8スタイル（機能）：
// 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
はそのような機能はありませんが、あなたは次のようなものを作成し、あなたがする必要があるとき、それを呼び出すことができます。
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();
}
}
