Vimの<C-f>でスクロールしていくと最後一行になってしまうのを直す設定

Vimの<C-f>を押していくと、最後に一行だけになってしまいます。 おっと行き過ぎたと言ってわざわざ戻っている方も多いのではないでしょうか。 この世の中にはたくさんスクロールのUIがありますが、普通はこうなっていません。 ウェブブラウザーのスクロールも、PDFビューワのスクロールも、lessコマンドのスクロールも、ページの一番下が画面の下に見えたら止まってくれます。

この挙動は、<C-f>を次のようにマッピングすると直ります。

noremap <expr> <C-f> max([winheight(0) - 2, 1]) . "\<C-d>" . (line('.') > line('$') - winheight(0) ? 'L' : 'H')

バッファーの最後の行がウィンドウの一番下になったらきちんと止まってくれます。 <C-d>はウィンドウをスクリーンの半分スクロールするマッピングです。 <C-f>と同様に[count]を受け取ることができますが、<C-d>はウィンドウの一番下がバッファーの最後の行を超えることはありません。 max([winheight(0) - 2, 1])は、ウィンドウの高さが小さすぎてもエラーにならないようにしています。 LやHというのは、スクロールはせずにスクリーンに表示されている一番下や上の行にカーソルを移動するマッピングです。 現在の行が最後の方ならL、すなわちスクリーンの最下行に移動し、そうでなければ一番上の行に移動します。

<C-b>は<C-f>ほど困るようなマッピングではありませんが、少し気に入らないことがあります。 上にスクロールしていった時に、一行目まで戻ってくれません。 これはあまり気持ちがよくないので、私は<C-f>のマッピングとのアナロジーで次のように設定しています。

noremap <expr> <C-b> max([winheight(0) - 2, 1]) . "\<C-u>" . (line('.') < 1 + winheight(0) ? 'H' : 'L')

最初のページになったらHで一行目に戻ります。 nnoremapではなくてnoremapなので、ビジュアルモードにも適用されて便利です。

スクロールするマッピングには他にも<C-e>や<C-y>などがあります。 これらも<C-f>や<C-b>と同じような問題があります。 つまり、<C-e>を押し続けると最後一行だけになってしまいますし、<C-y>は押し続けても途中で止まってしまって一行目まで行きません。 この挙動は私は好きじゃないので、次のようにマッピングしています。

noremap <expr> <C-y> (line('w0') <= 1         ? 'k' : "\<C-y>")
noremap <expr> <C-e> (line('w$') >= line('$') ? 'j' : "\<C-e>")

まとめ

最後は一ページ残った状態でスクロールが止まってくれるし、上に行くときはきちんと最初の行まで戻ってくれて便利な設定です。

noremap <expr> <C-b> max([winheight(0) - 2, 1]) . "\<C-u>" . (line('.') < 1         + winheight(0) ? 'H' : 'L')
noremap <expr> <C-f> max([winheight(0) - 2, 1]) . "\<C-d>" . (line('.') > line('$') - winheight(0) ? 'L' : 'H')
noremap <expr> <C-y> (line('w0') <= 1         ? 'k' : "\<C-y>")
noremap <expr> <C-e> (line('w$') >= line('$') ? 'j' : "\<C-e>")

<C-f>を押しすぎて最後必ず戻っている人は検討してみてください。

Haskellでimport文をソートするプラグイン vim-haskell-sort-import を作りました

Go言語には、gofmtというコードフォーマッターがあります。 標準ライブラリーで備えており、このフォーマッターをかけることを半ば強制することにより、Goで書かれたコードはどれも統一的なスタイルをしているように見えます。 gofmtには様々な機能がありますが、特にimportしているモジュールをソートしてくれるのが便利だなと思います。

フォーマッターがimportのモジュールをソートしてくれるのはとても便利です。 第一に、どのファイルにおいてもあるモジュールはだいたい同じ場所にあります。 例えばbufioモジュールは上のほうで、osモジュールは下のほうがといった感じです。 第二に、モジュールを追加するときにどこに追加すればよいかということに気を回さなくてすみます。 何か新しいモジュールを追加しようという時に、どこに追加するかについて私たちはかなり気を使っているように思います。 もちろん、import文をひっくり返しても言語の仕様上において意味は変わらないということが大前提にあります。

Haskellを書いていても、モジュールをどの位置にimportするか悩みます。 適当にimportを書いていくとファイルによってマチマチになりがちです。 そこでHaskellでもimport文を常にソートするようにしようと思いたち、Vimプラグインを作ってみました。 github.com このプラグインは一つのコマンドを提供します。 その名も、 HaskellSortImport です。 そのままですね。

例えば、次のようなコードがあったとします。

