Java 再帰的ジェネリクス 

# 参考資料

## 先人の足跡

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

## 標準APIでの実装例

[この人](http://docs.oracle.com/javase/jp/7/api/java/lang/Enum.html)とか
[この人](https://docs.oracle.com/javase/8/docs/api/java/util/stream/BaseStream.html)がそうです。

**Enum**&lt;E extends **Enum**&lt;E&gt;&gt;
**BaseStream**&lt;T,S extends **BaseStream**&lt;T,S&gt;&gt;

* * *

# 使いみち

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

```java::RecursiveGenerics.java
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"));
    }
}
```

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

```java::OrdinalPOJO.java
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再利用してて動作していなかった）

```java::Binding.java
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);
  }
}
```

<table>
  <tr>
    <th>タイトルA</th><th>タイトルB</th><th colspan=3>タイトルC</th><th>タイトルD</th><th>タイトルD</th><th>タイトルD</th>
  </tr>  
  <tr><td>A1</td><td>B1</td><td>C1.1</td><td>C2.1</td><td>C3.1</td><td>D1.1</td><td>D2.1</td><td>D3.1</td></tr>
  <tr><td>A2</td><td>B2</td><td>C1.2</td><td>C2.2</td><td>C3.2</td><td>D1.2</td><td>D2.2</td><td>D3.2</td></tr>
  <tr><td>A3</td><td>B3</td><td>C1.3</td><td>C2.3</td><td>C3.3</td><td>D1.3</td><td>D2.3</td><td>D3.3</td></tr>
</table>

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

```java::App.java
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&lt;EnumMap&lt;T,Stream&lt;Cell&gt;&gt;を収集。

```
> 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 あまりに丈が長いので整理

```java::Root.java
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();
	}
}
```
```java::Leaf.java
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();
	}
}
```
```java::Resource.java
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->不動点 に訂正。

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

```java::Y.java
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](http://groups.csail.mit.edu/mac/projects/scheme/) のシンボル から F を (I O) にするだけでOK。~~

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

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

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

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

```hs::infinite.hs
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. ラムダ計算とは**等価だけど別物**の計算表現形式。
  - 実は[歴史](https://ja.wikipedia.org/wiki/コンビネータ論理)的にはラムダ計算よりも先に発見されている。
2. **変数が存在しない**のがポイント。

SKIコンビネータ計算では以下の三種のラムダ計算の[関数合成](http://docs.oracle.com/javase/jp/8/docs/api/java/util/function/Function.html#compose-java.util.function.Function-)によりありとあらゆる計算を表現する。

- $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 が発見した[命題論理と対応](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AA%E3%83%BC%EF%BC%9D%E3%83%8F%E3%83%AF%E3%83%BC%E3%83%89%E5%90%8C%E5%9E%8B%E5%AF%BE%E5%BF%9C)する [B,C,K,W システム](https://ja.wikipedia.org/wiki/B,C,K,W%E3%82%B7%E3%82%B9%E3%83%86%E3%83%A0)なんかもあります。

* * *

## 不動点コンビネータ

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

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

**型無しラムダ計算**の[不動点コンビネータ](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF)はアルゴリズムにより無限に生成できる。(帰納的加算集合)

### 言語実装

[Lazy-K](https://ja.wikipedia.org/wiki/Lazy_K) SKI
[Unlambda](https://ja.wikipedia.org/wiki/Unlambda) SK
[Iota and Jot](https://en.wikipedia.org/wiki/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)
```

* * *