第21章ハイロモルフィズムとネクサス（やさしい版） — 関数プログラミングによるアルゴリズム設計の真珠

この章のテーマは、「木を作って→たたむ」タイプの再帰計算を、もっと効率よく実行する方法です。

ざっくり全体像ふつうのハイロモルフィズムは「木を作って→即消す」ので、同じ部分問題を何度も解いてしまいます。
そこで 木をあえて残し、共有を保ったまま下から埋めていく と、動的計画法のように無駄が消え、速くなります。この「共有された木」がネクサスです。

fold、unfold、そしてハイロモルフィズム

使う道具：葉ラベル付きの木

抽象的に議論するとつらいので、ひとつだけ具体的な中間データ構造に絞ります。次のような、葉にだけ値を持つ木です。

data Tree a = Leaf a | Node [Tree a]

Dart sealed class Tree<A> {} class Leaf<A> extends Tree<A> { final A x; Leaf(this.x); } class Node<A> extends Tree<A> { final List<Tree<A>> ts; Node(this.ts); }

この木は次の同型（つまり型の見方の言い換え）にもとづいています。

fold :: (Either a [b] → b) → Tree a → b fold f t = case t of Leaf x → f (Left x) Node ts → f (Right (map (fold f) ts)) unfold :: (b → Either a [b]) → b → Tree a unfold g x = case g x of Left y → Leaf y Right xs → Node (map (unfold g) xs)

Dart // Either a [b] は sealed class で表現 sealed class Either<A, B> {} class Left<A, B> extends Either<A, B> { final A x; Left(this.x); } class Right<A, B> extends Either<A, B> { final B x; Right(this.x); } B foldE<A, B>(B Function(Either<A, List>) f, Tree<A> t) => switch (t) { Leaf(:final x) => f(Left(x)), Node(:final ts) => f(Right(ts.map((s) => foldE(f, s)).toList())), }; Tree<A> unfoldE<A, B>(Either<A, List> Function(B) g, B x) => switch (g(x)) { Left(x: final y) => Leaf(y), Right(x: final xs) => Node(xs.map((s) => unfoldE(g, s)).toList()), };

合成して「森林伐採」する

hylo f g = fold f · unfold g と定めて、中間の木を作らずに一気に計算するように書き換えると（これが森林伐採）、次が得られます。

hylo f g x = case g x of Left y → f (Left y) Right xs → f (Right (map (hylo f g) xs))

Dart B hyloE<A, B, X>( B Function(Either<A, List>) f, Either<A, List<X>> Function(X) g, X x, ) => switch (g(x)) { Left(x: final y) => f(Left(y)), Right(x: final xs) => f(Right(xs.map((s) => hyloE(f, g, s)).toList())), };

もっと見やすい形へ整理する

Either があると見通しが悪いので、成分に分解して書き直します。fold は次のように 2 つの関数 f、g の組で表せます。

fold :: (a → b) → ([b] → b) → Tree a → b fold f g (Leaf x) = f x fold f g (Node ts) = g (map (fold f g) ts)

Dart B fold<A, B>(B Function(A) f, B Function(List) g, Tree<A> t) => switch (t) { Leaf(:final x) => f(x), Node(:final ts) => g(ts.map((s) => fold(f, g, s)).toList()), };

unfold は 3 つの関数（判定 p、葉の値 v、部分問題 h）で書けます。

unfold :: (b → Bool) → (b → a) → (b → [b]) → b → Tree a unfold p v h x = if p x then Leaf (v x) else Node (map (unfold p v h) (h x))

Dart Tree<A> unfold<A, B>( bool Function(B) p, A Function(B) v, List Function(B) h, B x, ) => p(x) ? Leaf(v(x)) : Node(h(x).map((y) => unfold(p, v, h, y)).toList());

hylo x = if p x then f (v x) else g (map hylo (h x))

Dart // f, v, g, p, h をクロージャで受け取る中間版 B hyloMid<A, B, X>( B Function(A) f, A Function(X) v, B Function(List) g, bool Function(X) p, List<X> Function(X) h, X x, ) => p(x) ? f(v(x)) : g(h(x).map((y) => hyloMid(f, v, g, p, h, y)).toList());

よく見ると v は f に吸収できて要らないので、消しましょう。すると次の 一般形 が出てきます。

hylo x = if p x then f x else g (map hylo (h x))(21.1)

