loop/recurで相互再帰(Clojure)

 Clojureのtrampolineを使った相互再帰の例として, even/odd関数が有りますが, しかし,  簡単な相互再帰なら, trampolineよりloop-recur内に自分でディスパッチさせる処理を書いたほうがわかりやすいような気がします.

 例えば, even/oddならこんな感じ.

(defn even-odd? [even-or-odd n]
  (loop [status even-or-odd n n]
    (cond
     (= status :even)
     (if (= n 0)
       true
       (recur :odd (dec n)))
     (= status :odd)
     (if (= n 0)
       false
       (recur :even (dec n))))))

こう書いておいて,

user> (even-odd? :odd 9)

と呼び出すとか. cond節が冗長になりますが, declare, defnと書いて, 無名関数で囲って, trampolineで待ち受けさせるのと大差ないかなと....思ったのですが, 比べてみると, やっぱり読みにくい. trampoline版のほうがシンプルですね.

(declare my-odd?)

(defn my-even? [n]
  (if (= n 0)
    true
    #(my-odd? (dec n))))

(defn my-odd? [n]
  (if (= n 0)
    false
    #(my-even? (dec n))))

適当に測ってみると少し早くなった程度.

user> (time (trampoline my-even? 10000000))
"Elapsed time: 2127.23756 msecs"
true
user> (time (even-odd? :even 10000000))
"Elapsed time: 1781.678006 msecs"
true

しかし, 相互再帰を書く時の選択肢としてはありかなと思ったりしてます.

dorothy(Graphviz)で木構造(構文解析木)を可視化

 dorothyは, GraphvizのClojure向けのラッパーです. シーケンスによる(Graphvizの)DOT言語を用いて, グラフ構造を記述すると, そこから, そのグラフを可視化します.
 dorothyの基本的な使い方については, dorothyのREADMEか, 以下のページの説明が詳しいです.

dorothyの魔法でクラス図を描く - Qiita

 木構造もグラフの一種なので, パーサ(opennlp)によって生成された構文解析木を表示させてみることにします. Clojureのopennlpについては, 前にも触れましたが, 今回は, これにdorothyを合わせて使ってみます. 長文を構文解析し, dorothyで可視化すると, 以下のようになります.

 opennlpからdorothyへの変換は, 基本的に, 木構造のリンク関係を[src dst]のリストへ変換すればOKで, 書いてみると, こんな感じになります.

(require '[dorothy.core :refer :all];; [dorothy "0.0.6"]
         '[opennlp.treebank :refer :all]) ;; [clojure-opennlp "0.3.2"]

(def treebank-parser
  (make-treebank-parser "en-parser-chunking.bin"))

(defn gensym- [tag]
  (keyword (gensym (str (name tag) "-"))))

(defn ungensym- [tag]
  (first (clojure.string/split (name tag) #"-")))

(defn tree->links [tree]
  (if (string? tree)
    [(gensym- tree)]
    (let [{tag :tag chunk :chunk} tree
          children (map tree->links chunk)
          top (keyword (gensym- tag))]
      (concat [top]
              (map (fn [x] [top (first x)]) children)
              (apply concat (map rest children))))))

(defn treeviz [en-text]
  (letfn [(remove-sym [node]
            (subgraph [[:node {:label (ungensym- node)}] node]))]
    (let [link-pairs
          (->> (treebank-parser [en-text]) first make-tree tree->links)
          subnodes
          (->> link-pairs flatten distinct (map remove-sym))
          params
          [(graph-attrs {:size "5, 5"}) (node-attrs {:fontsize 10})]]
      (->> link-pairs (concat params subnodes) digraph dot show!))))

 Graphviz側では, 親ノードから, 子ノードへのリンクの表現のリストで, 木構造を表すわけですが, ノードを表す識別子(POS(品詞)や名詞)が重複する可能性があるのでgensymなどを使ってノードのアイデンティティを確立します. 再帰的にリンクを表すペアのリストを作って上に投げるという処理を繰り返すだけで生成できるdorothyの記法は, かなりお手軽です.
 dorothyには, 以下のような[srs dst]で表されるペアのリストを渡します.

([:TOP-2782 :S-2783] [:S-2783 :NP-2784] [:S-2783 :VP-2791] [:S-2783 :.-2801] [:NP-2784 :DT-2785] [:NP-2784 :NN-2787] [:NP-2784 :NN-2789] [:DT-2785 :This-2786] [:NN-2787 :parse-2788] [:NN-2789 :tree-2790] [:VP-2791 :VBZ-2792] [:VP-2791 :NP-2794] [:VBZ-2792 :visualizes-2793] [:NP-2794 :DT-2795] [:NP-2794 :NN-2797] [:NP-2794 :NN-2799] [:DT-2795 :a-2796] [:NN-2797 :parse-2798] [:NN-2799 :tree-2800] [:.-2801 :.-2802])

 これだけでも, 木構造は可視化できますが, これだと, シノニム部分がくっついて見づらいため, 各ノードのラベルは数値の部分を抜いた名前で表すことにします. 各ノードにラベル(ノードとして表示される名前)をつけるには, subgraphを使います. その他, 表示用のオプションがいくつか設定できますが, 今回は, フォントサイズと, 表示される画像のサイズを設定しました.

user> (treeviz "This tree visualizes a parse tree .")

こんな感じで実行するとして,

 上図の木構造が出てきます. 自然変換言語処理の教科書に乗ってそうな図ですね.
 TOPの下のSは, Statement(文)のSです. SubjectのSではないです. 主語は, NPで表されている左側の部分木です.

 ちなみに, 要素の順番は重要で, 上記の例だと, 綺麗に元の文の単語列が左から順に表示されていますが, リストの順序が異なれば, 可視化の結果も異なり, 木構造としては成立していても変な形で表示されたりもします.

関手, 自然変換とHaskell

$\require{AMScd}$ 最近, Mathjaxで遊んでいるので, それを使って, 関手と自然変換について調べたことのメモ.

関手とHaskellのFunctor

 関手$F$は圏$X$から$Y$へ対応を表し, 圏$X$の各関数$f : A \rightarrow B$を $F(f) : F(A) \rightarrow F(B)$ として移すものです. 関手は元の圏の関数について合成則を保存し, $f : A \rightarrow B, g : B \rightarrow C$,を関手$F$によって移すと, $F(f) \circ F(g) = F(f \circ g)$という性質を持ちます. また, 元の圏の各対象Xについて, 移した先の関手$F(id_X)$の射もその先の対象の$id$射となります.

 Haskellにおける関手$F$は, 名前も性質もmap関数に似ています.

class Functor a where
  mapf : (a -> b) -> f a -> f b

 mapfの実装として, リスト上のmap関数を考えると, 関手の合成則の保存が成立し, (map f) . (map g) = map (f . g)という規則が成立するはずですが, これは, プログラムの融合変換では一般にmap分配則と呼ばれるもので, 一般に成立します.

 つまり, ある型からなる圏〜リストへの関手とは, ただのリストのmap関数だということになります. 上記の定義では, 対象についての対応関係を考えていないように見えますが, 射$F(f)$が定義されれば, 自動的に対象同士の対応関係も定義されるということでしょう. というわけで, 任意の型Aのリスト/Map関数は, AからAのリストへの関手だということになります(太字部分, 2016/05/02追記修正).

 一般にmap関数は, リストだけのものでなく, 木構造へ応用できます. 例えば, 2分木について, 木構造の各要素に関数fを適用するmap関数は容易に想像できます.

data BTree a = Leaf a | Fork (BTree a) (BTree a) deriving Show

を考えることにして,

instance Functor BTree where
  fmap f (Leaf a) = Leaf (f a)
  fmap f (Fork a b) = Fork (fmap f a) (fmap f b)

 タプルのリストで, 二番目の要素のみへの関数適用を考えるなら,

data TList a b = Nil | Cons a b (TList a b)

instance Functor (TList a) where
  fmap f Nil = Nil
  fmap f (Cons a b rest) = Cons a (f b) (fmap f rest)

とすれば, Functorのインスタンスとして具体的な関数が実装でき, 関手が定義できる流れになります. 代数的データ型なら, (fmap f) $= F(f)$の対応について, 自由に考えることが可能です. 関手というと身構えてしまいますが, 関数型言語上では, 単なる高階関数として表されることがわかります.

自然変換とHaskell上の関数

 関手$F, G$における自然変換$\mu$は, 関手$F, G : X \rightarrow Y$について, $\mu \circ F(f) = G(f) \circ \mu$を成り立たせるもの. というわけで, 可換図式を考えると,
$$\begin{CD} F(A) @>{F(f)}>> F(B)\\ @V{\mu_A}VV @V{\mu_B}VV \\ G(A) @>{G(f)}>> G(B) \end{CD}$$
 となります(上図 : 2016/05/18修正). 前述の条件を満たしていることがわかります. 自然変換の概念は, 2つの関手$F, G : X \rightarrow Y$の移した先の対応$\mu : F \dot{\rightarrow} G$を定義するものですが, $\mu \circ F(f)$のルートと, $G(f) \circ \mu$のルートの結果(計算)を同一にするものと考えると, わかりやすいですね. ちなみに, 上記の可換図式の個々の$\mu_A , \mu_B$は, 別の射(関数)である場合もあり, 個々の射は, 自然変換のコンポーネントと呼ばれるそうです.

 問題は, この自然変換を表すプログラム上の関数とは何かということです. 調べたら, 以下に例がありました.

 Category theory/Natural transformation - Haskell Wiki

 前述のデータ型BTreeとリスト([])で書くとすれば, 自然変換 $\mu :$ (BTree a) $\rightarrow$ [a]の自然変換とは, 例えば,

flatten2List :: (BTree a) -> [a]
flatten2List (Leaf a) = [a]
flatten2List (Fork a b) = (flatten2List a) ++ (flatten2List b)

 になりそうです.
 可換図式の主張する合成規則$\mu \circ F(f) = G(f) \circ \mu$は,

((flatten2List . fmap f) = (map f . flatten2List)

 が成立するはず. あまりにシンプルですね. ただのキャストに相当する(?)何かになりました.

 さらに自然変換$\mu$には, 別の自然変換$\eta$との垂直合成$\eta \circ \mu$を考えることも可能です. 前述の可換図式に下にもうひとつ自然変換をくっつけた形で, 以下のようになります.
$$\begin{CD} F(A) @>{F(f)}>> F(B)\\ @V{\mu_A}VV @V{\mu_B}VV \\ G(A) @>{G(f)}>> G(B) \\ @V{\eta_A}VV @V{\eta_B}VV \\ H(A) @>{H(f)}>> H(B) \end{CD}$$

 関手fmapの実装として, Maybeについて考えると,

data Maybe x = Nothing | Just x deriving Show

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

と定義することができて, この時の自然変換$\eta :$[a]$\rightarrow$ (Maybe a)を考えれば,

list2Maybe :: [a] -> (Maybe a)
list2Maybe [] = Nothing
list2Maybe (x:xs) = (Just x)

となると思います. この時の, $\eta \circ \mu$による自然変換の垂直合成は,

(list2Maybe . flatten2List)

となり, 可換図式を満たすなら,

((list2Maybe . flatten2List . fmap f)
= (list2Maybe . map f . flatten2List)

= (fmap f . list2Maybe . flatten2List)

となるはずです.

参考文献

• ループ書いたら負けかなと思っている : https://www.yumpu.com/ro/document/view/11416939/-/37
• S. マクレーン, 圏論の基礎, 三好 博之 (翻訳), 高木 理 (翻訳),  丸善