LoginSignup
29
26

More than 5 years have passed since last update.

@goro-ikeda

Java 再帰的ジェネリクス

Last updated at Posted at 2016-07-05

参考資料

先人の足跡

http://blogs.wankuma.com/nagise/archive/2008/05/25/139308.aspx
http://d.hatena.ne.jp/Nagise/20101101/1288629634

標準APIでの実装例

この人とか
この人がそうです。

Enum<E extends Enum<E>>
BaseStream<T,S extends BaseStream<T,S>>

使いみち

継承関係にあるクラスでの自然なメソッドコールチェイン実装

class RecursiveGenerics {
    public static class Parent<T extends Parent> {
        @SuppressWarnings("unchecked")
        protected T self() {
            return (T) this;
        }
        private String value1;
        public T setValue1(String value) {
            value1 = value;
            return self();
        }
        @Override
        public String toString() {
            return getClass().getSimpleName() + "/" + value1;
        }
    }
    public static class Child<T extends Child> extends Parent<T> {
        private String value2;
        public T setValue2(String value) {
            value2 = value;
            return self();
        }
        @Override
        public String toString() {
            return super.toString() + "/" + value2;
        }
    }
    public static class GrandChild extends Child<GrandChild> {
        private String value3;
        public GrandChild setValue3(String value) {
            value3 = value;
            return self();
        }
        @Override
        public String toString() {
            return super.toString() + "/" + value3;
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println(
            new Parent<Parent>()
            .setValue1("value1"));
        System.out.println(
            new Child<Child>()
            .setValue1("value1")
            .setValue2("value2"));
        System.out.println(
            new GrandChild()
            .setValue1("value1")
            .setValue2("value2")
            .setValue3("value3"));
    }
}

再帰的ジェネリクスを使わない場合は呼び出し順に制限がかかってしまう。

class OrdinalPOJO {
    public static class Parent {
        private String value1;
        public Parent setValue1(String value) {
            value1 = value;
            return this;
        }
        @Override
        public String toString() {
            return getClass().getSimpleName() + "/" + value1;
        }
    }
    public static class Child extends Parent {
        private String value2;
        public Child setValue2(String value) {
            value2 = value;
            return this;
        }
        @Override
        public String toString() {
            return super.toString() + "/" + value2;
        }
    }
    public static class GrandChild extends Child {
        private String value3;
        public GrandChild setValue3(String value) {
            value3 = value;
            return this;
        }
        @Override
        public String toString() {
            return super.toString() + "/" + value3;
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println(
            new GrandChild()
            .setValue3("value3")
            .setValue2("value2")
            .setValue1("value1"));
    }
}

Sheet@AachePOIからEnumMap変換

2018/10/17 修正（どこかでStream再利用してて動作していなかった）

import java.util.*;
import java.util.function.*;
import java.util.stream.*;
import org.apache.poi.ss.util.*;
import org.apache.poi.ss.usermodel.*;

interface Binding<T extends Enum<T> & Binding<T>> extends Predicate<Cell> {
  interface Mapping<T extends Enum<T>> extends Supplier<T> {
    default <V> Function<EnumMap<T,V>,EnumMap<T,V>> apply(V value) {
      return map -> { map.put(get(), value); return map; };
    }
    static <T extends Enum<T>> Mapping<T> of(T value) {
      return () -> value;
    }
  }
  interface Transform<X,Y> extends Supplier<Function<X,Y>> {
    default <T extends Enum<T>> EnumMap<T,Y> apply(EnumMap<T,X> input) {
      return input.entrySet().stream()
        .map(elm -> Mapping.of(elm.getKey())
            .apply(get().apply(elm.getValue())))
        .reduce(x -> x, (f0,f1) -> f1.compose(f0))
        .apply(new EnumMap<T,Y>(classify(input)));
    }
    static <X,Y> Transform<X,Y> of(Function<X,Y> f) {
      return () -> f;
    }
  }
  interface Scanning extends Supplier<Row>, Predicate<Row> {
    default boolean test(Row input) {
      return input.getRowNum() > get().getRowNum();
    }
    default <T extends Enum<T> & Binding<T>>
      Stream<EnumMap<T,Stream<Cell>>> scanning(EnumMap<T,int[]> mapping) {
      return stream(get().getSheet()).filter(this)
        .map(Binding::columns).map(Transform::of).map(f -> f.apply(mapping));
    }
    default <T extends Enum<T> & Binding<T>> 
      Stream<Function<EnumMap<T,int[]>,EnumMap<T,int[]>>> mapping(T value) {
      return stream(get()).filter(value)
        .map(Binding::indices).reduce(IntStream::concat)
        .map(IntStream::distinct).map(IntStream::toArray)
        .map(Mapping.of(value)::apply).map(Stream::of).orElseGet(Stream::empty);
    }
    static Scanning of(Row input) {
      return () -> input;
    }
  }
  interface Grouping<T extends Enum<T> & Binding<T>>
    extends Supplier<EnumSet<T>>, Function<Scanning,Stream<EnumMap<T,Stream<Cell>>>> {
    @Override
    default Stream<EnumMap<T,Stream<Cell>>> apply(Scanning input) {
      return get().stream().flatMap(input::mapping)
        .reduce((f0,f1) -> f1.compose(f0))
        .map(f -> f.apply(new EnumMap<T,int[]>(classify(get()))))
        .filter(map -> map.keySet().containsAll(get()))
        .map(input::scanning).orElseGet(Stream::empty);
    }
    static <T extends Enum<T> & Binding<T>> Grouping<T> of(EnumSet<T> input) {
      return () -> input;
    }
  }
  static <T> Stream<T> stream(Iterable<T> s) {
    return StreamSupport.stream(s.spliterator(), false);
  }
  static Function<int[],Stream<Cell>> columns(Row input) {
    return indices -> IntStream.of(indices).mapToObj(input::getCell);
  }
  static IntStream indices(Cell input) {
    return input.getSheet().getMergedRegions().stream()
      .filter(range -> range.isInRange(input))
      .findFirst().map(range -> IntStream
          .rangeClosed(range.getFirstColumn(), range.getLastColumn()))
      .orElse(IntStream.of(input.getColumnIndex()));
  }
  static <T extends Enum<T>> Class<T> classify(EnumMap<T,?> input) {
    return classify(EnumSet.copyOf(input.keySet()));
  }
  static <T extends Enum<T>> Class<T> classify(EnumSet<T> input) {
    return classify(Stream.concat(input.stream(),
          EnumSet.complementOf(input).stream()));
  }
  static <T extends Enum<T>> Class<T> classify(Stream<T> input) {
    return input.map(Enum::getDeclaringClass).findFirst().get();
  }
  static <T extends Enum<T> & Binding<T>>
    Function<Sheet,Stream<EnumMap<T,Stream<Cell>>>> of(Class<T> bindings) {
    return of(EnumSet.allOf(bindings));
  }
  static <T extends Enum<T> & Binding<T>>
    Function<Sheet,Stream<EnumMap<T,Stream<Cell>>>> of(EnumSet<T> bindings) {
    return sheet -> stream(sheet).map(Scanning::of)
      .map(Grouping.of(bindings)).findFirst().orElseGet(Stream::empty);
  }
}
タイトルA タイトルB タイトルC タイトルD タイトルD タイトルD
A1 B1 C1.1 C2.1 C3.1 D1.1 D2.1 D3.1
A2 B2 C1.2 C2.2 C3.2 D1.2 D2.2 D3.2
A3 B3 C1.3 C2.3 C3.3 D1.3 D2.3 D3.3

enum Foo implements Binding<Foo> の各要素にヘッダ列判定boolean test(Cell input)を実装。

import java.nio.file.*;
import java.util.stream.*;
import java.util.function.*;
import org.apache.poi.ss.usermodel.*;
public class App {
    enum Foo implements Binding<Foo> {
      A(input -> input.startsWith("タイトルA")),
      B(input -> input.startsWith("タイトルB")),
      C(input -> input.startsWith("タイトルC")),
      D(input -> input.startsWith("タイトルD"));
      private final Predicate<String> p;
      private Foo(Predicate<String> p) {
        this.p = p;
      }
      public boolean test(Cell input) {
        return p.test(input.getStringCellValue());
      }
    }
    public static void main(String[] args) {
      try {
      Binding.of(Foo.class)
        .apply(WorkbookFactory
            .create(Files.newInputStream(Paths.get("test.xlsx"))).getSheet("Sheet1"))
        .peek(System.out::println)
        .forEach(map -> map.entrySet().stream()
            .map(entry -> 
              Stream.concat(
                Stream.of(entry.getKey().toString()),
                entry.getValue().map(Cell::getStringCellValue))
              .collect(Collectors.joining(",")))
            .forEach(System.out::println));
      } catch(Exception e) { e.printStackTrace(); }
    }
}

全ヘッダ列が検出された行以下の列からStream<EnumMap<T,Stream<Cell>>を収集。

> Task :run
{A=java.util.stream.IntPipeline$1@6e535154, B=java.util.stream.IntPipeline$1@15a34df2, C=java.util.stream.IntPipeline$1@5b38c1ec, D=java.util.stream.IntPipeline$1@338fc1d8}
A,A1
B,B1
C,C1.1,C2.1,C3.1
D,D1.1,D2.1,D3.1
{A=java.util.stream.IntPipeline$1@5c7933ad, B=java.util.stream.IntPipeline$1@57bc27f5, C=java.util.stream.IntPipeline$1@5fb759d6, D=java.util.stream.IntPipeline$1@4b8d604b}
A,A2
B,B2
C,C1.2,C2.2,C3.2
D,D1.2,D2.2,D3.2
{A=java.util.stream.IntPipeline$1@d554c5f, B=java.util.stream.IntPipeline$1@2dfaea86, C=java.util.stream.IntPipeline$1@15888343, D=java.util.stream.IntPipeline$1@33ecda92}
A,A3
B,B3
C,C1.3,C2.3,C3.3
D,D1.3,D2.3,D3.3

共用エンティティと共用JAX-RSリソース

2016/07/08 あまりに丈が長いので整理

import java.util.List;
import javax.persistence.*;
// サブクラスで @Entity & @XmlRootElement
@MappedSuperclass
public class Root<S extends Root<S, T>, T extends Leaf<S, T>> {
    @SuppressWarnings("unchecked")
    public S self() {
        return (S) this;
    }
    private long id;
    @Id
    @GeneratedValue
    public long getId() {
        return id;
    }
    public S setId(long value) {
        id = value;
        return self();
    }
    protected List<T> leaves;
    // サブクラスで @Override & @ManyToOne
    public List<T> getLeaves() {
        return leaves;
    }
    public S setLeaves(List<T> values) {
        for (T value : values) {
            value.setRoot(self());
        }
        leaves = values;
        return self();
    }
}

import javax.persistence.*;
//サブクラスで @Entity & @XmlRootElement
@MappedSuperclass
public class Leaf<S extends Root<S, T>, T extends Leaf<S, T>> {
    @SuppressWarnings("unchecked")
    public T self() {
        return (T) this;
    }
    private long id;
    @Id
    @GeneratedValue
    public long getId() {
        return id;
    }
    public T setId(long value) {
        id = value;
        return self();
    }
    protected S root;
    // サブクラスで @Override & @OneToMany
    @Transient
    public S getRoot() {
        return root;
    }
    public T setRoot(S value) {
        root = value;
        return self();
    }
}

import java.util.Optional;
import javax.enterprise.inject.Instance;
import javax.inject.Inject;
import javax.persistence.EntityManager;
import javax.validation.constraints.NotNull;
import javax.ws.rs.Consumes;
import javax.ws.rs.GET;
import javax.ws.rs.NotFoundException;
import javax.ws.rs.POST;
import javax.ws.rs.PUT;
import javax.ws.rs.Path;
import javax.ws.rs.PathParam;
import javax.ws.rs.Produces;
import javax.ws.rs.core.Context;
import javax.ws.rs.core.MediaType;
import javax.ws.rs.core.Response;
import javax.ws.rs.core.UriInfo;

public abstract class Resource<S extends Root<S, T>, T extends Leaf<S, T>> {

