実装時の型と評価後の型

.groovy

前回の木構造と同じようにリストを表現するとどうなるのか?

def tree = { [:].withDefault{ owner.call() } }
def list = { h, t -> [h, { t?.call() }] }

ちょっと意味が違う気がするけど気持ちの問題の範囲なので続ける。
h は先頭の要素で、t は評価すると残りのリストを返し、list は遅延評価されるリストになる。

def ones = list(1){ list(1){ owner.call() } }
assert 1 == ones[0]
assert 1 == ones[1]()[0]
assert 1 == ones[1]()[1]()[0]
assert 1 == ones[1]()[1]()[1]()[0]
assert 1 == ones[1]()[1]()[1]()[1]()[0]

今回は使う側で{ owner.call() }する。
この例は3回が適切だが中毒性があるので5回書いてしまった。
なので毒を抜く。

def lazySeq(head, generateTail) {
  def seq = [:]
  seq.head = { head }
  seq.tail = { generateTail?.call() }
  return seq
}

コンストラクタとファクトリメソッドの違いはあるが http://groovy.codehaus.org/Functional+Programming+with+Groovy の LazyList の形になった。

あなたは何型ですか？

def twos = lazySeq(2){ lazySeq(2){ owner.call() } }
assert 2 == twos.head()
assert 2 == twos.tail().head()
assert 2 == twos.tail().tail().head()

assert 2 == [2,2,2].head()
assert 2 == [2,2,2].tail().head()
assert 2 == [2,2,2].tail().tail().head()

動的言語では常に型を知る必要はないが、失礼のないように頭の中では知っておくのがマナー。
twos はリストのように扱えるので List にしてしまっていいのだろうか？
head と tail の Pair なのだろうか？

is-implemented-in-terms-of 関係

今回調べてみて知ったのだが親子関係を考えるときに is-a, has-a 以外にも実装としての継承を表わす関係があるようだ。
ただし、Java では実装としての継承を使うと隠す方法がないので通常は has-a の関係で表わす。
実装の関係を表に出して問題となっているのが Groovy の Range である。
Range は List を継承してしまった。
おそらく Iterable の意味で使ったのだろうが Range が実装されたときには Iterable が存在しなかったのだ。


twos で考える。
無限に続くので Iterable として扱ってよいだろう。
だが twos が Pair で Pair が Iterable を継承していたら、2つしかないはずが終わらなくて目撃者は通報するだろう。
Pair を継承したときには Pair は Iterable を継承していなかったというアリバイがあったらどうだろうか？

Pair であることは内緒にして Iterable にする

def lazySeq(head, generateTail) {
  return new Iterable() {
    def head() { head }
    def tail() { generateTail?.call() }
    @Override Iterator iterator() {
      def curr  = this
      def value = []
      return new Iterator() {
        @Override boolean hasNext() {
          if (value.empty && curr) {
            value.add(curr.head())
            curr = curr.tail()
          }
          return !value.empty
        }
        @Override def next() {
          value.remove(0)
        }
        @Override void remove() {
          throw new UnsupportedOperationException()
        }
      }
    }
  }
}

def integers(n) {
  return lazySeq(n){ integers(n+1) }
}

def ints = integers(1)
assert 1 == ints.head()
assert 2 == ints.tail().head()
assert 3 == ints.tail().tail().head()

assert [1,2,3] == integers(1).iterator().take(3).collect()

まとめて数えられるようになった。

評価後の型

ここでもう一つの疑問が
integers(1) は List なのだろうか？
List なら比較できるべきなのだろうか？

// == になるようにしますか？
assert integers(1) != integers(1)
assert integers(1).iterator() != integers(1).iterator()

ちなみに Haskell ではリストは比較できなければならないので実行してくれるが結果は返さない。

[1..] == [1..]
-- Interrupted.

ここで静的な型と実行時の型があるように実は評価後の型と評価前の型があるということにようやく気がついた。
Haskell の型に書かれているのは評価後の型だ。
[1..] 自体は何者かわからない評価されるとリストになる何かだが遅延評価の言語では区別する必要がない。
Groovy は遅延評価の言語ではないので実装すると評価前の型も表にでてきてしまう。
integers(1) は評価すると List をくれる何かであって List でもないし比較もできない。

ファクトリメソッド

最初の tree や list は携帯型のファクトリメソッドともいえる。
クロージャのおかげでファクトリメソッド自体も動けるようになったみたいだ。
そして遅延評価で再帰している。
Groovy 1.8.7 では List#withDefault のようなファクトリメソッドも追加される。
しかし DefaultGroovyMethods にばかり機能が追加されるようになってしまったので実装としての型がないものには機能が追加されない。
実装の型のオブジェクトからではなく評価されたときの型などに静的なファクトリメソッドが追加されるようになればいいのにと思った。
いまさら Range を Iterable にすることができないのなら Iterable.range も存在すればいいだけだから。