Dart // (21.1) v を f に吸収した一般形 B hylo<A, B>( B Function(A) f, B Function(List) g, bool Function(A) p, List<A> Function(A) h, A x, ) => p(x) ? f(x) : g(h(x).map((y) => hylo(f, g, p, h, y)).toList());

反対のアイデア：ラベル付き木を残す（annotation）

森林伐採が「木を消す」方向なら、逆に 計算し終わった値を木のノードにラベルとして残す という方向もあります。そのためにラベル付き木を用意します。

data LTree a = LLeaf a | LNode a [LTree a]

Dart sealed class LTree<A> {} class LLeaf<A> extends LTree<A> { final A x; LLeaf(this.x); } class LNode<A> extends LTree<A> { final A x; final List<LTree<A>> ts; LNode(this.x, this.ts); }

次に、木をたどりつつ各ノードに fold の結果をラベル付けする関数 fill を定義します。

fill :: (a → b) → ([b] → b) → Tree a → LTree b fill f g = fold (lleaf f) (lnode g) lleaf f x = LLeaf (f x) lnode g ts = LNode (g (map label ts)) ts label (LLeaf x) = x label (LNode x ts) = x

Dart B label(LTree t) => switch (t) { LLeaf(:final x) => x, LNode(:final x) => x, }; LTree lleaf<A, B>(B Function(A) f, A x) => LLeaf(f(x)); LTree lnode(B Function(List) g, List<LTree> ts) => LNode(g(ts.map(label).toList()), ts); LTree fill<A, B>(B Function(A) f, B Function(List) g, Tree<A> t) => fold<A, LTree>((x) => lleaf(f, x), (ts) => lnode(g, ts), t);

fill は、もとの木と同じ形のラベル付き木を作り、各ラベルには「そのノードから下の部分木を fold した値」を入れます。したがって根のラベルが答えになります。

hylo = label · fill f g · unfold p id h

Dart // unfold で木を作り、fill でラベル付け、label で根を取り出す B hyloViaFill<A, B>( B Function(A) f, B Function(List) g, bool Function(A) p, List<A> Function(A) h, A x, ) => label(fill(f, g, unfold<A, A>(p, (a) => a, h, x)));

これから扱う形の限定

以降の例では、x は非空リスト、p は「単元リストか？」の判定に固定します。すると全部が次の形になります。

hylo :: ([a] → b) → ([b] → b) → ([a] → [[a]]) → [a] → b hylo f g h = fold f g · mkTree h mkTree h = unfold single id h

Dart // リスト特化版：単元リストが基本ケース bool single<A>(List<A> xs) => xs.length == 1; Tree<List<A>> mkTree<A>(List<List<A>> Function(List<A>) h, List<A> xs) => unfold<List<A>, List<A>>(single, (a) => a, h, xs); B hyloList<A, B>( B Function(List<A>) f, B Function(List) g, List<List<A>> Function(List<A>) h, List<A> xs, ) => fold<List<A>, B>(f, g, mkTree(h, xs));

ここで h は、長さ 2 以上のリストを受け取り、非空リストのリストを返す関数です。

三つの例

例1：h = split（真ん中で二分割）

split xs = [take n xs, drop n xs] where n = length xs div 2

Dart List<List<A>> split<A>(List<A> xs) { final n = xs.length ~/ 2; return [xs.sublist(0, n), xs.sublist(n)]; }

長さが 2 の冪のリストなら、mkTree split xs は葉が単元リストの完全二分木になります。共有は起きないので、ネクサスにもなりません。

例2：h = isegs（両端を 1 つずつ削って 2 本にする）

isegs xs = [init xs, tail xs]

Dart // 両端を1つずつ削って2本にする List<List<A>> isegs<A>(List<A> xs) => [xs.sublist(0, xs.length - 1), xs.sublist(1)];

例：isegs "abcde" = ["abcd", "bcde"]。名前の由来は「直近の区分（immediate segments）」を返すこと。

ここでは葉は単元リストになりますが、部分木を共有できるのがポイントです。abcd と bcde はどちらも bcd を含みますよね。だから真のネクサスが得られます（図21.1）。

recover :: [[a]] → [a] recover xss = head (head xss) : last xss

Dart List<A> recover<A>(List<List<A>> xss) => [xss.first.first, ...xss.last];

例3：h = minors（要素を 1 つだけ落とす）