import Data.Monoid
import qualified Data.HashMap.Lazy as HM
import Control.Monad (forM_, when)
import Data.Hashable
import Data.Maybe (mapMaybe)
import Data.Char (isAlpha)
import Data.List (foldl')
import System.Info (os)
import System.IO (hFlush, stdout)
import System.Exit (ExitCode(..))

main :: IO ()
main = do
  ...

import文のモジュールはソートされていませんね。 ここで、次のコマンドを叩きます。

:HaskellSortImport

すると、次のようになります。

import Control.Monad (forM_, when)
import Data.Char (isAlpha)
import Data.Hashable
import qualified Data.HashMap.Lazy as HM
import Data.List (foldl')
import Data.Maybe (mapMaybe)
import Data.Monoid
import System.Exit (ExitCode(..))
import System.Info (os)
import System.IO (hFlush, stdout)

main :: IO ()
main = do
  ...

アルファベット順に綺麗に並びました。

vim-haskell-sort-importは、import文が改行で分かれていると各ブロックごとにソートするようになっています。 例えば、標準ライブラリーとローカルのライブラリーでごちゃまぜにして欲しくないということがあるでしょう。

import Data.Monoid
import System.IO (hFlush, stdout)
import Data.List (foldl')
import Control.Monad (forM_, when)

import XXX
import CCC
import DDD
import ZZZ
import AAA

main :: IO ()
main = do
  ...

これにHaskellSortImportを掛けると、次のようになります。

import Control.Monad (forM_, when)
import Data.List (foldl')
import Data.Monoid
import System.IO (hFlush, stdout)

import AAA
import CCC
import DDD
import XXX
import ZZZ

main :: IO ()
main = do
  ...

標準ライブラリーとごっちゃにならなくて安心です。

他にも、import文が複数行に跨る場合でもきちんと扱えます。

import System.IO ( hFlush,
                   stdout )
import Data.Monoid
import Data.List ( foldl',
                   mapAccumL,
                   mapAccumR )
import Control.Monad ( forM_,
                       unless,
                       when )

これに:HaskellSortImportすると、次のようになります。

import Control.Monad ( forM_,
                       unless,
                       when )
import Data.List ( foldl',
                   mapAccumL,
                   mapAccumR )
import Data.Monoid
import System.IO ( hFlush,
                   stdout )

コードは壊れていません。 安心です。

いちいちコマンドを叩くのは面倒なので、私はファイルを保存したら常にソートするように設定しています。 rtpの通っているどこかのftplugin/haskell.vimに、次のように書いておくと良いでしょう。

autocmd BufWritePre <buffer> HaskellSortImport

あるいは別の方法としては、vimrcに次のように書いておくとうまく動きます。

augroup vimrc-haskell-sort-import
  autocmd!
  autocmd BufWritePre *.hs HaskellSortImport
augroup END

ファイルを保存する度に容赦なくソートされます。 この設定をそのままにしつつ、一時的にソートせず保存したいときは、noa wすると良いと思います。

そんなわけで、Haskellのimport文をソートしてくれるプラグインを作りました。 VimでHaskellを書く方にはとても便利なプラグインだと思いますので、ぜひお使い下さい。 github.com

Haskellで無限個の無限リストをソートされた形で結合する

CodeforcesやProject Eulerの問題には、無限リストをうまく使うと綺麗に解くことができる問題がたくさんあります。 数列の性質から探索範囲の上界を決めて解を探索することが多いのですが、きちんとした根拠を持って上界を決めることができることは少なく、余裕を持って十分に広い範囲で計算して解を求める解法がよく取られます。

Haskellの特徴である遅延評価とその洗練された糖衣構文を用いると、無限リストを簡単に扱うことができます。 上界を適当に定める解法よりも、より宣言的で美しく、時に効率的なコードで同じ解を得ることができます。 しかし、無限リストをきちんと、それも無限個の無限リストをきちんと扱うとなると、意外と苦労します。

この記事では、無限個の無限リストをソートされた形で結合する方法について説明します。 一般的な無限リストではなく、条件はかなり絞っていてます (そうでないと原理的に解けません)。 まず、それぞれのリストはソートされていて、リストは無限個あるもののリストの要素間の大小は決まっているとします。 詳細は後々説明していきます。

いきなり無限個の無限リストを考えるのは難しいので、次の三通りを順番に考えて、簡単な問題から解いていくことにします。

1. 2つの無限リスト
2. 3つの無限リスト
3. 無限個の無限リスト

マージする方法も和集合と共通集合があります。

1. 和集合
2. 共通集合

この掛け合わせの6通りについて、問題と解いていく形式で説明を進めていきます。 以下の6つがこのエントリーで扱う問題です。

【問題】

• 三角数もしくは平方数である数のうち、小さい方から1000番目の数字を答えよ。
• 三角数でかつ平方数である数のうち、小さい方から7番目の数字を答えよ。
• 三角数または平方数または五角数である数のうち、小さい方から10万番目の数字を答えよ。
• 三角数でかつ平方数でかつ六角数である数のうち、小さい方から5番目の数字を答えよ。
• 正の整数のうち、ある奇素数pに対するp角数の要素であるような数の集合を考える。このような数の中で、小さい方から1万番目の数字を答えよ。
• 21は三角数であり八角数であり21角数であるため、多角数として三通りの表現ができる。多角数としてちょうど五通りの表現ができる数のうち、小さい方から150番目の数字を答えよ。

これらの問題をご自分で解きたいと思われた方は、ここで一旦記事を読むのをやめて解いてみてください。 解きますか？解きませんか？ もうこの下からは問題に対する解答が始まりますよ。

それでは、無限リストが織りなす宣言的な世界へようこそ。

2つの無限リストの和集合

【問題】三角数もしくは平方数である数のうち、小さい方から1000番目の数字を答えよ。

この記事ではghciで作業を進めていきます。 今回はpromptにモジュール名が出ていても特に嬉しいことはないので、隠しておきましょう。

 $ ghci
Prelude> :set prompt "> "
> :set prompt2 "| "

まず、平方数を定義してみます。

> let squares = [ n * n | n <- [1..] ]
> take 10 squares
[1,4,9,16,25,36,49,64,81,100]

次は三角数です。

> let triangulars = [ n * (n + 1) `div` 2 | n <- [1..] ]
> take 10 triangulars
[1,3,6,10,15,21,28,36,45,55]

これらを結合して小さい方から1000番目の数字を取り出しましょう。 単純な解法は、次のようなものが考えられるでしょう。

> import Data.List
> let n = 1000 in sort (union (take n squares) (take n triangulars)) !! (n - 1)
173166

答えが出ました。平方数または三角数の正の整数のうち、1000番目の数字は173166です。 1000番目を求めよという問題なので、それぞれの数列から1000個取ってきて和集合をとり、ソートして1000番目を返すという感じです。

しかし、このような問題に対しては、unionもsortも使うべきではありません。 とても効率が悪く、100万番目を求めてくださいという問題だと、現実的な時間で解くことができません。

> let n = 1000000 in sort (union (take n squares) (take n triangulars)) !! (n - 1)
^CInterrupted.

しばらく待ちましたが、返ってきませんでした。

2つのリストが既にソートされていると分かっているのに、unionやsortを使うは無駄な計算です。 結合してからソートするのではなく、まるでファスナーを上げるように、結合しながらソートされたリストを作ることができます。

> :{
| let union2 xs [] = xs
|     union2 [] ys = ys
|     union2 xxs@(x:xs) yss@(y:ys)
|       | x < y = x : union2 xs yss
|       | x == y = x : union2 xs ys
|       | otherwise = y : union2 xxs ys
| :}
> let n = 1000 in union2 squares triangulars !! (n - 1)
173166

同じ答えが出ました。 もちろん、この方法は最初に考えたunionしてsortする方法よりも圧倒的に高速です。

> let n = 100000 in union2 squares triangulars !! (n - 1)
1716013236
> let n = 1000000 in union2 squares triangulars !! (n - 1)
171575840736

10万番目だろうと100万番目だろうとすぐに答えが返ってきます。

このunion2関数は、ソートされた2つのリストをソートされた形でマージする関数です。 大事な関数なのでもう一度書いておきます。

union2 xs [] = xs
union2 [] ys = ys
union2 xxs@(x:xs) yss@(y:ys)
  | x < y = x : union2 xs yss
  | x == y = x : union2 xs ys
  | otherwise = y : union2 xxs ys

上記の問題の制約上、同じ数字は省いており、しかも入力のリストはどちらも真に増えていく (strictly increasing) 数列でなくてはなりません。 この条件を緩めて、単純に増えていく (同じ数字が続いても良い) 数列を受け付けて、かつ重複は省略しないならば、次のような実装になるでしょう。

union2' xs [] = xs
union2' [] ys = ys
union2' xxs@(x:xs) yss@(y:ys)
  | x <= y = x : union2' xs yss
  | otherwise = y : union2' xxs ys

この2つの関数の違いは、以下の結果で一目瞭然です。

> union2 [1..10] [1..10]
[1,2,3,4,5,6,7,8,9,10]
> union2' [1..10] [1..10]
[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]

いずれにせよ、入力がソートされているならば、効率よくソートされた結合リストを作ることができるということが分かります。 これら2つの関数はどちらが良いとか悪いとかではなく、入力に課している条件も結果も違いますので、問題によって使い分けることになります。 入力は同じ数字が続くかもしれない増加数列で、かつ重複しないようにマージする関数を書くことは、読者への課題とします (ヒント: dropWhile)。

2つの無限リストの共通集合

【問題】三角数でかつ平方数である数のうち、小さい方から7番目の数字を答えよ。

先ほどの問題では、1000番目と言われたときには三角数の1000番目までか、もしくは平方数の1000番目までかのいずれかに必ず含まれるということが分かっていました。 しかし、今回の場合、最初にいくつ取ればいいのか分かりません。

> intersect (take 100 triangulars) (take 100 squares)
[1,36,1225]

試しに100個ずつとってみて、共通するのは3つだけでした。 7番目と言われているので、簡単に見つかるのではと思うかもしれませんが、なかなか見つかりません。

> intersect (take 5000 triangulars) (take 5000 squares)
[1,36,1225,41616,1413721]
> intersect (take 10000 triangulars) (take 10000 squares)
[1,36,1225,41616,1413721,48024900]
> intersect (take 50000 triangulars) (take 50000 squares)
[1,36,1225,41616,1413721,48024900^CInterrupted.

すでに6個求まっているのであと少しなんですが、数を増やすとえらく時間がかかってしまいます。

ここで、triangularsやsquaresがソートされていることを思い出します。 しかも、どちらも真に増加していく数列です。 先ほどのunion2関数と同じ要領で、入力がソートされていると仮定したintersect2関数を定義してみます。

> :{
| let intersect2 _ [] = []
|     intersect2 [] _ = []
|     intersect2 xxs@(x:xs) yss@(y:ys)
|       | x < y = intersect2 xs yss
|       | x == y = x : intersect2 xs ys
|       | otherwise = intersect2 xxs ys
| :}
> take 7 $ intersect2 triangulars squares
[1,36,1225,41616,1413721,48024900,1631432881]

すぐに求まりました！ 三角数でありかつ平方数である数の7番目の数は、1631432881です！

一見良さそうに見えますが、残念ながらこの方法でも20個求めようとなると時間がかかりすぎてしまいます。

> take 20 $ intersect2 triangulars squares
[1,36,1225,41616,1413721,48024900,1631432881,55420693056,1882672131025^CInterrupted.

この結果を見ると、だいたい34倍ずつになっていることが分かります。

> let xs = intersect2 triangulars squares in zipWith (\x y -> fromIntegral x / fromIntegral y) (tail xs) xs
[36.0,34.02777777777778,33.972244897959186,33.97061226451365,33.97056420609158,33.970562791385305,33.97056274974024,33.970562748514325^CInterrupted.

はて、何やら法則でもあるのかしらと思って、OEISで一般項を調べます。 OEISに「1,36,1225,41616」と入力すると、A001110が見つかります。 FORMULAのところを見ると、次のような漸化式が書かれています。

a(0) = 0, a(1) = 1; for n >= 2, a(n) = 34 * a(n-1) - a(n-2) + 2.

なるほど、漸化式に34という係数がありますね。 なぜこうなるのかはさておき、数学者が一生懸命研究して導き出した漸化式ですから、正しいことを期待してghciで定義して30番目まで求めてみましょう。

> let squareTriangulars = 0 : 1 : zipWith (\x y -> 34 * x - y + 2) (tail squareTriangulars) squareTriangulars
> take 30 squareTriangulars
[0,1,36,1225,41616,1413721,48024900,1631432881,55420693056,1882672131025,63955431761796,2172602007770041,73804512832419600,2507180834294496361,85170343853180456676,2893284510173841030625,98286503002057414584576,3338847817559778254844961,113422539294030403250144100,3853027488179473932250054441,130889512058808083293251706896,4446390382511295358038307980025,151046383493325234090009219613956,5131130648390546663702275158894481,174307395661785261331787346182798400,5921320321852308338617067495056251121,201150583547316698251648507485729739716,6833198520286915432217432187019754899225,232127599106207807997141045851185936833936,7885505171090778556470578126753302097454601]

一瞬で求まりました。 OEISの解答で答え合わせをして、あっていることを確認しましょう。 三角数でかつ平方数である数列を求める問題は、あるペル方程式の解に帰着することがWikipediaの記事やMathWorldの記事を見ると分かります。

3つの無限リストの和集合

【問題】三角数または平方数または五角数である数のうち、小さい方から10万番目の数字を答えよ。

まずは五角数を定義します。

> let pentagonals = [ n * (3 * n - 1) `div` 2 | n <- [1..] ]
> take 10 pentagonals
[1,5,12,22,35,51,70,92,117,145]

定義できました。

3つのソートされた (しかも真に増加していく) 数列 triangulars, squares そして pentagonals を小さい順にマージしていきます。 とりあえずどれも無限リストなので、引数が[]になることは考えないことにします。

> :{
| let union3 xxs@(x:_) yss@(y:_) zzs@(z:_)
|       = w : union3 (dropWhile (==w) xxs) (dropWhile (==w) yss) (dropWhile (==w) zzs)
|           where w = minimum [ x, y, z ]
| :}

<interactive>:96:5: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘union3’:
        Patterns not matched:
            [] _ _
            (_ : _) [] _
            (_ : _) (_ : _) []
> take 100 $ union3 triangulars squares pentagonals
[1,3,4,5,6,9,10,12,15,16,21,22,25,28,35,36,45,49,51,55,64,66,70,78,81,91,92,100,105,117,120,121,136,144,145,153,169,171,176,190,196,210,225,231,247,253,256,276,287,289,300,324,325,330,351,361,376,378,400,406,425,435,441,465,477,484,496,528,529,532,561,576,590,595,625,630,651,666,676,703,715,729,741,780,782,784,820,841,852,861,900,903,925,946,961,990,1001,1024,1035,1080]
> take 100 (union3 triangulars squares pentagonals) == take 100 (sort (take 100 triangulars `union` take 100 squares `union` take 100 pentagonals))
True

ちゃんと合ってそうですね。 10万番目の数を求めてみます。

> let n = 10000 in union3 triangulars squares pentagonals !! (n - 1)
9603153
> let n = 100000 in union3 triangulars squares pentagonals !! (n - 1)
958335849

求めることができました！ 三角数または平方数または五角数である正の整数で、10万番目の数は958335849だということが分かりました。

3つの無限リストの共通集合

【問題】三角数でかつ平方数でかつ六角数である数のうち、小さい方から5番目の数字を答えよ。

まずは六角数を定義しましょう。

> let hexagonals = [ n * (2 * n - 1) | n <- [1..] ]
> take 10 hexagonals
[1,6,15,28,45,66,91,120,153,190]

3つの無限リストの共通集合です。 これらのリストは真に増加するリストなので、それぞれの最初の数を比較して小さいものは落としていけばよいことが分かります。

> :{
| let intersect3 xxs@(x:xs) yss@(y:ys) zzs@(z:zs)
|       | x < y || x < z = intersect3 xs yss zzs
|       | y < z || y < x = intersect3 xxs ys zzs
|       | z < x || z < y = intersect3 xxs yss zs
|       | otherwise = x : intersect3 xs ys zs
| :}

<interactive>:138:5: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘intersect3’:
        Patterns not matched:
            [] _ _
            (_ : _) [] _
            (_ : _) (_ : _) []

引数が[]であるときに対応できていないという警告が出ていますが、とりあえず今は無限リストに対して使うので無視します。 三角数でかつ平方数でかつ六角数であるような数は、次のようになります。

> take 5 $ intersect3 triangulars squares hexagonals
[1,1225,1413721,1631432881,1882672131025]

従って、求めるべき5番目の数は1882672131025であることが分かりました。 OEISに「1,1225,1413721,1631432881,1882672131025」と入力すると、A046177が見つかり、確かに答えがあっていることを確認できます。 OEISに書かれている漸化式をコードに落として30番目まで求めるのは、読者への課題とします。

実はこの問題はintersect3を使わなくても解けてしまいます。 全ての六角数は三角数でもあるからです。

> take 1000 (intersect2 triangulars hexagonals) == take 1000 hexagonals
True

従って、intersect2を使えば解けてしまいます。

> take 5 $ intersect2 squares hexagonals
[1,1225,1413721,1631432881,1882672131025]

同じ答になりましたね。 なんじゃそれと思われるかもしれませんが、問題を解く前にきちんと数学的な性質を調べて無駄な計算をしないことはとても大切なことなのです。

ここまで理解できた方はProject Euler 45を簡単に解くことができるでしょう。

無限個の無限リストの和集合

【問題】正の整数のうち、ある奇素数pに対するp角数の要素であるような数の集合を考える。このような数の中で、小さい方から1万番目の数字を答えよ。

まずは、Wikipediaの記事から多角数表を引っ張ってきます。

k	n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
3	1	3	6	10	15	21	28	…
4	1	4	9	16	25	36	49	…
5	1	5	12	22	35	51	70	…
6	1	6	15	28	45	66	91	…
7	1	7	18	34	55	81	112	…
8	1	8	21	40	65	96	133	…
9	1	9	24	46	75	111	154	…
10	1	10	27	52	85	126	175	…
11	1	11	30	58	95	141	196	…
12	1	12	33	64	105	156	217	…
13	1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙	︙

奇素数pのp角数と言われているので、該当する行のみ抽出します。

k	n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
3	1	3	6	10	15	21	28	…
5	1	5	12	22	35	51	70	…
7	1	7	18	34	55	81	112	…
11	1	11	30	58	95	141	196	…
13	1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙	︙

この表に含まれている数を、小さい方から並べていきます。

1, 3, 5, 6, 7, 10, 11, 12, 13, 15 ...

すぐに分かることは、この数列は素数を全て含んでいるということです。 素数以外にも 1, 6, 10, 12, 15 のような数が含まれています。

素数は無限個あります。 ある素数pに対して、p角数は無限リストです。 すなわち、無限個の無限リストを、結合して小さい方から並べなさいという問題なのです。 無限個の無限リスト… この問題は解くことができるのでしょうか？

これまではせいぜい2つや3つの無限リストをマージしてきました。 しかし、同じ考え方では今回の問題は解けそうにありません。

> let union' xxs@(x:_) yss@(y:_) zzs@(z:_) wws@(w:_) uus@(u:_) ...

いえいえ、もちろん引数はリストのリストですよね。

> let union' xss = let w = minimum (map head xss) in ...

map head xssは無限リストなので、minimumを取ることができません。

私たちは、「奇素数角数表」を眺めながら、小さい方から順番に数字を言うことができます。 それは、この表が右に行くほど、下に行くほど大きくなるという性質があるからです。 改めて、表を見ながら私たちが小さい方から数字を言っていく時に何を考えているのか調べてみましょう。

まず、1はどの行にも一列目にあります。 次に、一列目を除いたら右に行くほど下に行くほど大きくなるので、次の数字は二列目以降の左上にある3ということが分かります。

n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
1	3	6	10	15	21	28	…
1	5	12	22	35	51	70	…
1	7	18	34	55	81	112	…
1	11	30	58	95	141	196	…
1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙

次に比較するのは6, 5です。 小さい5を取ります。

n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
1	3	6	10	15	21	28	…
1	5	12	22	35	51	70	…
1	7	18	34	55	81	112	…
1	11	30	58	95	141	196	…
1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙

次に、6, 12, 7で比較して、6を選びます。

n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
1	3	6	10	15	21	28	…
1	5	12	22	35	51	70	…
1	7	18	34	55	81	112	…
1	11	30	58	95	141	196	…
1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙

10, 12, 7で比較して、7を選びます。

n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
1	3	6	10	15	21	28	…
1	5	12	22	35	51	70	…
1	7	18	34	55	81	112	…
1	11	30	58	95	141	196	…
1	13	36	70	115	171	238	…
︙	︙	︙	︙	︙	︙	︙	︙

ようやく私たちがどのように数を列挙しているか分かってきたことでしょう。 比較すべき数はどんどん増えていきます。 赤くなっている数字よりも右や下は考える必要はありません。 7を選んだ時、18や11が次に比較すべき数字の対象に追加されます。 次に10、11、12と選ぶと、15, 22, 18, 30, 13が比較対象となります。

ルールが分かってきたのでコードに落とし込める気がしてきました。 頑張って実装していきましょう。

まずは素数を定義します。 適当なパッケージを使っても良いですが、素数のリストを定義するのは2行書いてあげれば事足ります。 「素数のリスト」は「2と素数である奇数」で、「ある数が素数である」とは「その数の平方根以下の素数でその数を割り切れない」ということです。

> :{
| let primes = 2 : filter isPrime [3,5..]
|     isPrime n = n > 1 && foldr (\p r -> p * p > n || n `mod` p /= 0 && r) True primes
| :}
> take 100 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

きちんと素数になっていますね。 大丈夫そうです。

次に、多角数を定義します。 三角数は自然数の和ですし、平方数は奇数の和です。 一般に、等差数列を足していくと多角数になります。

> let polygonals k = scanl1 (+) [1,k-1..]
> take 10 $ polygonals 3
[1,3,6,10,15,21,28,36,45,55]
> take 10 $ polygonals 4
[1,4,9,16,25,36,49,64,81,100]
> take 10 $ polygonals 5
[1,5,12,22,35,51,70,92,117,145]
> take 10 $ polygonals 6
[1,6,15,28,45,66,91,120,153,190]
> take 1000 (polygonals 5) == take 1000 pentagonals
True
> take 1000 (polygonals 6) == take 1000 hexagonals
True

OKですね。

試しに、「奇素数角数表」を表示してみます。 奇素数ではない素数は2だけなので、奇素数はtail primesです。

> mapM_ print [ (p, take 10 $ polygonals p) | p <- take 10 (tail primes) ]
(3,[1,3,6,10,15,21,28,36,45,55])
(5,[1,5,12,22,35,51,70,92,117,145])
(7,[1,7,18,34,55,81,112,148,189,235])
(11,[1,11,30,58,95,141,196,260,333,415])
(13,[1,13,36,70,115,171,238,316,405,505])
(17,[1,17,48,94,155,231,322,428,549,685])
(19,[1,19,54,106,175,261,364,484,621,775])
(23,[1,23,66,130,215,321,448,596,765,955])
(29,[1,29,84,166,275,411,574,764,981,1225])
(31,[1,31,90,178,295,441,616,820,1053,1315])

この右にも下にも無限に続く数列たちを、頑張ってマージしていかなくてはいけません。

まず、作りたい和集合を取る関数の型は、

> :{
| let union' :: Ord a => [[a]] -> [a]

としましょう。 マージしながら、次にいくつ数を取って比較するかという数字を持ち越します。 最初は1つなので、適当にgo 1と書いてからgo関数を一所懸命実装します。

|     union' = go 1
|       where
|         go k xss = let (k', m, yss) = extractMin k xss in m : go k' yss

extractMinは、リストのリストからk個とってそれらの最初要素の中で最小のものを見つけつつ、その要素を落としたものを返します。 慎重に定義しましょう。

|         extractMin k xss = (max k (l + 1), m, yss)
|           where
|             m = minimum $ map head $ take k xss
|             (l, yss) = extract m 1 xss

mは、リストのリストxssからk個とったそれらの最初の要素たちの最小です。 extractはリストのリストxssから初めて見つけたmを抜き出す関数です。 lはmを何番目のリストで見つけたかという数字が返ってきます。

|         extract m l (xxs@(x:xs):yss)
|           | x == m = (l, xs:yss)
|           | otherwise = fmap (xxs:) $ extract m (l + 1) yss
| :}

<interactive>:25:9: Warning:
    Pattern match(es) are non-exhaustive
    In an equation for ‘extract’:
        Patterns not matched:
            _ _ []
            _ _ ([] : _)

最初のリストの最初の要素がmであれば、それを取ってxs:yssを返します。 extract関数で引数が[]や[]:_であるケースに対応できていないと怒られていますが、とりあえず今考えているのは無限リストなので放っておきます。

ようやく定義できたunion'関数をさっそく使ってみましょう。

> take 30 $ union' [ polygonals p | p <- tail primes ]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

おっと、そうでした。 どの多角数も最初は1なので、これを除外しないと「右に行くほど下に行くほど大きく」という条件が達成されません。 それぞれの多角数の最初は無視することにします。

> take 30 $ union' [ tail (polygonals p) | p <- tail primes ]
[3,5,6,7,10,11,12,13,15,17,18,19,21,22,23,28,29,30,31,34,35,36,36,37,41,43,45,47,48,51]

一見良さそうに見えますが、よく見ると36が被ってしまっていますね。 36は三角数でありかつ十三角数でもあります。 実は上のextract関数では、数が重複した時にそれを一つだけにしていません。 ソートされたリストの重複を除くのは、map head . groupを使うのがお手軽です。 あと最初の1を追加しておきます。

> let primePolygonals = 1 : map head (group (union' [ tail (polygonals p) | p <- tail primes ]))
> take 30 primePolygonals
[1,3,5,6,7,10,11,12,13,15,17,18,19,21,22,23,28,29,30,31,34,35,36,37,41,43,45,47,48,51]

やったー！ できました！ 重複もしていません。 この結果を表とじっと見比べたり、

k	n=1	n=2	n=3	n=4	n=5	n=6	n=7	…
3	1	3	6	10	15	21	28	…
5	1	5	12	22	35	51	70	…
7	1	7	18	34	55	81	112	…
11	1	11	30	58	95	141	196	…
13	1	13	36	70	115	171	238	…
17	1	17	48	94	155	231	322	…
19	1	19	54	106	175	261	364	…
23	1	23	66	130	215	321	448	…
︙	︙	︙	︙	︙	︙	︙	︙	︙

あるいは

> take 100 primePolygonals == take 100 (sort (foldl1 union [ take 100 (polygonals p) | p <- take 100 (tail primes) ]))
True

愚直に求めたものと合致することを確認して正しいことを確認します。 最後に問題に対する答を出します。

> let n = 10000 in primePolygonals !! (n - 1)
40641

出ました！ 奇素数の多角数の中で小さい方から数えて1万番目の数は40641ということが分かりました！ 無限個の無限リストをマージして小さい方から列挙することができました！

上記のコードをファイルにして実行できる形にしておきます。

import Data.List (group)

main :: IO ()
main = do
  print $ take 100 primePolygonals
  let n = 10000
  print $ primePolygonals !! (n - 1)

primes :: Integral a => [a]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integral a => a -> Bool
isPrime n = n > 1 && foldr (\p r -> p * p > n || n `mod` p /= 0 && r) True primes

polygonals :: Integral a => a -> [a]
polygonals k = scanl1 (+) [1,k-1..]

primePolygonals :: Integral a => [a]
primePolygonals = 1 : map head (group (union' [ tail (polygonals p) | p <- tail primes ]))

union' :: Ord a => [[a]] -> [a]
union' = go 1
  where
    go k xss = let (k', m, yss) = extractMin k xss in m : go k' yss
    extractMin k xss = (max k (l + 1), m, yss)
      where
        m = minimum $ map head $ take k xss
        (l, yss) = extract m 1 xss
    extract m l (xxs@(x:xs):yss)
      | x == m = (l, xs:yss)
      | otherwise = fmap (xxs:) $ extract m (l + 1) yss

意外とシンプルでしょう？ union'関数の引数が有限長のリストであったり有限個だったりするとうまく動かないので、これらに対応させるのは読者への課題とします (ヒント: concatMap (take 1))。

この無限個の無限リストを結合して小さい方から列挙する関数union'を用いると、Project Euler 126をきれいに解くことができます。 実はこの問題は、このエントリーを書き始めたきっかけの問題です。 Project Euler 126を解いている過程で、無限個のリストを処理する必要があり、書いてみたら意外とちゃんと動いたので勢いでこのエントリーも書いたというわけです。 無限リストを自在に操れるようになると、「この問題にはいくら以下でおそらく答えが見つかるだろうからこのくらいの長さの配列を作ってその中で解を探す」みたいな雑な見積もりをせずとも、宣言的ですっきりとしたコードを書くことができます。

無限個の無限リストの中のいくつかに含まれる集合

【問題】21は三角数であり八角数であり21角数であるため、多角数として三通りの表現ができる。多角数としてちょうど五通りの表現ができる数のうち、小さい方から150番目の数字を答えよ。

今回の問題では、「多角数として五通りの表現ができる数」となっています。 全ての多角数に含まれる数は1しかありません。 なぜなら全ての多角数の最初の要素は1である上に、任意の2以上の数kはk角数に含まれないからです。 「五つの多角数の数列に含まれている」と表現することで、問題が数学的に意味を持つのです。

実は、先ほどのunion'関数は重複を除外しないので、これを使うと問題を簡単に解くことができます。

main :: IO ()
main = do
  print $ take 100 polygonalsIntersection
  let n = 150
  print $ polygonalsIntersection !! (n - 1)

polygonalsIntersection :: Integral a => [a]
polygonalsIntersection = map head (filter ((==5) . length) (group (union' [ tail (polygonals p) | p <- [3..] ])))

groupしてその長さが5となるものでfilterするだけです。 実行すると次のようになります。

[225,231,276,325,435,441,540,595,616,651,820,861,936,946,1035,1089,1128,1275,1288,1296,1326,1431,1521,1596,1716,1881,1926,1936,2025,2080,2145,2205,2211,2296,2380,2415,2485,2541,2640,2745,2835,2871,2916,2925,2961,3136,3160,3186,3201,3312,3381,3430,3486,3537,3655,3745,3816,3825,3861,4096,4200,4221,4225,4236,4356,4371,4465,4564,4576,4641,4656,4845,4941,4950,4992,5005,5076,5151,5160,5265,5292,5356,5481,5551,5625,5656,5685,5776,5886,5929,5995,6076,6084,6105,6111,6201,6345,6441,6480,6501]
10206

従って、答は10206です！ それぞれの数字がどの多角数に属するか求めるのも難しくありません。

> let elem' x xs = x == head (dropWhile (<x) xs)
> mapM_ print [ [ (p, q) | q <- [3..p], elem' p (polygonals q) ] | p <- polygonalsIntersection ]
[(225,4),(225,8),(225,24),(225,76),(225,225)]
[(231,3),(231,6),(231,17),(231,78),(231,231)]
[(276,3),(276,6),(276,20),(276,93),(276,276)]
[(325,3),(325,6),(325,9),(325,34),(325,325)]
[(435,3),(435,6),(435,45),(435,146),(435,435)]
[(441,4),(441,14),(441,31),(441,148),(441,441)]
[(540,7),(540,10),(540,21),(540,181),(540,540)]
[(595,3),(595,15),(595,30),(595,61),(595,595)]
[(616,7),(616,13),(616,31),(616,104),(616,616)]
[(651,5),(651,9),(651,45),(651,218),(651,651)]
[(820,3),(820,20),(820,31),(820,138),(820,820)]
^CInterrupted.
>

225は15番目の平方数であり (1+3+5+..+29=15*15)、9番目の八角数であり (1+7+13+19+25+31+37+43+49)、5番目の24角数であり (1+23+45+67+89)、3番目の76角数であり (1+75+149)、そして最初の225角数です。

おわりに

CodeforcesやProject Eulerには、2つ以上のパラメーターによって特徴づけられる数列を集計して答えを求める問題がたくさん出てきます。 いくつまでに答えが見つかるはずだから (この根拠は勘である場合もあったり数学的に証明できる上界だったりする・コンテスト中にあまりきちんと証明している暇はない) 固定長の配列を用意し、探索するパラメータの上限も適当なところで打ち切り、一気に二重ループを回してしまってから配列から答を得るという方法がよく取られます。

このエントリーでは、多角数を題材にとって、無限個の無限リストを扱う方法を紹介してみました。 多角数でなくても「右に行くほど下に行くほど大きくなる」というような構造がある場合は、このエントリーの関数をそのまま使うことができますし、そうでなくてもチェックする数を持ち越していくやり方は一般的に使えるテクニックでしょう。 無限リストをきちんと扱えるようになると、解を探索する上界を意識する必要がなくなりますし、コードも美しくなります。 また、無駄な計算をしないため、探索範囲を決めて計算する解法よりも速く計算できる可能性もあります。

大事なことは、データの構造や型の制約を考えて適切な関数を使うことです。 例えば簡単な例としては、10000未満の素数はいくつあるか？という問題には、filterではなくてtakeWhileを使うでしょう。 これは素数リストがどんどん大きくなるという性質を使っています。 既にソートされているリストの重複を除きなさいと言われたら、nubではなくてgroupを使うでしょう。 リストがソートされていないとしても、順序がつく型 (Ordのinstance) ならば存在する要素をSetで持ち回すとnubよりも計算オーダーの低い関数を書くことができます。 つまり、型に制約を課していくと、その型の構造をうまく用いたデータ構造を使って計算量を落とすことができる可能性があるということです。

Haskellは遅延評価の評価戦略を取っており、また豊富な糖衣構文により、無限リストを簡単に扱うことができます。 Project Eulerのように数学的な問題を解く上で、無限リストをどれだけうまく使いこなせるかというのは重要なことです。 無限個の無限リストをきちんと扱うのは大変なことです。 目の前にあるデータの数学的な性質をしっかりと見抜き、効率のよいアルゴリズムを考えて、問題を解くことを楽しんでください。

2015年を振り返って

今年は働き始めた年でした。環境が大きく変わりました。新しい環境は毎日刺激が多く、とても楽しく過ごしています。

入社してちょうど三か月した時、自分にとってとても大きなことが起こりました。ある仕事を与えられたのですが、その解決したい問題に対するアプローチを自ら考えて、自発的に編み出した解決法によって問題を解決したのです。入社してまだ間もないひよっこのような自分が、自らの能力を活かしてプロダクトに貢献できたことで、とても自信がつきましたし、この会社で自分が役に立っていけそうという安心感もありました。この成果によって社内の人からも評価していただき、とても嬉しく思いました。

今年はブログは28記事書きました。特に以下の記事は、多くの方々から反応をいただきとても感謝しています。 itchyny.hatenablog.com itchyny.hatenablog.com itchyny.hatenablog.com 自らのアイディアを形にし、記事を書いて多くの方に評価していただくのはとても楽しいことです。 sjspもrexdepも目の前に解決したい問題があり、それに対する自分が出した直球の解を披露したものです。 PDFの記事はかなり異色で、社内の人たちから今でも「それでは今からitchynyくんが5分でPDFの解説をしてくれます」のような冗談を言われたりします。 記事の長さに圧倒されてしまって最初の方を少しスクロールして閉じてしまった方もいらっしゃるかもしれませんが、中には詳細PDF入門をリファレンスとしてじっくり読んでいただき、新しく便利なソフトウェアを作っていただいた方もいらっしゃいました。 本当に嬉しい限りです。 自分は昔から人に教えることが好きで、自分が知っていることを人に教えて広めたいという欲求が技術エントリーに繋がっているのだと思います。 今後も定期的に技術的なエントリーを書き続けていきたいと思います。

私が技術エントリーを書くときに気をつけていることは、三つあります。 一つ目は、既存のものとの比較をはっきりと書くことです。 換言すると、新しいツールを作る動機を読者に共感してもらうということです。 二つ目は、文章の骨子を意識することです。 適当な節や段落に分けて、節にはよいタイトルをつけます。 そして各段落の一文目に重要な文を置きます。 各段落の一文目を順番に読んでいくと、だいたいそのエントリーの内容が分かるようにします。 これを厳格に守ると文章が少し機械的になってしまいますので、最後のほうにかけてこのスタイルを少しずつ崩していくと読みやすいと思います。 三つ目は、自分を卑下せず自信を持つことです。 自分が作ったものや書いているエントリーに自信を持つことはとても大事です。 自信をもって作ったものを世に出すからこそ、世の中の人に批評されるのだと思います。 自分が作ったものは所詮くだらないものだと思っていたのでは、そんな気持ちで書いたエントリーは誰にも読まれないと思います。 自分はよい物を作っていると自信を持つことは大事です。

今年はScalaとGoを始めました。 Scalaはとても奥深い言語で、常に勉強になります。 Scalaをしっかりと学ぶことで、オブジェクト指向の難しさを改めて感じています。 Goはまだまだ勉強中です。 その設計は気に入らないところも多いのですが、有用な言語であることは認識していますので、これからも使っていきたいと思います。

私の一番好きな言語はHaskellです。 まだまだ勉強できていない分野も多く、エキスパートというわけではないですが、それなりに得意だと思います。 例えばsjspでもHaskellを使いましたし、詳細PDF入門でもHaskellのコードを載せて解説しています。 また、つい先日にも以下のエントリーを書きました。 itchyny.hatenablog.com このエントリーはがっつりとしたHaskellの記事ですし、閲覧数もあまり伸びませんでしたが、Haskellを得意とされている方々から反応をいただきとても嬉しく思いました。 Haskellは便利ですし、当分は自分の一番好きな言語であり続けると思います。 何よりも、Haskellなんて理論屋のおもちゃで演算子は難しくて読めないし役に立たないと思われがちなのが悲しいのです。 便利ソフトウェアを作った→実はHaskell製でしたというストーリーが好きなので、今後もそういうエントリーが出てくるかもしれません。

Vimの活動はめっきり減ってしまいました。 新しいプラグインはちょくちょく作っていますが、どれも自分が快適にファイルを編集するためのツールという感じなので、あまり宣伝はしていません。 ずっとVimは使っていますが、Vim自体に対するモチベーションも減っていて、Lingr部屋を覗きに行くことも少なくなってしまいました。 とは言え、かつて作ったlightline.vimのスターは伸び続けていて、1300の大台に乗りました。 またVimエントリー向けの記事でlightline.vimをインストールされているのを見るなど、使っていただいている雰囲気を感じることもあります。 また、calendar.vimもじわじわとスターを伸ばしていて、きちんと機能開発をしていかなければと感じています。 そのうちcalendar.vimの技術的な解説をしたいのですが、モチベーションも低くて書けていません。

今年はよい一年でした。 来年も頑張っていきましょう。

景「私は今を思いっきり走り続けたい」

ef - a tale of memories., ep. 12

Haskellで書かれたおもしろいFizzBuzz ― Haskellで読めないコードに遭遇した時に解読する方法を徹底解説！

Haskellには抽象的な高階関数や演算子がいくつもあり、たまにそれらを巧妙に用いたコードがでてきて感心することがあります。 他の人が書いたHaskellのコードを読んでいると、なかなか面白いものと遭遇したりします。 巧妙に書かれたコードを解読していくと、実は型クラスのinstanceをうまく組み合わせて使っていて、とてもよい教材になることがあります。

実際にアプリケーションコードを書いていてここまで技巧的なコードを書くわけではありません。しかし、こういうコードを読み解くのは型クラスのいい練習になりますし、それまで知らなかったinstanceと遭遇したりしたときは、とても勉強になるのです。

このエントリーでは、とても技巧的なFizzBuzzを紹介し、それを読み解いていく方法を紹介します。 Haskellの初心者向けに、どういうふうに関数や型を調べて言ったらいいかを丁寧に書いています。 Haskellの難しいコード見ても何から手を付けていいか分からないという方や、そもそもHaskellのコード読む時ってどうやってリファレンスを引くの？という方には、ぜひ関数や型クラスなどを調べる方法を身につけて欲しいと思います。

注意: この記事の内容は古くなっていますが、当時のままあえて書き直していませんのでご注意ください。<> は現在は Data.Semigroup の演算子です。

目次

導入 ― おもしろいFizzBuzz

Twitterを眺めていたらCAMPHOR- Advent Calendarの26日目の記事が流れてきて、Haskellに関する内容だったので開いて読んでいました。 ryota-ka.hatenablog.com この記事ではMonad (Either a)の>>=演算子を使ってうまく結果を集めていますね。

自分もEitherとかMonadとか使ったおもしろFizzBuzzを書いてみようとしましたが、結局うまく書けませんでした。

import Data.Maybe (catMaybes, listToMaybe)

main = mapM_ (print . fizzbuzz) [1..100]

fizzbuzz n = concat $ catMaybes [ listToMaybe [ "Fizz" | n `mod` 3 == 0 ], listToMaybe [ "Buzz" | n `mod` 5 == 0 ] ]

catMaybes :: [Maybe a] -> [a] を使ってmod 3とmod 5の結果を集めてみましたが、この後どうすればいいかよく分かりませんでした。 ここでconcatを使わずにlistToMaybeを用いると、15の倍数のBuzzが落ちてしまいます。 かと言って""をまたNothingにマップするString -> Maybe Stringを書くのも、なんか一旦Stringに落としたものをまた持ち上げている感じがして嫌な気分です。 [] -> Nothing でそれ以外の時は関数をかますことができる、[a] -> ([a] -> b) -> Maybe bを書こうかと思いましたが、どうもキレイじゃない気がします。

綺麗に書けなくて困ったので、Beautiful FizzBuzz in Haskellとかで適当にググってカッコイイFizzBuzzを探していたところ、とても興味深いFizzBuzzを見つけました。

I finally bothered to implement FizzBuzz. I would fail the interview anyway, though...

let (m ~> str) x = str <$ guard (x `mod` m == 0)
in map (fromMaybe . show <*> 3 ~> "fizz" <> 5 ~> "buzz")

reddit Haskell: I Did A Haskell: fizzbuzz

なるほど、わからん

何をやっているかさっぱり分かりませんね。(<>) や (<*>) など、平均的なHaskellerが普段から使っている演算子でも、このコードになるとなんでここに使えるのか、型はどうやって合致しているのか、すぐには理解できないと思います。 一体どんな仕組みでこのコードが成り立っているのか、これを書いた人はどうやってこのコードを組み立てたのか、調べてみましょう。

コードを理解しよう

まずは必要なモジュールなどを含め、実行できる形にコードを整えてみました。 (GHC 7.10.x以降をお使いの方は、Control.ApplicativeとData.Functorのimportは不要です。)

import Control.Applicative ((<*>))
import Control.Monad (guard)
import Data.Functor ((<$))
import Data.Maybe (fromMaybe)
import Data.Monoid ((<>))

main :: IO ()
main = mapM_ (putStrLn . fizzbuzz) [1..100]

fizzbuzz :: Integer -> String
fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
               in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"

このコードを実行すると、きちんとFizzBuzzが表示されます。

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
...

よさそうですね。 ちゃんとFizzBuzzになっています。 それでは、このコードがどういう仕組みで動いているのか調べてみましょう。

前半戦: 演算子 (~>)・Alternative

まずはletのところからです。

fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
               in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"

演算子(~>)を定義しています。 ghciで丁寧に、この演算子の型と動作を見ていきます。

 $ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
Prelude> let (d ~> s) n = s <$ guard (n `mod` d == 0)

<interactive>:2:23: Not in scope: ‘guard’
Prelude> :!hoogle guard | head -n 1
Control.Monad guard :: MonadPlus m => Bool -> m ()
Prelude> import Control.Monad
Prelude Control.Monad> let (d ~> s) n = s <$ guard (n `mod` d == 0)

定義できたので使ってみましょう。 ((<$)がないと言われる場合は、:import Data.Functorして下さい)

Prelude Control.Monad> (3 ~> "Fizz") 1

<interactive>:21:1:
    No instance for (Show (f0 [Char])) arising from a use of ‘print’
    The type variable ‘f0’ is ambiguous
    Note: there are several potential instances:
      instance (Show a, Show b) => Show (Either a b)
        -- Defined in ‘Data.Either’
      instance Show a => Show (Maybe a) -- Defined in ‘GHC.Show’
      instance (Integral a, Show a) => Show (GHC.Real.Ratio a)
        -- Defined in ‘GHC.Real’
      ...plus 15 others
    In a stmt of an interactive GHCi command: print it

型を限定してあげないと表示できないか… なになに、f0が曖昧？うーん、まぁ左のほうでfromMaybeとかやってるしMaybeでしょうね。

Prelude Control.Monad> (3 ~> "Fizz") 1 :: Maybe String
Nothing
Prelude Control.Monad> (3 ~> "Fizz") 3 :: Maybe String
Just "Fizz"
Prelude Control.Monad> map (3 ~> "Fizz") [1..20] :: [Maybe String]
[Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing,Just "Fizz",Nothing,Nothing]

なるほど。 この演算子がやっていることはすぐに理解できますね。3 ~> "Fizz"は、「3の時だけJust "Fizz"になる」関数です。 型を見てみましょう。

Prelude Control.Monad> :t (3 ~> "Fizz")
(3 ~> "Fizz")
  :: (Integral a1, GHC.Base.Alternative f) => a1 -> f [Char]
Prelude Control.Monad> :t ((3 ~> "Fizz") :: Integer -> Maybe String)
((3 ~> "Fizz") :: Integer -> Maybe String) :: Integer -> Maybe String

(3 ~> "Fizz") :: Integer -> Maybe String ですね。 つまり、(~>)の型は

Prelude Control.Monad> :t (~>)
(~>)
  :: (Integral a1, GHC.Base.Alternative f) => a1 -> a -> a1 -> f a
Prelude Control.Monad> :t (~>) :: Integer -> String -> Integer -> Maybe String
(~>) :: Integer -> String -> Integer -> Maybe String
  :: Integer -> String -> Integer -> Maybe String

です。 単に:t 演算子するだけでは、量化されたよく分からない型が表示されますが、 明示的に :: T とつけてやれば、それで型チェックが通るかどうか確かめることができます。

それでは、(~>)の中で型が合っていることを確かめます。

Prelude Control.Monad> :t guard
guard :: GHC.Base.Alternative f => Bool -> f ()
Prelude Control.Monad> :t (<$)
(<$) :: Functor f => a -> f b -> f a

guardはf ()を返します。このfは、Maybeに違いありません。ということは…

Prelude Control.Monad> :t (guard :: Bool -> Maybe ())
(guard :: Bool -> Maybe ()) :: Bool -> Maybe ()
Prelude Control.Monad> :t (<$) :: String -> Maybe () -> Maybe String
(<$) :: String -> Maybe () -> Maybe String
  :: String -> Maybe () -> Maybe String

なるほど。ようやく登場人物たちの型がわかってきました。

guard :: Bool -> Maybe ()
(<$) :: String -> Maybe () -> Maybe String
(~>) :: Integer -> String -> Integer -> Maybe String

ですね。 もう一度、(~>)の定義を見てみましょう。

(~>) :: Integer -> String -> Integer -> Maybe String
(~>) d s n = s <$ guard (n `mod` d == 0)

dとnはInteger、sは"Fizz"のようなStringです。 きちんと型があっていることが目で見て分かりますね。 (分からなかったら丁寧に紙と鉛筆で確認しましょう！コードの下に線でも引いて、ここがどういう型だからちゃんと適用できるな、というふうに確認します。)

あとは(<$)とguardの動作を確認するだけです。 まず、guardから調べましょう。 Hoogleでguardを調べて、ドキュメントに飛びます。

guard :: Alternative f => Bool -> f ()

guard b is pure () if b is True, and empty if b is False.The base package: Control.Monad

Alternative、慣れていないと難しいですね。 今回の場合はguard :: Bool -> Maybe ()、すなわちf = Maybeなので、instance Alternative Maybeを探します。 上のドキュメントを開いていますか？ guardの型定義のApplicativeのところのリンクを踏んで、まずはAlternativeがどういう型クラスだったかを調べます。

class Applicative f => Alternative f where

A monoid on applicative functors.
Minimal complete definition

empty, (<|>)

The base package: Control.Applicative

Monoidですね。emptyはだいたい単位元 (mempty) で(<|>)はだいたいOR (mappend) です (かなりざっくりしたイメージです)。 少し下に、Alternative Maybeのリンクがあります。 左の+をクリックすると、Maybeがどういう風にAlternativeのinstanceなのかが分かります。しかし、なんかよくわからないですね。 そういう時は、Sourceというところをクリックしてソースコードを見ます。

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

なるほど、とても簡潔ですね。 だいたい、NothingはFalseで(<|>)はOR (||)のようなものです。

(||) :: Bool -> Bool -> Bool
False || r = r
l || _ = l

同じです。

さて、guardの説明は、guard b is pure () if b is True, and empty if b is False.でした。emptyの意味はinstance Alternative Maybeの定義からNothingだと分かりましたが、まだpureが何者かがよく分かっていません。 そこで、guardの説明文のpureのリンクを踏むと、Applicativeに飛びます。 Applicativeが何かはとりあえず置いておいて、instance Applicative Maybeを探してソースコードを確認します。

instance Applicative Maybe where
    pure = Just

    Just f  <*> m       = fmap f m
    Nothing <*> _m      = Nothing

    Just _m1 *> m2      = m2
    Nothing  *> _m2     = Nothing

つまり、pureはJustということが分かりました。 まとめると、guardの説明をBool -> Maybe ()に限ると、次のようになります。

guard b is Just () if b is True, and Nothing if b is False.

これが本当か、ghciで確認しましょう。

Prelude Control.Monad> guard True :: Maybe ()
Just ()
Prelude Control.Monad> guard False :: Maybe ()
Nothing

確かに、そうなっていますね。 TrueならJust ()を返し、FalseならNothingを返す関数です。 この文脈において、guardはBool -> Maybe ()の同型写像ですね。

さて、(~>)の中でguardの働きが分かりました。

(~>) :: Integer -> String -> Integer -> Maybe String
(~>) d s n = s <$ guard (n `mod` d == 0)

nがdの倍数なら s <$ Just () となり、倍数でないなら s <$ Nothing となります。 (~>)の動作からすると、(<$)は、右辺がJust ()なら Just s、右辺がNothingならNothingを返すと推察されます。 それでは、(<$)の定義を見てみましょう。 Hoogleで<$を検索し、Functorのドキュメントに飛びます。

(<$) :: a -> f b -> f a

Replace all locations in the input with the same value. The default definition is fmap . const, but this may be overridden with a more efficient version.The base package: Data.Functor

なるほど、手短に言うとfmap . constだということがわかりました。 (<$)の部分を書き換えてみます。

(~>) d s n = (fmap . const) s (guard (n `mod` d == 0))

もうちょい簡約！

(~>) d s n = fmap (const s) (guard (n `mod` d == 0))

うおおおおお！ようやく見慣れた感じになりました。 guardの返り値は、Just ()かNothingなので、

fmap (const s) (Just ()) ==> Just s
fmap (const s) Nothing ==> Nothing

となることが分かります。 この動作が不安という方は、instance Functor Maybeを確認して下さい。

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

fmapはNothingには何もせず、Justで包まれた値には関数を適用してJustで包んで返します。 このMaybe Functorはとても重要なFunctorなので、覚えておきましょう。

以上で、(~>)演算子の動きを完全に追うことができました。

let (d ~> s) n = s <$ guard (n `mod` d == 0)

3 ~> "Fizz" は、3の倍数にはNothingを返し (ここでguardの処理とinstance Applicative Maybe、(<$) = fmap . constとinstance Functor Maybeの定義をパッパッと思い出しながら動作を確認します)、引数が3の倍数ではないならJust "Fizz"を返すような関数です。 だんだんパズルの紐が解けてきました。

• instance Alternative Maybe の guard :: Bool -> Maybe () で倍数かどうかというBool値からMaybe ()に写す。
• Data.Functorの演算子(<$) = fmap . constが使われている。ここでのFunctorのinstanceはMaybe

後半戦: 関数Applicative・関数Monoid

それでは、後半を調べていきましょう。

fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"

演算子が4つありますね。 (.)は頻繁に使われる関数の合成演算子で、(~>)は先程動作を確認した演算子です。 (<*>)はApplicativeの演算子で(<>)はMonoidの演算子、という知識はお持ちの方は多いでしょう。 しかし、普段使う演算子にも関わらず、このコードがなぜうまく動くのか、パッとイメージするのは難しいのではないでしょうか。 それくらい、このコードは技巧に富んでおり、エレガントで、しかもこんなにもエントリーを書いてしまうほど興味深いコードなのです。

とりあえず、fizzbuzz関数をghciで定義しましょう。

Prelude Control.Monad> let fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0) in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"

<interactive>:42:64: Not in scope: ‘fromMaybe’

<interactive>:42:97:
    Not in scope: ‘<>’
Prelude Control.Monad> import Data.Monoid
Prelude Control.Monad Data.Monoid> import Data.Maybe
Prelude Control.Monad Data.Monoid Data.Maybe> let fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0) in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"
Prelude Control.Monad Data.Monoid Data.Maybe> :t fizzbuzz
fizzbuzz :: (Integral a, Show a) => a -> String
Prelude Control.Monad Data.Monoid Data.Maybe> map fizzbuzz [1..20]
["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz","16","17","Fizz","19","Buzz"]

できました。 ちゃんと動いていますね。

まず、演算子が4つもあって、どういうふうに結合しているかが定かではありません。 予想をつけることはできますが、きちんと結合の強さを確認しておきます。

Prelude Control.Monad Data.Monoid Data.Maybe> :i .
(.) :: (b -> c) -> (a -> b) -> a -> c  -- Defined in ‘GHC.Base’
infixr 9 .
Prelude Control.Monad Data.Monoid Data.Maybe> :i <*>
class Functor f => Applicative (f :: * -> *) where
  ...
  (<*>) :: f (a -> b) -> f a -> f b
  ...
    -- Defined in ‘GHC.Base’
infixl 4 <*>
Prelude Control.Monad Data.Monoid Data.Maybe> :i ~>
(~>) ::
  (Integral a1, GHC.Base.Alternative f) => a1 -> a -> a1 -> f a
    -- Defined at <interactive>:12:8
Prelude Control.Monad Data.Monoid Data.Maybe> :i <>
(<>) :: Monoid m => m -> m -> m    -- Defined in ‘Data.Monoid’
infixr 6 <>

このinfixrとかinfixlの後の数字に着目します。 この数字が大きい方が、強く結合します。 強く結合するとは、括弧を省略した時に先に結びつくということです。 例えば、1 + 2 * 3は1 + (2 * 3)となりますが、これは

Prelude> :i +
class Num a where
  (+) :: a -> a -> a
  ...
    -- Defined in ‘GHC.Num’
infixl 6 +
Prelude> :i *
class Num a where
  ...
  (*) :: a -> a -> a
  ...
    -- Defined in ‘GHC.Num’
infixl 7 *

のように、(*)演算子のほうが(+)演算子よりも結合の強さを表す数字が大きいからです。 それでは今出てきた4つの演算子の結合の強さは

infixr 9 .
infixr 6 <>
infixl 4 <*>

あれ、(~>)の結合の強さはいくらなのでしょうか？ 演算子の結合の強さは我々が明示的に指定することができますが、今回の場合は何も書いていません。 書いていない時はどうなるんだったっけと思ってhaskell operator precedence rulesのような適当な単語でググります。 そうすると、The Haskell 98 Report: Declarationsが検索結果トップに出てきます (記事執筆当時) のでリンクを開き、「operator」でページ内検索します。

Any operator lacking a fixity declaration is assumed to be infixl 9 (See Section 3 for more on the use of fixities).The Haskell 98 Report: Declarations

なるほど、何も書かなかったらinfixl 9になると書いてあります。 すなわち、今回のコードでは

infixr 9 .
infixl 9 ~>
infixr 6 <>
infixl 4 <*>

なので、

(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))

のように結合することが、きちんと分かりました。 このFizzBuzzのコード、演算子の結合の強さを味方につけていてとても上手いですね (この演算子の強さを見たときは、本当に「あーうまいなー」と言ってにやにやしてしまいました)。 「きちんと」の意味は、なんとなく動作やコードの見た目から推測したのではなく、根拠を持って結論づけてたということです。 括弧が書かれていない式の中で演算子の挙動を調べるときは、まずは結合の強さを調べるのがポイントです。

さぁ、まず右側の動作から確認していきましょう。

(3 ~> "Fizz") <> (5 ~> "Buzz")

FizzBuzzの出力結果や、3 ~> "Fizz"をこれまで動作と型を確認してきたことから、この関数は

• 15の倍数ならJust "FizzBuzz"
• 3の倍数ならJust "Fizz"
• 5の倍数ならJust "Buzz"
• 上記のどれでもないならNothing

となる関数であることが推測されます。 そして、実際にそうなのです！

Prelude Control.Monad Data.Monoid Data.Maybe> let f = (3 ~> "Fizz") <> (5 ~> "Buzz")
Prelude Control.Monad Data.Monoid Data.Maybe> map f [1..20] :: [Maybe String]
[Nothing,Nothing,Just "Fizz",Nothing,Just "Buzz",Just "Fizz",Nothing,Nothing,Just "Fizz",Just "Buzz",Nothing,Just "Fizz",Nothing,Nothing,Just "FizzBuzz",Nothing,Nothing,Just "Fizz",Nothing,Just "Buzz"]

このように3の倍数の結果と5の倍数の結果を結合しつつ、Maybeを返すというのは、私もcatMaybesを使ったりいろいろごちゃごちゃして悩んで結局わからなかったところです。 一体このコードはどんなトリックを使っているのでしょうか。 ここにはMonoidがうまく使われています。

注目すべきは言うまでもなく、(<>)という演算子にあります。 (3 ~> "Fizz") :: Integer -> Maybe String であることから、今回のコードでは

(<>) :: (Integer -> Maybe String) -> (Integer -> Maybe String) -> (Integer -> Maybe String)

となっているはずです。 そこで、HoogleでMonoidと入力してData.Monoidのドキュメントに飛びます。 Monoidとは、一つの二項演算子と単位元を持つような代数的構造です。群から逆元の存在を抜いたものです。 要するに、((||), False)はMonoidだし ((++), [])も((+), 0)もMonoidです。 Monoidについては以下の記事が初心者にも丁寧に書かれているのでご参考にしてください。 itchyny.hatenablog.com

さて、今回のMonoidのinstanceは何を使っているのでしょうか。 Monoidの定義と(<>)は次のようになっています。

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a

(<>) :: Monoid m => m -> m -> m
(<>) = mappend

現在のコード上の(<>)の型と上のMonoidの定義をじっと見比べると、Monoid (Integer -> Maybe String)を使っていることになります。 こんなの見たことありますか？ええっ、関数Monoid？とびっくりしてData.Monoidのドキュメントを確認しますと、確かにMonoid b => Monoid (a -> b)というものがあります。 Sourceをクリックしてコードを確認すると、次のようになっています。

instance Monoid b => Monoid (a -> b) where
    mempty _ = mempty
    mappend f g x = f x `mappend` g x

なるほど、むずかしい。関数を適用した2つを演算子にかますような関数を返すんですね。mappendの定義は、どことなくControl.Arrowの(&&&)を思い出させます。 これは本当にMonoidになっているのでしょうか。 この定義に従いますと、Monoid (a -> b)のmemptyは\_ -> memptyです (const memptyです)。 これが上記で定義された二項演算子mappendの単位元であることを確認できればOKです。

mappend (\_ -> mempty) g
    ==> \x -> ((\_ -> mempty) x) `mappend` g x
    ==> \x -> mempty `mappend` g x
    ==> \x -> g x                  (Monoid bの性質より)
    ==> g
mappend f (\_ -> mempty)
    ==> \x -> f x `mappend` ((\_ -> mempty) x)
    ==> \x -> f x `mappend` mempty
    ==> \x -> f x                  (Monoid bの性質より)
    ==> f

よって\_ -> memptyは二項演算子mappendの単位元になっていることが確かめられました。 従って、もしbがMonoidならMonoid (a -> b)を作れることが分かりました。

FizzBuzzのコードで使われている(<>)は、

(3 ~> "Fizz") <> (5 ~> "Buzz")

次のような型でした。

(<>) :: (Integer -> Maybe String) -> (Integer -> Maybe String) -> (Integer -> Maybe String)

ですからa = Integer、b = Maybe StringとなるようなMonoid (a -> b)が使われています。 ここでMonoid bとなることが要請されますが、b = Maybe Stringですから、次のようなinstanceが使われます。

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Nothingが単位元、演算子はJustの中身に対して行われます。 つまりこういうことですね。

Prelude Data.Monoid> Just "Fizz" <> Just "Buzz"
Just "FizzBuzz"
Prelude Data.Monoid> Just "Fizz" <> Nothing
Just "Fizz"
Prelude Data.Monoid> Nothing <> Just "Buzz"
Just "Buzz"
Prelude Data.Monoid> Nothing <> Nothing
Nothing

ようやく謎が解けてきました。 もう一度じっとコードを見つめて

(3 ~> "Fizz") <> (5 ~> "Buzz")
instance Monoid b => Monoid (a -> b) where
    mappend f g x = f x `mappend` g x

順番にどの性質を使っているか確認しながら書き換えていきます (勘の良い人は分かったところで止めてよいですよ)。

(3 ~> "Fizz") <> (5 ~> "Buzz")
    ==> (\n -> if n `mod` 3 == 0 then Just "Fizz" else Nothing)
     <> (\n -> if n `mod` 5 == 0 then Just "Buzz" else Nothing)
    ==> \n -> ((if n `mod` 3 == 0 then Just "Fizz" else Nothing)
            <> (if n `mod` 5 == 0 then Just "Buzz" else Nothing))  (関数Monoidのmappend)
    ==> \n -> (if n `mod` 3 == 0 && n `mod` 5 == 0
                  then Just "Fizz" <> Just "Buzz"
                  else if n `mod` 3 == 0 && !(n `mod` 5 == 0)
                          then Just "Fizz" <> Nothing
                          else if !(n `mod` 3 == 0) && n `mod` 5 == 0
                                  then Nothing <> Just "Buzz"
                                  else Nothing <> Nothing)           (ifを展開)
    ==> \n -> (if n `mod` 3 == 0 && n `mod` 5 == 0
                  then Just "FizzBuzz"
                  else if n `mod` 3 == 0 && !(n `mod` 5 == 0)
                          then Just "Fizz"
                          else if !(n `mod` 3 == 0) && n `mod` 5 == 0
                                  then Just "Buzz"
                                  else Nothing)                (Maybe MonoidにおいてNothingは単位元)

やっと、この関数が意図する動作をすることが確認できました (ifは展開せずともイメージできたらよいです)。 少しまとめますと、

• この(<>)は3つのMonoidが使われている
• 一つ目はinstance Monoid [a]: ((++), [])。これのおかげで"Fizz" <> "Buzz"が"FizzBuzz"となる。
• 二つ目はinstance Monoid a => Monoid (Maybe a)。単位元はNothing。Just "Fizz" <> Just "Buzz"がJust "FizzBuzz"になる。Nothingが単位元なので、Just "Fizz" <> Nothing == Just "Fizz"になる。
• 三つ目はinstance Monoid b => Monoid (a -> b)。単位元は\_ -> mempty。3の倍数に対する関数と、5の倍数に対する関数を(<>)で結合して、これらの結果をうまくくっつけるような関数を作ることができる。

かなり巧妙にMonoidが使われていることが分かります。

最後に残ったのは、(<*>)という演算子です。

(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))

演算子の左辺は次のような型ですので、

Prelude Control.Monad Data.Monoid Data.Maybe> :t fromMaybe . show
fromMaybe . show :: Show a => a -> Maybe String -> String
Prelude Control.Monad Data.Monoid Data.Maybe> :t fromMaybe . show :: Integer -> Maybe String -> String
fromMaybe . show :: Integer -> Maybe String -> String
  :: Integer -> Maybe String -> String

この(<*>)演算子の特化された型は次のようになるはずです。

Prelude Control.Monad Data.Monoid Data.Maybe> :t (<*>) :: (Integer -> Maybe String -> String) -> (Integer -> Maybe String) -> Integer -> String
(<*>) :: (Integer -> Maybe String -> String) -> (Integer -> Maybe String) -> Integer -> String
  :: (Integer -> Maybe String -> String)
     -> (Integer -> Maybe String) -> Integer -> String

きちんと型が合いましたね。

さて、(<*>)はApplicativeの演算子ですが、こういうふうな型になるinstanceは何だろうと調べます。 (<*>)の量化された型は

Prelude Control.Monad Data.Monoid Data.Maybe> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

ですので、今回使われている型と睨みながら次のように当てはめてみます。

f (a -> b) === Integer -> Maybe String -> String
f a        === Integer -> Maybe String
f b        === Integer -> String

なんかいやな予感がしますね… 関数かな… Hoogleでこの演算子を調べて、Control.Applicativeのドキュメントに飛びます。 そうすると、instance Applicative ((->) a)というそれっぽいinstanceを見つけたので、慌てて紙と鉛筆を取って型が合うか確かめます。

f (a -> b) === ((->) r) (a -> b) === r -> a -> b === Integer -> Maybe String -> String
f a        === ((->) r) a        === r -> a      === Integer -> Maybe String
f b        === ((->) r) b        === r -> b      === Integer -> String
a === Maybe String
b === String
r === Integer

型は合いますね。 次にこのinstanceのSourceを見に行きます。

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

なんだこれは… f xにg xを適用するとか言っていますよ… つまり今回の場合は

(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))

なので、一生懸命変形していくと

(fromMaybe . show) <*> ((3 ~> "Fizz") <> (5 ~> "Buzz"))
    ==> (\f g x -> f x (g x)) (fromMaybe . show) ((3 ~> "Fizz") <> (5 ~> "Buzz"))
    ==> (\g x -> (fromMaybe . show) x (g x)) ((3 ~> "Fizz") <> (5 ~> "Buzz"))
    ==> \x -> fromMaybe (show x) (((3 ~> "Fizz") <> (5 ~> "Buzz")) x)

なるほど、もう分かりましたね。 最初のfizzbuzzをこの形で書いてみます。

fizzbuzz n = let (d ~> s) n = s <$ guard (n `mod` d == 0)
                 in fromMaybe (show n) (((3 ~> "Fizz") <> (5 ~> "Buzz")) n)

ここまで来たら読めますね！ あとはfromMaybeという関数を知っているかどうかというだけです。 HoogleでfromMaybeを検索し、Data.Maybeのドキュメントに飛びます。

fromMaybe :: a -> Maybe a -> a

The fromMaybe function takes a default value and and Maybe value. If the Maybe is Nothing, it returns the default values; otherwise, it returns the value contained in the Maybe.The base package: Data.Maybe

つまり、デフォルトを指定してJustから安全に取り出す関数というわけです。 念のためにSourceを見に行きます。

fromMaybe     :: a -> Maybe a -> a
fromMaybe d x = case x of {Nothing -> d;Just v  -> v}

コードはとても簡潔で、確かにNothingならデフォルトを返してそうでないならJustを外しています。 今FizzBuzzのコードは

fromMaybe (show n) (((3 ~> "Fizz") <> (5 ~> "Buzz")) n)

となっています。fromMaybeの第二引数がJust "FizzBuzz"またはJust "Fizz"、Just "Buzz"そしてNothingを返すことを思い出すと、Justから取り出しつつNothingのときは数字をそのまま表示するshow nとなっていることが分かります。

• 演算子が出てきたら結合の強さを確認しよう。結合の強さをこちらが指定しなければ、infixl 9になる。
• Monoid三段構え。instance Monoid b => Monoid (a -> b) の単位元は\_ -> mempty。2つの関数の返り値が同じ型でかつMonoidなら、関数たちをうまくmappendすることができる。
• instance Applicative ((->) a) では (<*>) f g x = f x (g x) になっている。

同じコードを書いてみよう

ここまでは、すでにあるコードを読み解く方法を説明してきました。 しかし、これを書いた人は、どのようにこのコードを書いたのでしょうか。 きっと私たちにも理解できる試行錯誤で、同じコードを組み立てることができるはずです。 これを書けるためにはどういうことができればいいか、どういうことは知っていなければいけないかを確かめてみましょう。

まず、fizzbuzz関数はInteger -> Stringを作ることにしましょう (オリジナルはこれをmapしたものです)。

main :: IO ()
main = mapM_ (print . fizzbuzz) [1..100]

fizzbuzz = ...

後でprintはputStrLnにしますが、コードを書いている途中は面倒なので最初はprintと書いておきます。 まず簡単なものを書いてみます。

fizzbuzz n
  | n `mod` 15 == 0 = "FizzBuzz"
  | n `mod` 3 == 0 = "Fizz"
  | n `mod` 5 == 0 = "Buzz"
  | otherwise = show n

実行したら次のようになります。

"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
"8"
"Fizz"
"Buzz"
"11"
"Fizz"
"13"
"14"
"FizzBuzz"
"16"
"17"
"Fizz"
"19"
"Buzz"
...

動作は大丈夫です。

さて、何度もmodと書いているので、関数にしたいですね。 また、mod 3の計算結果とmod 5の計算結果を何とかしてまとめたいです。 3の倍数ならJust 文字列を返し、そうでないならNothingを返す、そんな関数を作ってみましょう。

fizzbuzz n = (show n, f n 3 "Fizz", f n 5 "Buzz")

f n d s = if n `mod` d == 0 then Just s else Nothing

実行してみます。

("1",Nothing,Nothing)
("2",Nothing,Nothing)
("3",Just "Fizz",Nothing)
("4",Nothing,Nothing)
("5",Nothing,Just "Buzz")
("6",Just "Fizz",Nothing)
("7",Nothing,Nothing)
("8",Nothing,Nothing)
("9",Just "Fizz",Nothing)
("10",Nothing,Just "Buzz")
("11",Nothing,Nothing)
("12",Just "Fizz",Nothing)
("13",Nothing,Nothing)
("14",Nothing,Nothing)
("15",Just "Fizz",Just "Buzz")
("16",Nothing,Nothing)
("17",Nothing,Nothing)
("18",Just "Fizz",Nothing)
("19",Nothing,Nothing)
("20",Nothing,Just "Buzz")
...

ちゃんとできていますね。 modが一箇所になっていい感じです。

さぁこの結果を集約していきましょう。 まず3の倍数かつ5の倍数、すなわち

("15",Just "Fizz",Just "Buzz")

の二つ目と三つ目をJust "FizzBuzz"にしたいと考えます。 どちらか一方がNothingだったら他方を採用する… これはMonoidだと気が付きます。 Monoidの演算子(<>)を使えることを確認します。

 $ ghci
GHCi, version 7.10.2: http://www.haskell.org/ghc/  :? for help
Prelude> import Data.Monoid
Prelude Data.Monoid> Just "Fizz" <> Just "Buzz"
Just "FizzBuzz"
Prelude Data.Monoid> Just "Fizz" <> Nothing
Just "Fizz"
Prelude Data.Monoid> Nothing <> Just "Buzz"
Just "Buzz"
Prelude Data.Monoid> Nothing <> Nothing
Nothing

いけそうですね！ 早速この演算子を使ってみます。

fizzbuzz n = (show n, f n 3 "Fizz" <> f n 5 "Buzz")

("1",Nothing)
("2",Nothing)
("3",Just "Fizz")
("4",Nothing)
("5",Just "Buzz")
("6",Just "Fizz")
("7",Nothing)
("8",Nothing)
("9",Just "Fizz")
("10",Just "Buzz")
("11",Nothing)
("12",Just "Fizz")
("13",Nothing)
("14",Nothing)
("15",Just "FizzBuzz")
("16",Nothing)
("17",Nothing)
("18",Just "Fizz")
("19",Nothing)
("20",Just "Buzz")
...

うまくいってます！ そして、右側がNothingの時にのみ左側を採用したら良さそうです。 Justから中身を取り出しつつ安全な… fromMaybeですね！

fizzbuzz n = fromMaybe (show n) (f n 3 "Fizz" <> f n 5 "Buzz")

"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
"8"
"Fizz"
"Buzz"
"11"
"Fizz"
"13"
"14"
"FizzBuzz"
"16"
"17"
"Fizz"
"19"
"Buzz"
...

やったー！ うまくいきました。

ここからは、更にコードを難読化洗練させていきます。

f n d s = if n `mod` d == 0 then Just s else Nothing

まずif .. then .. elseを辞めたいですね。 BoolからMaybe Stringになるような関数、そんなものありましたっけ。 勘で Bool -> Maybe String、いや Bool -> Maybe a のほうが良さそうかなと思ってHoogleで検索します。 Justも違う、returnも違う… 第一引数がBoolのやつは… fromBool違う… お、guard？これなんだっけ…

guard :: MonadPlus m => Bool -> m ()

と思って、定義を見に行きます (今回たまたまMaybe aでヒットしてしまいましたが、思うように見つからないときはどんどん一般化させてBool -> m aのように検索します)。

guard :: Alternative f => Bool -> f ()

guard b is pure () if b is True, and empty if b is False.The base package: Control.Monad

instance Applicative Maybeを調べつつ、ghciで確認してみます。

Prelude Control.Monad> guard True :: Maybe ()
Just ()
Prelude Control.Monad> guard False :: Maybe ()
Nothing

なるほど。

f n d s = if guard (n `mod` d == 0) == Just () then Just s else Nothing

Just ()ならJust s、NothingならNothingなので、fmapだとすぐに気が付きます。

f n d s = fmap (const s) (guard (n `mod` d == 0))

"1"
"2"
"Fizz"
"4"
"Buzz"
"Fizz"
"7"
...

guardを使ってifを消せました！ そして、constしてfmap… fmap . const… (<$)ですね！ これは流石に知っておかないと気がつけません。 少し動作を確認しておきましょう。

Prelude> 1 <$ Just 0
Just 1
Prelude> 1 <$ Nothing
Nothing
Prelude> 1 <$ [1..5]
[1,1,1,1,1]
Prelude> 1 <$ Left 0
Left 0
Prelude> 1 <$ Right 0
Right 1

ふむふむ、なるほど。 Functor素晴らしいですね。 この演算子を使うと、次のようになりました。

f n d s = s <$ guard (n `mod` d == 0)

できましたね！

次は、fizzbuzz関数本体をpoint-freeスタイルに変形しましょう。

fizzbuzz n = fromMaybe (show n) (f n 3 "Fizz" <> f n 5 "Buzz")

引数のnを消したいです。 まず、後ろ側のところでnが第1引数に来ているのが難しいので、最後に来るようにfを変更します

fizzbuzz n = fromMaybe (show n) (f 3 "Fizz" n <> f 5 "Buzz" n)

f :: Integer -> String -> Integer -> Maybe String
f d s n = s <$ guard (n `mod` d == 0)

fの型も書いてみました。f 3 "Fizz"はInteger -> Maybe Stringですね。 ここで、関数のMonoidを思い出します。これもやはり知っていないとできませんね。

instance Monoid b => Monoid (a -> b) where
    mempty _ = mempty
    mappend f g x = f x `mappend` g x

まさに f 3 "Fizz" n <> f 5 "Buzz" n の部分がこの形になっています！ よって、次のようにも書けます。

fizzbuzz n = fromMaybe (show n) ((f 3 "Fizz" <> f 5 "Buzz") n)

show nのnが深いところにあるので、少し変形します。

fizzbuzz n = ((fromMaybe . show) n) ((f 3 "Fizz" <> f 5 "Buzz") n)

nが二回使われています。f n (g n)の形です。 うーんと考えて、Applicative ((->) a)やMonad ((->) r)などを調べます。

instance Applicative ((->) a) where
    pure = const
    (<*>) f g x = f x (g x)

instance Monad ((->) r) where
    return = const
    f >>= k = \r -> k (f r) r

今回はApplicativeの方ですね。

fizzbuzz n = ((fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")) n

最後にη変換です！

fizzbuzz = (fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")

やりました！point-freeスタイルになりました！ 関数fをfizzbuzzの中に入れて

fizzbuzz = let f d s n = s <$ guard (n `mod` d == 0)
               in (fromMaybe . show) <*> (f 3 "Fizz" <> f 5 "Buzz")

それっぽい演算子に書き換えつつ、恐る恐る括弧を外し、printをputStrLnにしたら完成です！

main :: IO ()
main = mapM_ (putStrLn . fizzbuzz) [1..100]

fizzbuzz :: Integer -> String
fizzbuzz = let (d ~> s) n = s <$ guard (n `mod` d == 0)
               in fromMaybe . show <*> 3 ~> "Fizz" <> 5 ~> "Buzz"

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
...

やったー！！！ なんとか元のコードを再構築することができました！

気合と根性といくつかの知識が必要ですね。

• とにかくがんばる。とにかくpoint-freeスタイル。
• 困ってもArrowに頼りすぎない。とりあえずMonadとかApplicativeなどからそれっぽいのを探す。((->) a)に注目しよう。
• Monoid便利。超便利。便利すぎる。

まとめ

Monoid・Functor・Applicative・Alternative、そしてMonad。 型クラスはHaskellの特徴的な機能であり、とても便利なものです。 型クラスは我々のコードを量化し、またコードを書くときにはどういう構造のどういう性質を使っているかを意識させてくれます。 私はHaskellの様々な機能に魅了されて使っていますが、型クラスの機能がもしなかったらここまで惹かれることはなかったかもしれません。

point-freeスタイルは常にいいものではありません。 時にはコードを難解にし、読めないものにしてしまいます。 私は一時期Arrowのcombinatorを使ったpoint-freeスタイルに没頭した時期がありましたが、しばらくして熱が冷めてしまい、残ったのは全く読めない難解なコードばかりでした。

しかし、もちろん積極的に使うべきケースだって多々あります。 \x -> f (g x)よりもf . gのほうが読みやすく、「2つの関数を順番に適用する」という意味もはっきりしています。 また、do { a <- m1; b <- m2; return (f a b) }よりも f <$> m1 <*> m2 のほうが、本当に何をやりたいのかということに集中してコードを書くことができます。 いちいち case ... of を使っていたところを、 Alternative Maybe の (<|>) でサラッと書けたときは快感です。 型クラスのメソッドを意味のある用途で使い、コードが簡潔になるならば、それは推奨されてよいでしょう。

複雑なコードを解読していくのは、とても楽しいパズルです。 時には便利なinstanceを発見したり、型クラスへの理解が更に深まることもあります。 抽象的な高階関数をここまで自在に扱える言語は他にはないと思います。 技巧的すぎて実際には書かないし役に立たないなどと言わず、たまには頭の体操と思って仕組みを調べてみてはいかがでしょうか。