# Zig-Zag Numbers

F - ジグザグ数 (Zig-Zag Numbers)

EQ * x = x
LT * x = LT
GT * x = GT

Haskell だと compare が Ordering を返す。

Prelude> compare 1 2
LT
Prelude> compare 2 2
EQ
Prelude> compare 3 2
GT
Prelude> :t compare
compare :: Ord a => a -> a -> Ordering
Prelude>

これは何者なのかというと、長さの等しい 2 つのリストを辞書順比較するときに自然に現れるものである。 比較する２つのリストを$x=[3,1,4,2,5,9,1], y=[3,1,4,1,5,9,2]$とする。各要素を比較すると $[\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}]$となる。これを$\mathtt{fold}$で畳み込むと何が起きるかというと、foldr なら、

\begin{align}
& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT}
\end{align}

https://beta.atcoder.jp/contests/joi2012yo/submissions/1893277