minors [x, y] = [[x], [y]] minors (x : xs) = map (x :) (minors xs) ++ [xs]

Dart // 要素を1つだけ落とした部分列すべて List<List<A>> minors<A>(List<A> xs) { if (xs.length == 2) return [[xs[0]], [xs[1]]]; final x = xs.first; final rest = xs.sublist(1); return [ ...minors(rest).map((ys) => [x, ...ys]), rest, ]; }

長さ n の入力に対する木のサイズ S(n) は、S(0) = 0、S(n+1) = 1 + (n+1)S(n) を満たします。解くと

一方、ネクサスにすると 2ⁿ − 1 ノードまで縮みます（図21.2）。階乗から指数への激減です。

ネクサスの構築

基本方針：層ごとに下から積む

これまでの例では、ネクサスの葉はぜんぶ同じ深さにあります。そこで、下の層から上の層へ一段ずつ組み立てる戦略が自然です。層が 1 個だけになったら完成、というイメージです。

各層は「ラベル付き木のリスト」だと決めつけず、いったん抽象型 Layer a にしておきます。すると全体の骨格は次のようにまとまります。

mkNexus f g = label · extractL · until singleL (stepL g) · initialL f initialL :: ([a] → b) → [a] → Layer (LTree b) stepL :: ([b] → b) → Layer (LTree b) → Layer (LTree b) singleL :: Layer (LTree b) → Bool extractL :: Layer (LTree b) → LTree b

Dart // Layer<A> は各実装ごとに具体型が異なる（typedef で切り替える） // mkNexus の骨格：層を積み上げ、singleL になるまで stepL を繰り返す B mkNexus<A, B, L>( B Function(List<A>) f, B Function(List) g, L Function(List<A>) initialL, L Function(L) stepL, bool Function(L) singleL, LTree Function(L) extractL, List<A> xs, ) { var layer = initialL(xs); while (!singleL(layer)) { layer = stepL(layer); } return label(extractL(layer)); }

この 4 つの関数を、h = split、isegs、minors それぞれについて実装するのが目標です。

split と isegs：層はただのリストでよい

initialL f = map (lleaf f · wrap) singleL = single extractL = head

Dart // split / isegs 用：Layer = List<LTree> List<LTree> initialLFlat<A, B>(B Function(List<A>) f, List<A> xs) => xs.map((x) => lleaf<List<A>, B>(f, [x])).toList(); bool singleLFlat(List<LTree> ts) => ts.length == 1; LTree extractLFlat(List<LTree> ts) => ts.first;

ここで wrap x = [x]。h = split のときの stepL は、リストを 2 個ずつまとめる group を使って、

stepL g = map (lnode g) · group group [ ] = [ ] group (x : y : xs) = [x, y] : group xs

Dart // split 用：2つずつまとめる List<List<A>> groupSplit<A>(List<A> xs) { final out = <List<A>>[]; for (var i = 0; i + 1 < xs.length; i += 2) { out.add([xs[i], xs[i + 1]]); } return out; } List<LTree> stepLSplit( B Function(List) g, List<LTree> ts, ) => groupSplit(ts).map((pair) => lnode(g, pair)).toList();

これで、たとえば mkNexus id merge xs は「ペアで併合 → 4 つずつ併合 → …」というボトムアップ版のマージソートになります。

group [x] = [ ] group (x : y : xs) = [x, y] : group (y : xs)

Dart // isegs 用：隣接ペアを取り出す（要素は共有される） List<List<A>> groupIsegs<A>(List<A> xs) { final out = <List<A>>[]; for (var i = 0; i + 1 < xs.length; i++) { out.add([xs[i], xs[i + 1]]); } return out; } List<LTree> stepLIsegs( B Function(List) g, List<LTree> ts, ) => groupIsegs(ts).map((pair) => lnode(g, pair)).toList();

minors の場合はかなり手ごわい

木を組み合わせて次の層を作る方法を、まず葉のリスト（最下層）で観察します。5 枚の葉 a、b、c、d、e のペアリングは、こう並べます（丸括弧はグルーピングを表すだけの情報）。

(ab ac ad ae) (bc bd be) (cd ce) (de)

この形（丸括弧を無視）が、次の group で得られる第二層です。

group [x] = [ ] group (x : xs) = map (bind x) xs ++ group xs where bind x y = [x, y]