    protected abstract EntityManager getEntityManager();

    @Inject
    private Instance<Class<S>> rootClass;
    @Inject
    private Instance<Class<T>> leafClass;
    @PathParam("rootId")
    private long rootId;
    @Context
    private UriInfo uri;

    @PUT
    @Consumes({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    @Produces({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    public S put(S root) {
        getEntityManager().merge(root);
        return root;
    }

    @GET
    @Produces({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    public S get() {
        return Optional.of(getEntityManager()
                .find(rootClass.get(), rootId))
                .orElseThrow(() -> new NotFoundException());
    }

    @POST
    @Consumes({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    @Produces({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    public Response post(T leaf) {
        getEntityManager().persist(leaf.setRoot(get()));
        return Response.created(uri.getAbsolutePathBuilder()
                .path("{leafId}").build(leaf.getId())).entity(leaf).build();
    }

    @PUT
    @Path("{leafId}")
    @Consumes({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    @Produces({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    public T put(@NotNull @PathParam("leafId") long leafId, T leaf) {
        getEntityManager().merge(leaf.setRoot(get()));
        return leaf;
    }

    @GET
    @Path("{leafId}")
    @Produces({ MediaType.APPLICATION_JSON, MediaType.APPLICATION_XML })
    public T get(@NotNull @PathParam("leafId") long leafId) {
        return Optional.of(getEntityManager()
                .find(leafClass.get(), leafId))
                .orElseThrow(() -> new NotFoundException());
    }
}

不動点コンビネータ

2017/07/07 Z->不動点 に訂正。

意外とシンプルなものを見ない。

import java.util.function.Function;
import java.util.stream.Stream;

@FunctionalInterface
interface Y<I,O> extends Function<Y<I,O>, Function<I,O>> {
    public static <I,O> Function<I,O> of(Y<I,O> f) {
        return f.apply(f);
    }
    // 0..20番目までのフィボナッチ数を出力
    public static void main(String[] args) {
        Y.<Function<Integer, Integer>, Function<Integer, Stream<Integer>>>of(
            // 関数 g と 初期値 x を入力として
            // (x < 1) になるまでの g(x) の結果 Stream を返す再帰関数
            f -> g -> x -> (x < 1)
                ? Stream.of(g.apply(x))
                : Stream.concat(
                    Stream.of(g.apply(x)),
                    f.apply(f).apply(g).apply(x - 1)))
                    .apply(Y.of(
                        // x 番目のフィボナッチ数を返す再帰関数
                        f -> x -> x < 2 ? 1 
                        : f.apply(f).apply(x - 1)
                        + f.apply(f).apply(x - 2)
                    )).apply(20).forEach(System.out::println);
    }
}

Scheme のシンボル から F を (I O) にするだけでOK。

たぶん同型なんだけど名状し難い違和感がある。

型定義中の自己参照部分(Y<I,O>)からは次のような無限の展開が発生する。

Function<Function<Function<..., Function<I,O>>, Function<I,O>>, Function<I,O>>

Haskellで自己参照なしの不動点コンビネータを組もうとするとこの無限の展開のために型推論の段階で弾かれる。

fix f = f (fix f)

-- main = print $ show (fix (\f -> \i -> if i == 0 then 1 else i * f (i-1)) 5)

main = print $ show (
  (\f -> (\x -> f (x x))(\x -> f (x x)))
  (\f -> \i -> if i == 0 then 1 else i * f (i-1)) 5)

Occurs check: cannot construct the infinite type:

t0 ~ t0 -> a0 -> a0
Expected type: t0 -> a0 -> a0
Actual type: (t0 -> a0 -> a0) -> a0 -> a0

Javaでも似たようなコンパイルエラーを吐くコードが組めた気がするんだけど忘れた。

ここから蛇足。

そもそもコンビネータって何

  1. ラムダ計算とは等価だけど別物の計算表現形式。
    • 実は歴史的にはラムダ計算よりも先に発見されている。
  2. 変数が存在しないのがポイント。

SKIコンビネータ計算では以下の三種のラムダ計算の関数合成によりありとあらゆる計算を表現する。

  • $S = λxyz.xz(yz)$
    • 適用コンビネータ
  • $K = λxy.x$
    • 定数コンビネータ
  • $I = S K K = λx.x$
    • 恒等コンビネータ
  1. $(λxyz.xz(yz))(λxy.x)(λxy.x)$
  2. $(λz.(λxy.x)(z)((λxy.x)(z))$
    • $(λxy.x)(z)(any) = z$
  3. $λz.z$

単独でありとあらゆる計算を表現できる one-point bases というのも存在する。

  • $X = λx.((xS)K)$
  • $K = X(X (X X))$
  • $S = X(X (X (X X)))$

うわぁ。

他にも皆大好きな Haskell Curry が発見した命題論理と対応する B,C,K,W システムなんかもあります。

不動点コンビネータ

Yコンビネータは Haskell Curry が発見した不動点コンビネータの一種。

  • $Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))$

型無しラムダ計算の不動点コンビネータはアルゴリズムにより無限に生成できる。(帰納的加算集合)

言語実装

Lazy-K SKI
Unlambda SK
Iota and Jot X

リンク先にある傑作を Haskellで実装してたんですが残念ながら out of memory。

fix.hs
main = do
  print $ show ((不動点 階乗) 5)

凄いの a b c d e f g h i j k l m n o p q s t u v w x y z r =
  (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))

不動点 f = (
  凄いの 凄いの 凄いの 凄いの 凄いの
  凄いの 凄いの 凄いの 凄いの 凄いの
  凄いの 凄いの 凄いの 凄いの 凄いの
  凄いの 凄いの 凄いの 凄いの 凄いの
  凄いの 凄いの 凄いの 凄いの 凄いの 凄いの)

階乗 f 0 = 1
階乗 f x = x * f (x - 1)
29
26
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
29
26