Haskell - $の仕組みを覗いてみよう

この記事は、[Haskell (その3) Advent Calendar 2017](https://qiita.com/advent-calendar/2017/haskell3)の８日目の記事です。

Haskellのコードでよく登場する`$`がどのような原理で働くのかを解説します。

#カッコの略記で大活躍の`$`
Haskellでプログラムを組んでいると、カッコをネストする場面によく出くわします。

例えば、1〜10のうち、偶数のもののみの２乗の和（つまり、$2^2+4^2+6^2+8^2+10^2$ )を求めるプログラムを考えてみます。

```Haskell
main = print ( sum ( map (^2) ( filter even [1..10] ) ) )
```

おびただしい数のカッコですね…！ちょっとごちゃごちゃして読みにくい感じです。

ここで、我らが`$`が登場します。
[Haskell超入門](https://qiita.com/7shi/items/145f1234f8ec2af923ef)では、「`$`から行末までを括弧で囲むのと同じ効果があります」とありますので、その通りに書き換えてみます。

```Haskell
main = print $ sum $ map (^2) $ filter even [1..10]
```
カッコが減って見やすくなりましたね。

このように、読みやすいコードを書くには欠かせない`$`です。
ところで、一体どのような仕組みで`$`がカッコを省略するように働くのか、疑問に思ったことはありませんか？

ここでは、その仕組みを解き明かしてみましょう。

##`$`の定義を見てみよう
実は、他の多くの演算子と同じく`$`も関数です。従って、どこかに`($)`の定義があるはずです。

まずは、`($)`が定義されているモジュールを調べるために、GHCiを使ってみましょう。

```
$ ghci
Configuring GHCi with the following packages: 
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> :i ($)
($) ::
  forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
  (a -> b) -> a -> b
  	-- Defined in ‘GHC.Base’
infixr 0 $
Prelude>
```

GHCiによれば、`Defined in ‘GHC.Base’`だそうですから、GHC.Baseモジュールを覗いてみます。

[ghc/Base.hs at master - ghc/ghc](https://github.com/ghc/ghc/blob/master/libraries/base/GHC/Base.hs)

執筆時点では、1282行目からの部分に定義があります。

```haskell:Base.hs
($)                     :: (a -> b) -> a -> b
f $ x                   =  f x
```
まず、型を見ると、「(a -> b)型の関数」と「a型の値」を受取って、「b型の値」を返す関数、となっています。
さらに、定義を見ると、`f $ x = f x`となっています。

つまり、関数とその引数を受け取っていますが、引数をそのまま受け取った関数に垂れ流しているように見えます。

こんなに単純でいいのでしょうか？具体例でちょっと考えてみましょう。

```haskell
main = print $ sum [1..10]
```
先ほどの定義に従えば、このコードの`$`演算子を適用すると

```haskell
main = print sum [1..10]
```

となる、ということになります。やはり、おかしい感じです。
これでは`$`があっても無くても何も変わらないような気がしてしまいます。

`$`の挙動を知るには、定義を見るだけでは不十分のようです。

##決め手は優先順位
先ほどのコードの解釈に足りなかった概念、それはズバリ「**優先順位**」です。
Haskellの演算子には適用の優先順位が存在します。

以下がHaskellの演算子の優先順位を示す表です。
※[演算子 - ウォークスルーHaskell](http://walk.northcol.org/haskell/operators)の表をお借りしました。

|優先順位|演算子|
|---|---|
|(10)|その他のすべての関数適用|
|9|`!!` `.`|
|8|`^` `^^` `**`|
|7|`*` `/` \`div\` \`mod\` \`rem\` \`quot\`|
|6|`+` `-`|
|5|`:` `++`|
|4|`==` `/=` `>=` \`elem\` \`notElem\`|
|3|`&&`|
|2| ‖|
|1|`>>` `>>=`|
|0|`$` `$!` \`seq\`|

ご覧の通り、`$`演算子は優先順位が最も低く設定されています。
これが、`$`の挙動を知る鍵です。


##関数適用を手作業で追ってみよう

では、先ほどのコードをもう一度見てみましょう。

```haskell
main = print $ sum [1..10]
```
まずは、優先順位に従ってカッコをつけます。
「`$`の適用」の優先順位はあらゆるものより低いので、

```haskell
main = (print) $ (sum [1..10])
```

となります。優先順位の働きによって、暗黙のうちにカッコがつけられていたのですね！

あとは、`(print)`関数に`(sum [1..10])`が渡されて、計算結果が出力される、という感じです。


##複数の`$`がある時の挙動

`$`が複数あるときも同じようにして挙動を把握できるでしょうか。
最初の例を持ってきてみます。

```haskell
main = print $ sum $ map (^2) $ filter even [1..10]
```
`$`の優先順位が一番低いことを利用して、カッコをつけてみます。

```haskell
main (print) $ (sum) $ (map (^2)) $ (filter even [1..10] )
```
少し違和感がありますね。`$`を使わないコードでは

```Haskell
main = print ( sum ( map (^2) ( filter even [1..10] ) ) )
```
となっていたはずです。カッコが入れ子になってくれていないようです。
一体どういうことでしょうか。

##`$`の最後の性質：結合性

実は、ここにはもう一つ欠けている概念があります。
それは、演算子の「**結合性**」です。

これは、複数の演算子が連なったときの、演算子の適用順を決める概念です。

簡単な例で考えてみましょう。

```haskell
a = 1 + 2 + 3 + 4
```
このような式があったとき、どういう順番で計算していくでしょうか？

Haskellでは、このような計算の順番を決定していく方法が２つあります。
一つは「**左結合**」と呼ばれる方法で、左側の演算子から適用していきます。つまり、

```haskell
a = 1 + 2 + 3 + 4
a =     3 + 3 + 4
a =         6 + 4
a =            10
--つまり、
a = ((1 + 2) + 3) + 4
```
とするやり方です。
もう一つは「**右結合**」で、さっきとは逆に右側から計算していきます。

```haskell
a = 1 + 2 + 3 + 4
a = 1 + 2 + 7
a = 1 + 9
a = 10
--つまり、
a = 1 + (2 + (3 + 4))
```

ちなみに、`$`演算子は**右結合**となっています。

##結合性を使ってもう一度

さて、結合性を使ってもう一度先ほどの式を解釈してみましょう。

```haskell
main = print $ sum $ map (^2) $ filter even [1..10]
```
`$`の優先順位が一番低いことを利用して、カッコをつけてみます。

```haskell
main (print) $ (sum) $ (map (^2)) $ (filter even [1..10] )
```

さらに、`$`は右結合でしたから、右側の`$`から適用されるようにカッコを付けてみます。

```haskell
main (print) $ ( (sum) $ ( (map (^2)) $ (filter even [1..10] ) ) )
```

ちゃんとカッコがネストされましたね！
あとは`$`を適用すれば、

```haskell
main (print) ( (sum) ( (map (^2)) (filter even [1..10] ) ) )
```
となって、ちゃんと`$`を使わない式と同じになっていることが分かります。

これで、`$`の仕組みを完全に解き明かすことができました。

---

※実は、優先順位と結合性も、先ほどのBase.hsで宣言されています。
執筆時点では145行目にあります。

```haskell
infixr 0  $, $!
```
`infixr`は右結合を意味します。(`infixl`なら左結合です。)
その横の数字は優先度を表しています。

つまり、`$`はコンパイラが特別に用意してくれた記号というわけではなく、
Haskellの文法に従って定義された演算子だったのです。
その気になれば自前の`$`を作ることも可能です。（！）

仕組みとしてとても美しいと思いませんか？