Dart // 第二層（ペア）を生成する group List<List<A>> groupPairs<A>(List<A> xs) { if (xs.length <= 1) return []; final x = xs.first; final rest = xs.sublist(1); return [ ...rest.map((y) => [x, y]), ...groupPairs(rest), ]; }

第三層（三つ組）へ進むには、第二層の丸括弧のグルーピング構造を利用します。

((abc abd abe) (acd ace) (ade)) ((bcd bce) (bde)) ((cde))

(((abcd abce) (abde)) ((acde))) (((bcde)))

initialL f = map (Leaf · lleaf f · wrap) singleL = single extractL = extract · head where extract (Leaf x) = x extract (Node [t]) = extract t stepL g = map (mapTree (lnode g)) · group group :: [Tree a] → [Tree [a]] group [t] = [ ] group (Leaf x : vs) = Node [Leaf [x, y] | Leaf y ← vs] : group vs group (Node us : vs) = Node (zipWith combine (group us) vs) : group vs combine (Leaf xs) (Leaf x) = Leaf (xs ++ [x]) combine (Node us) (Node vs) = Node (zipWith combine us vs)

Dart // minors 用：Layer = List<Tree<LTree>> // 各要素は「森」を成し、木のノードにはラベル付き木がぶら下がる // Tree の中の各要素に関数を適用 Tree mapTree<A, B>(B Function(A) f, Tree<A> t) => switch (t) { Leaf(:final x) => Leaf(f(x)), Node(:final ts) => Node(ts.map((s) => mapTree(f, s)).toList()), }; List<Tree<LTree>> initialLMinors<A, B>( B Function(List<A>) f, List<A> xs, ) => xs.map((x) => Leaf<LTree>(lleaf<List<A>, B>(f, [x]))).toList(); bool singleLMinors(List<Tree<LTree>> ts) => ts.length == 1; LTree _extract(Tree<LTree> t) => switch (t) { Leaf(:final x) => x, Node(:final ts) when ts.length == 1 => _extract(ts.first), _ => throw StateError('extract: unexpected shape'), }; LTree extractLMinors(List<Tree<LTree>> ts) => _extract(ts.first); // combine: 左に「要素列」、右に「同じ形の木」を追加 Tree<List<A>> combine<A>(Tree<List<A>> l, Tree<A> r) => switch ((l, r)) { (Leaf(x: final xs), Leaf(x: final x)) => Leaf([...xs, x]), (Node(ts: final us), Node(ts: final vs)) => Node([ for (var i = 0; i < us.length && i < vs.length; i++) combine(us[i], vs[i]) ]), _ => throw StateError('combine: shape mismatch'), }; List<Tree<List<A>>> groupMinors<A>(List<Tree<A>> ts) { if (ts.length <= 1) return []; final head = ts.first; final vs = ts.sublist(1); return switch (head) { Leaf(x: final x) => [ Node<List<A>>([ for (final v in vs) if (v is Leaf<A>) Leaf<List<A>>([x, v.x]) ]), ...groupMinors(vs), ], Node(ts: final us) => [ Node<List<A>>([ for (var i = 0; i < groupMinors(us).length && i < vs.length; i++) combine(groupMinors(us)[i], vs[i]) ]), ...groupMinors(vs), ], }; } List<Tree<LTree>> stepLMinors( B Function(List) g, List<Tree<LTree>> layer, ) => groupMinors(layer) .map((t) => mapTree<List<LTree>, LTree>( (ts) => lnode(g, ts), t)) .toList();

これで次の等式が成り立つはずですが、証明は長いのでここでは省略します。

mkNexus f g = fill f g · mkTree minors

Dart // mkTree minors を fill にかけると、mkNexus と同じ結果を（素朴に）得る LTree mkNexusNaive<A, B>( B Function(List<A>) f, B Function(List) g, List<A> xs, ) { final tree = mkTree<A>(minors<A>, xs); return fill<List<A>, B>(f, g, tree); }

なぜネクサスを構築するのか

実は消しても解ける

「そもそもラベルだけ持っていれば、ネクサスは要らないのでは？」——もっともです。実際、h = isegs の場合は次のように書けます。

solve :: ([a] → b) → ([b] → b) → [a] → b solve f g = head · until single (map g · group) · map (f · wrap)

