PureScript by Example 4 章の後半を読む

この記事は [(bouzuya) PureScript Advent Calendar 2016](http://www.adventar.org/calendars/1494) の 11 日目。 (bouzuya) PureScript Advent Calendar 2016 は bouzuya の PureScript 学習の記録だ。

- ← 10 日目『 [PureScript by Example 4 章の前半を読む - Qiita][2016-12-10] 』
- → 12 日目『 [PureScript by Example 4 章の終わりと 5 章の冒頭を読む - Qiita][2016-12-12] 』

## 概要

[PureScript by Example][purescript-by-example] と [PureScript Language Guide][language-guide] を見ながら進めていく。今日は [PureScript by Example の 4 章][purescript-by-example-4] の後半 (例以外) を読む。

※注意事項: 英語と日本語訳では大きな差異がある。`0.10.x` に対応している英語の側で進める。

- [PureScript by Example][purescript-by-example] 2016-12-05 時点で 0.10.x 向け
- [実例による PureScript][purescript-by-example-ja] 2016-12-05 時点で 0.7 向け
- [PureScript Language Guide][language-guide] 対象バージョン不明

## PureScript 4.10

`do` 記法 (do notation) 。

`map` と `concatMap` は一般的には `map` と `bind` (`Array` における `bind` は `concatMap`) で、`map` と `bind` のための記法が用意されている。それが `do` 記法。

`map` と `concatMap` が配列の内包表記 (array comprehensions) なら `do` 記法によるものはモナドの内包表記 (monad comprehensions) になる。

ふむ。昨日の `factors` を書き換える例がある。

これが昨日の例を整理したもの。

```
module Main where

import Prelude (map, (==))
import Data.Array (concatMap, filter, (..))
import Data.Foldable (product)

pairs :: Int -> Array (Array Int)
pairs n = concatMap (\i -> (map (\j -> [i, j]) (i .. n))) (1 .. n)

factors :: Int -> Array (Array Int)
factors n = filter (\pair -> product pair == n) (pairs n)
```

これが今日の (`do` 記法の) 例を整理したもの。

```
module Main where

import Prelude (pure, bind, (==), ($))
import Data.Array (filter, (..))
import Data.Foldable (product)

pairs :: Int -> Array (Array Int)
pairs n = do
  i <- 1 .. n
  j <- i .. n
  pure [i, j]

factors :: Int -> Array (Array Int)
factors n = filter (\pair -> product pair == n) (pairs n)
```

`pairs` を `do` 記法を使って書き換えている。

`1 .. n` し、それぞれの要素に対して `i .. n` し、それぞれの要素に対して、`pure [i, j]` したものを `concatMap` する。`concatMap` より `do` 記法のほうが処理の流れを意識しやすそうだ。

ちなみに `Array` の `pure` は `pure x = [x]` 。[purescript/purescript-prelude の Applicative Array][applicative-array] を見れば分かる。

```
> import Prelude (pure)
> (pure [1,2]) :: Array (Array Int)
[[1,2]]
```

`Array` は `Functor` のインスタンスだから `map` が使えるし、 `Applicative` のインスタンスだから `pure` が使えるし、 `Bind` のインスタンスだから `bind` が使える。それぞれ [Functor Array][functor-array], [Applicative Array][applicative-array], [Bind Array][bind-array] を見れば分かる。

あと `do` 記法の Language Guide にはいろいろ書いてあるのだけど、これもまた後で出てくるはずなのでスルー。

Pursuit:

- [pure - Prelude - purescript-prelude - Pursuit][pursuit-prelude-pure]

Language Guide:

- [Do notation - Language Guide][language-guide-do-notation]

## PureScript 4.11

`guard` を使う。 `purescript-control` パッケージの `Control.MonadZero` モジュールにある。

```
> import Control.MonadZero (guard)
> :t guard
forall m. (MonadZero m) => Boolean -> m Unit
```

Pursuit:

- [guard - Control.MonadZero - purescript-control - Pursuit][pursuit-control-guard]

ソースコードを見ると引数が `true` なら `pure unit` そうでなければ `empty` みたいだ。

https://github.com/purescript/purescript-control/blob/v2.0.0/src/Control/MonadZero.purs#L51-L51

```
guard :: forall m. MonadZero m => Boolean -> m Unit
guard true = pure unit
guard false = empty
```

Pursuit:

- [unit - Data.Unit - purescript-prelude - Pursuit][pursuit-prelude-unit]
- [empty - Control.Plus - purescript-control - Pursuit][pursuit-control-empty]

で、この `guard` を `filter` のかわりに使う、と。

```
module Main where

import Control.MonadZero (guard)
import Data.Array ((..))
import Prelude (($), (*), (==), bind, pure)

factors :: Int -> Array (Array Int)
factors n = do
  i <- 1 .. n
  j <- i .. n
  guard $ i * j == n
  pure [i, j]
```

あと `(length $ guard true) == 1` `(length $ guard false) == 0` という例が載っているけど、ぱっと見では分かりづらいと感じる。

`guard true` は `pure unit` 。 `Array` で考えると `[unit]` なので、 `length $ guard true` は `1` になる。

`guard false` は `empty` 。 `Array` で考えると `[]` なので、 `length $ guard false` は `0` になる。

## PureScript by Example 4.12

`foldl` と `foldr` 。JavaScript で言うと `Array.prototype.reduce` 。

Pursuit:

- [foldl - Data.Foldable - purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable-foldl]
- [foldr - Data.Foldable - purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable-foldr]

```
> import Data.Foldable (foldl, foldr)
> :t foldl
forall a b f. (Foldable f) => (b -> a -> b) -> b -> f a -> b

> :t foldr
forall a b f. (Foldable f) => (a -> b -> b) -> b -> f a -> b
```

`Array` は `Foldable` なので `f` を `Array` で読みかえれば良い。

`foldl` / `foldr` は特に新しい要素もないような……。JavaScript との違いで言えば、`index` などは渡されないことと `callback` の引数の順序に注意するくらいか。

```
> import Prelude ((<>), show)
> import Data.Foldable (foldl, foldr)
> foldl (\acc n -> acc <> show n) "" [1,2,3,4,5]
"12345"

> foldr (\n acc -> acc <> show n) "" [1,2,3,4,5]
"54321"
```

`foldl` と `foldr` のイメージが書いてあるけど、左右の違いがピンと来ない例だ。

```
-- foldl のイメージ
((((("" <> show 1) <> show 2) <> show 3) <> show 4) <> show 5)
-- foldr のイメージ
((((("" <> show 5) <> show 4) <> show 3) <> show 2) <> show 1)
```

## PureScript by Example 4.13

末尾再帰 (tail recursion) 。 PureScript は末尾再帰を `while` に変換するらしい。ふむ。一応は例を転載しておく。せっかくなので変換結果も。

```
module Main where

import Prelude ((-), (*))

fact :: Int -> Int -> Int
fact 0 acc = acc
fact n acc = fact (n - 1) (acc * n)
```

```
"use strict";
var Prelude = require("../Prelude");
var Data_Ring = require("../Data.Ring");
var Data_Semiring = require("../Data.Semiring");
var fact = function (__copy_v) {
    return function (__copy_acc) {
        var v = __copy_v;
        var acc = __copy_acc;
        tco: while (true) {
            if (v === 0) {
                return acc;
            };
            var __tco_v = v - 1;
            var __tco_acc = acc * v | 0;
            v = __tco_v;
            acc = __tco_acc;
            continue tco;
        };
    };
};
module.exports = {
    fact: fact
};
```

確かに `while` 。

こういうときは [`try.purescript.org`][try-purescript] で試すと手軽だ。

## PureScript by Example 4.14

アキュムレーターパラメーター (accumulator parameter) 。末尾再帰が出てきたら、出て来るよね。次の呼び出しに渡す計算結果をアキュムレーターって呼んでる、って認識。ここまでの蓄積・累積したものだから accumulator 。

`reverse` の例があるけど、 `length` のほうが分かりやすくないかな……。(`snoc` を調べるのがめんどうなわけではない)

```
module Main where

import Prelude ((+), ($))
import Partial.Unsafe (unsafePartial)
import Data.Array.Partial (tail)

-- 普通に再帰
length' :: forall a. Array a -> Int
length' [] = 0
length' xs = 1 + length' (unsafePartial tail xs)

-- 末尾再帰
length'' :: forall a. Array a -> Int
length'' xs = f 0 xs
  where
    f acc [] = acc
    f acc xs = f (acc + 1) (unsafePartial tail xs)
```

Pursuit:

- [snoc - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-snoc]

## PureScript by Example 4.15

再帰よりも畳み込みを選べ、と。そりゃそうだ。ぼくは先に `foldl` が出て来たことに違和感を覚える。`foldl` / `foldr` の引数の一方はまさにアキュムレーターなわけだし……。

## まとめ

くたびれたのでここで区切り。

再帰関数のことは他の言語でも使える知識なので良さそう。PureScript に関して言うと末尾再帰の最適化処理が入っていることと、`do` 記法の紹介が大きそう。 `do` 記法はまた出て来るはずだ。

## 参考

- [PureScript by Example][purescript-by-example]
- [実例による PureScript][purescript-by-example-ja]
- [Language Guide][language-guide]
- [Language Guide - Do notation][language-guide-do-notation]
- [Pursuit - pure - Prelude - purescript-prelude][pursuit-prelude-pure]
- [Pursuit - unit - Data.Unit - purescript-prelude][pursuit-prelude-unit]
- [Pursuit - guard - Control.MonadZero - purescript-control][pursuit-control-guard]
- [Pursuit - empty - Control.Plus - purescript-control][pursuit-control-empty]
- [Pursuit - foldl - Data.Foldable - purescript-foldable-traversable][pursuit-foldable-traversable-foldl]
- [Pursuit - foldr - Data.Foldable - purescript-foldable-traversable][pursuit-foldable-traversable-foldr]
- [Pursuit - snoc - Data.Array - purescript-arrays][pursuit-arrays-snoc]

## 次回以降の TODO

- PureScript by Example & PureScript Language Guide を読み進める
- `Array` 以外での `do` 記法
- Tagged Unions / Newtype
- `psc-package`
- PureScript IDE の導入
- [24 Days of PureScript, 2016][paf31/24-days-of-purescript-2016]
- [24 Days of PureScript, 2014](https://gist.github.com/paf31/8e9177b20ee920480fbc)
- 某氏の記事の紹介
- [github.com/purescript](https://github.com/purescript/) のコードを読む
- [github.com/purescript-node](https://github.com/purescript-node) のコードを読む
- [github.com/purescript-contrib](https://github.com/purescript-contrib) のコードを読む


[paf31/24-days-of-purescript-2016]: https://github.com/paf31/24-days-of-purescript-2016
[2016-12-01]: http://qiita.com/bouzuya/items/a5be85ec3e496e5bf436
[2016-12-02]: http://qiita.com/bouzuya/items/806335ea74ead0e33d95
[2016-12-03]: http://qiita.com/bouzuya/items/86cc9aaaddcc1aa790cf
[2016-12-04]: http://qiita.com/bouzuya/items/b2b80c22c50d0c1e739c
[2016-12-05]: http://qiita.com/bouzuya/items/f19ee0b86e9aec3f0afa
[2016-12-06]: http://qiita.com/bouzuya/items/4694ac25f68931115319
[2016-12-07]: http://qiita.com/bouzuya/items/62c6ad30ecba3c68a7a3
[2016-12-08]: http://qiita.com/bouzuya/items/7224535dd053c41748ed
[2016-12-09]: http://qiita.com/bouzuya/items/868eafc19b96619c025a
[2016-12-10]: http://qiita.com/bouzuya/items/1a54ba3702f9818527a5
[2016-12-11]: http://qiita.com/bouzuya/items/ab2bc2d19461203f1ee5
[2016-12-12]: http://qiita.com/bouzuya/items/c42ddb14477716de1dcf
[purescript-by-example]: https://leanpub.com/purescript/read
[purescript/purescript]: https://github.com/purescript/purescript
[pursuit]: https://pursuit.purescript.org/
[language-guide]: https://github.com/purescript/purescript/wiki/Language-Guide
[purescript-by-example-4]: https://leanpub.com/purescript/read#leanpub-auto-recursion-maps-and-folds
[purescript-by-example-ja]: http://hiruberuto.bitbucket.org/purescript/

[applicative-array]: https://github.com/purescript/purescript-prelude/blob/v2.1.0/src/Control/Applicative.purs#L38
[bind-array]: https://github.com/purescript/purescript-prelude/blob/v2.1.0/src/Control/Bind.purs#L64
[functor-array]: https://github.com/purescript/purescript-prelude/blob/v2.1.0/src/Data/Functor.purs#L42
[language-guide-do-notation]: https://github.com/purescript/purescript/wiki/Language-Guide#do-notation
[pursuit-arrays-snoc]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:snoc
[pursuit-control-empty]: https://pursuit.purescript.org/packages/purescript-control/2.0.0/docs/Control.Plus#v:empty
[pursuit-control-guard]: https://pursuit.purescript.org/packages/purescript-control/2.0.0/docs/Control.MonadZero#v:guard
[pursuit-foldable-traversable-foldl]: https://pursuit.purescript.org/packages/purescript-foldable-traversable/2.0.0/docs/Data.Foldable#v:foldl
[pursuit-foldable-traversable-foldr]: https://pursuit.purescript.org/packages/purescript-foldable-traversable/2.0.0/docs/Data.Foldable#v:foldr
[pursuit-prelude-pure]: https://pursuit.purescript.org/packages/purescript-prelude/2.1.0/docs/Control.Applicative#v:pure
[pursuit-prelude-unit]: https://pursuit.purescript.org/packages/purescript-prelude/2.1.0/docs/Data.Unit#t:Unit
[try-purescript]: http://try.purescript.org/