Javaで無限リスト

Java Haskell

Haskell の勉強をしていたら iterate という関数を見つけて非常に興味がわきました。
iterate は「初期値」と「現在の値から次の値を算出する関数」の二引数を与えると無限リストを生成してくれる関数です。
線形合同法を用いた疑似乱数列なども簡単に作れてしまうようですね。

無限リストは遅延評価の言語ならではだよなー、Javaだと無理だよなーとかぼんやり考えていたんですが、もしかして hasNext() が常に true を返す Iterator って無限リストとして使えるのでは？と思いたったので書いてみました。

前提として以下のような interface が存在するとして、

public interface Function<ARG, RET> {
    RET call(ARG argument);
}

Haskell の iterate っぽいものが以下。

import java.util.Iterator;

public class InfinityIterator<T> implements Iterator<T> {

    private T current;
    private Function<? super T, ? extends T> calculator;
    
    public InfinityIterator(T init, Function<? super T, ? extends T> calculator) {
        this.current = init;
        this.calculator = calculator;
    }

    public boolean hasNext() {
        return true;
    }

    public T next() {
        T result = current;
        current = calculator.call(current);
        return result;
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }
    
}

クラス名はもう少し検討した方がいいかもしれません。

ついでに Haskell の take を行う Utility も作っておきます。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class InfinityUtil {
    private InfinityUtil() {}
    public static <T> List<T> take(int num, Iterator<? extends T> iterator) {
        List<T> result = new ArrayList<T>(num);
        for (int i=0; i<num && iterator.hasNext(); i++) {
            result.add(iterator.next());
        }
        return result;
    }
}

サンプルとして線形合同法の疑似乱数を作ってみましょう。

// 線形合同法
public class LinearCongruentialGenerators implements Function<Integer, Integer> {
    private int a;
    private int b;
    private int m;
    
    public LinearCongruentialGenerators(int a, int b, int m) {
        if (a > m || b > m || 0 > a || 0 > b) {
            throw new IllegalArgumentException();
        }
        this.a = a;
        this.b = b;
        this.m = m;
    }
    
    public Integer call(Integer argument) {
        return (a * argument + b) % m;
    }
    
}

// 動作サンプル
LinearCongruentialGenerators lcgs = new LinearCongruentialGenerators(13, 5, 24);
Iterator<Integer> random = new InfinityIterator<Integer>(8, lcgs);
System.out.println(InfinityUtil.take(10, random)); // [8, 13, 6, 11, 4, 9, 2, 7, 0, 5]

折角なので Haskell の cycle も作ってみました。

import java.util.Iterator;

public class CycleIterator<T> implements Iterator<T> {

    private Iterable<? extends T> base;
    private Iterator<? extends T> iterator;
    
    public CycleIterator(Iterable<? extends T> base) {
        this.base = base;
        iterator = base.iterator();
        if (!iterator.hasNext()) {
            throw new IllegalArgumentException("An empty list cannot be cycled.");
        }
    }
    
    public boolean hasNext() {
        return true;
    }

    public T next() {
        if (!iterator.hasNext()) {
            iterator = base.iterator();
        }
        return iterator.next();
    }

    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }
    
}

動作サンプル。

Iterator<Integer> cycle = new CycleIterator<Integer>(Arrays.asList(1, 2, 3, 4));
System.out.println(InfinityUtil.take(10, cycle)); // [1, 2, 3, 4, 1, 2, 3, 4, 1, 2]