Dart // isegs 用：ラベルだけ持って、下から一段ずつ潰していく B solveIsegs<A, B>( B Function(List<A>) f, B Function(List) g, List<A> xs, ) { var layer = xs.map((x) => f([x])).toList(); while (layer.length > 1) { layer = groupIsegs(layer).map(g).toList(); } return layer.first; }

solve f g = extractL · until singleL (step g) · map (Leaf · f · wrap) step g = map (mapTree g) · group

Dart // minors 用：森を保ちつつラベルだけ持って潰す B _extractPlain(Tree t) => switch (t) { Leaf(:final x) => x, Node(:final ts) when ts.length == 1 => _extractPlain(ts.first), _ => throw StateError('extract: unexpected shape'), }; B solveMinors<A, B>( B Function(List<A>) f, B Function(List) g, List<A> xs, ) { var layer = xs.map((x) => Leaf(f([x]))).cast<Tree>().toList(); while (layer.length > 1) { layer = groupMinors(layer) .map((t) => mapTree<List, B>(g, t)) .toList(); } return _extractPlain(layer.first); }

変種問題ではネクサスが本領を発揮する

答えは、同じ形のネクサスを流用して、変種の問題を解きたいときにネクサスが真価を発揮する、というものです。

変種1：最適括弧付け（optimal bracketing）

式 x₁ ⊕ x₂ ⊕ ⋯ ⊕ x_n を、コストが最小になるように括弧付けする問題です。⊕ は結合的（順序を変えても値は同じ）だが、括弧の入れ方でコストが違います。

この場合、部分問題の分け方は isegs ではなく uncats になります。

uncats [x, y] = [([x], [y])] uncats (x : xs) = ([x], xs) : map (cons x) (uncats xs) where cons x (ys, zs) = (x : ys, zs)

Dart // リストを空でない2本に分ける全通り（先頭の切れ目のみ） List<(List<A>, List<A>)> uncats<A>(List<A> xs) { if (xs.length == 2) return [([xs[0]], [xs[1]])]; final x = xs.first; final rest = xs.sublist(1); return [ ([x], rest), ...uncats(rest).map((p) => ([x, ...p.$1], p.$2)), ]; }

例：uncats "abcde" は次のとおり（先頭の切れ目を全通り列挙）。

[("a", "bcde"), ("ab", "cde"), ("abc", "de"), ("abcd", "e")]

uncats を使うともう Tree a の木にはなりませんが、isegs のネクサスを流用すれば解けます。ポイントは、賢い構成子 lnode の定義だけを差し替えることです。

lnode g [u, v] = LNode (g (zip (lspine u) (rspine v))) [u, v] lspine (LLeaf x) = [x] lspine (LNode x [u, v]) = lspine u ++ [x] rspine (LLeaf x) = [x] rspine (LNode x [u, v]) = [x] ++ rspine r

Dart // 最適括弧付け用：左スパイン・右スパインを zip して uncats を復元 List<A> lspine<A>(LTree<A> t) => switch (t) { LLeaf(:final x) => [x], LNode(:final x, :final ts) => [...lspine(ts[0]), x], }; List<A> rspine<A>(LTree<A> t) => switch (t) { LLeaf(:final x) => [x], LNode(:final x, :final ts) => [x, ...rspine(ts[1])], }; LTree lnodeBracket( B Function(List<(B, B)>) g, List<LTree> uv, ) { final u = uv[0], v = uv[1]; final ls = lspine(u); final rs = rspine(v); final zipped = [ for (var i = 0; i < ls.length && i < rs.length; i++) (ls[i], rs[i]) ]; return LNode(g(zipped), [u, v]); }

直感：左スパインと右スパインを zip すると uncats が復元できるのです。lspine はそのままだと二乗時間ですが、累積パラメータで線形にできます。

変種2：Countdown（前章の例）

部分列を扱う代表例。前章で使った関数は次の unmerges です。

unmerges [x, y] = [([x], [y])] unmerges (x : xs) = [([x], xs)] ++ concatMap (add x) (unmerges xs) where add x (ys, zs) = [(x : ys, zs), (ys, x : zs)]

Dart // 各部分列とその補集合のペアを列挙 List<(List<A>, List<A>)> unmerges<A>(List<A> xs) { if (xs.length == 2) return [([xs[0]], [xs[1]])]; final x = xs.first; final rest = xs.sublist(1); return [ ([x], rest), ...unmerges(rest).expand((p) => [ ([x, ...p.$1], p.$2), (p.$1, [x, ...p.$2]), ]), ]; }

例：unmerges "abcd" は次のとおり（各部分列とその補集合のペア）。

[("a", "bcd"), ("ab", "cd"), ("b", "acd"), ("abc", "d"), ("bc", "ad"), ("ac", "bd"), ("c", "abd")]

ペアの順や中身の順はどちらでもよく、大事なのは各部分列がその補集合とペアになることです。ここでも minors のネクサスを流用し、lnode を差し替えれば解けます。

「ラベル全部を取り出す」ための工夫

差し替えの中心は、ノードに対応するネクサスのラベル群から unmerges を復元することです。原理的には 幅優先走査で全ラベルを列挙できます。たとえば図21.2 の abcd のネクサスを幅優先走査して先頭を除くと、

abc, abd, acd, bcd, ab, ac, bc, ad, bd, cd, a, b, c, d

これを半分に分けて、前半と（逆順の）後半を zip すると、順は違うけれど unmerges "abcd" が再現できます。

traverse :: [LTree a] → [a] traverse [ ] = [ ] traverse ts = map label ts ++ traverse (concatMap subtrees ts) subtrees (LLeaf x) = [ ] subtrees (LNode x ts) = ts

Dart List<LTree<A>> subtrees<A>(LTree<A> t) => switch (t) { LLeaf() => [], LNode(:final ts) => ts, }; // 幅優先でラベルを列挙 List<A> traverseBF<A>(List<LTree<A>> ts) { final out = <A>[]; var layer = ts; while (layer.isNotEmpty) { out.addAll(layer.map(label)); layer = layer.expand(subtrees).toList(); } return out; }

二項木状のスパニング木を作る

図21.3 のスパニング木は階数 4 の二項木です。階数 n の二項木は、子として階数 n−1、n−2、…、0 の二項木を順に持つ木のこと。ネクサスに使った森の木の親戚のような存在です。

ネクサスから二項木状のスパニング木を得るには、子を順に落としていく剪定を行います。ざっくり手順:

forest k (LLeaf x : ts) = LLeaf x : ts forest k (LNode x us : vs) = LNode x (forest k (drop k us)) : forest (k + 1) vs

lnode g ts = LNode (g (zip xs (reverse ys))) ts where (xs, ys) = halve (traverse (forest 0 ts)) halve xs = splitAt (length xs div 2) xs

Dart // 動作確認: minors の列挙 void main() { final xs = [1, 2, 3, 4]; final ms = minors(xs); print('minors($xs):'); for (final m in ms) { print(' $m'); } // 期待: // [2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3] // // ネクサス構築（mkNexus / mkNexusNaive）は上で定義した通り、 // minors の各層を共有した木として保持する。差し替え関数 lnode を通せば // 各層の結果を計算できる（本章の例では [x1, ..., xn] から Countdown 風の // 探索や部分列の合計などに応用できる）。 }

おわりに

「ハイロモルフィズム」という名前は Meijer (1992) が初めて使ったもの（Meijer et al. 1991 も参照）。この章の内容は主に 2 つの資料から来ています。

まとめ

ハイロモルフィズム＝「unfold して fold」の再帰計算。素朴には (21.1) の一行で書ける。
ただし部分問題が重なる場合、素朴版は同じ計算を何度もしてしまう。
そこで中間の木を残し、共有された木＝ネクサスを下から埋める（mkNexus）。
ネクサスを保っておくと、lnode を差し替えるだけで、最適括弧付けや Countdown のような 変種の問題にも流用できる。

参考文献

Bird, R. S. and Hinze, R. (2003). Trouble shared is trouble halved. ACM SIGPLAN Haskell Workshop, Uppsala, Sweden.

Bird, R. S. (2008). Zippy tabulations of recursive functions. In LNCS 5133: Proceedings of the Ninth International Conference on the Mathematics of Program Construction, ed. P. Audebaud and C. Paulin-Mohring. pp. 92–109.

Meijer, E. (1992). Calculating compilers. PhD thesis, Nijmegen University, The Netherlands.

Meijer, E., Fokkinga, M. and Paterson, R. (1991). Functional programming with bananas, lenses, envelopes and barbed wire. Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture. New York, NY: Springer-Verlag, pp. 124–44.

ハイロモルフィズムとネクサス

どんな話？