PureScript by Example 4 章の前半を読む

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

- ← 9 日目『 [PureScript IDE (Visual Studio Code 拡張) の紹介 - Qiita][2016-12-09] 』
- → 11 日目『 [PureScript by Example 4 章の後半を読む - Qiita][2016-12-11] 』

## 概要

[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.1

4 章は再帰関数を扱うようだ。 `map` `fold` `filter` `concatMap` は少なくとも登場するらしい。

例としては仮想のファイルシステムを扱う。ツリー構造を再帰かな……。

## PureScript 4.2

今回のプロジェクトでは次のものをインストールするらしい。また `Data.Path` という使うだけのモジュールが必要らしい。[資料を置いてあるリポジトリ][purescript-book-4]を参照すると良い。なぜ、いままでも使ってきた `purescript-console` をいまさらと思う。

- `purescript-maybe`
- `purescript-arrays`
- `purescript-strings`
- `purescript-foldable-traversable`
- `purescript-console`

Pursuit:

- [purescript-maybe - Pursuit][pursuit-maybe]
- [purescript-arrays - Pursuit][pursuit-arrays]
- [purescript-strings - Pursuit][pursuit-strings]
- [purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable]
- [purescript-console - Pursuit][pursuit-console]

## PureScript by Example 4.3

再帰は重要。可変な状態を減らすことを助ける。なるほど。

再帰は分割統治と関係がある。ふむ。

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

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
```

それぞれの場合ごとに考えてつくっていけるってことかな。

## PureScript by Example 4.4

配列の再帰。 `length` の例。 `null` で `Array` が空かを判定して、そうでなければ `tail` に `length` で……という感じ。ふむり。

```
module Main where

import Prelude

import Data.Array (null)
import Data.Array.Partial (tail)
import Partial.Unsafe (unsafePartial)

length :: forall a. Array a -> Int
length arr =
  if null arr
    then 0
    else 1 + length (unsafePartial tail arr)
```

Pursuit:

- [null - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-null]
- [tail - Data.Array.Partial - purescript-arrays - Pursuit][pursuit-arrays-tail]
- [unsafePartial - Partial.Unsafe - purescript-partial - Pursuit][pursuit-partial-unsafe-partial]

そういえば `if ... then ... else` は初出なのかな。

`unsafePartial` は説明がないので、またそのうち出てくるはず。あと直接の依存関係にないのだけど、たぶん、`purescript-arrays` からの間接的な依存関係に入っているはず……。

## PureScript by Example 4.5

`map`

```
> import Prelude (map)
> map (\n -> n + 1) [1, 2, 3, 4, 5]
[2,3,4,5,6]

> :type map
forall a b f. (Functor f) => (a -> b) -> f a -> f b
```

JavaScript の `Array.prototype.map` と動きは似ているけど、こちらは `Prelude` に入っているし、`Array` 以外でも (`Functor` なら) 使える。その説明は出ていないけど、そのうち出てくるはず。過去に `AddressBook` のところで `Maybe` が出てきたときに、使っていた気もする。

あと `<$>` は `map` の operator alias (これも書いたはず) 。

Pursuit:

- [map - Prelude - purescript-prelude - Pursuit][pursuit-prelude-map]
- [<$> - Prelude - purescript-prelude - Pursuit][pursuit-prelude-map-op]

## PureScript by Example 4.6

Infix Operator 。あれ、前もやったような……。中置演算子や中置関数適用 (infix function application) か。

```
> (\n -> n + 1) `map` [1, 2, 3, 4, 5]
[2, 3, 4, 5, 6]

> (\n -> n + 1) <$> [1, 2, 3, 4, 5]
[2, 3, 4, 5, 6]

> :type map
forall a b f. (Functor f) => (a -> b) -> f a -> f b
```

言ってるそばから `<$>` や `:type map` が出てきた。

演算子を関数的に使う方法も前回書いたような気がする。

```
> import Prelude (map, show, (<$>))
> show <$> [1, 2, 3, 4, 5]
["1","2","3","4","5"]

> (<$>) show [1, 2, 3, 4, 5]
["1","2","3","4","5"]
```

`range` の operator alias である `(..)` を使ってみるらしい。

```
> import Data.Array ((..))
> 1 .. 5
[1,2,3,4,5]

> import Prelude (show, (<$>))
> show <$> (1 .. 5)
["1","2","3","4","5"]
```

Pursuit:

- [(..) - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-range-op]
- [range - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-range]

`(..)` の定義は次のようにするらしい。

```
infix 8 range as ..
```

ソースコードを見てみた。確かに。 https://github.com/purescript/purescript-arrays/blob/v3.1.0/src/Data/Array.purs#L161

## PureScript by Example 4.7

`filter` 。 JavaScript の `Array.prototype.filter` はおなじみのはずなので、特に説明は不要かな。

```
> import Prelude (mod, (==))
> import Data.Array (filter, (..))
> filter (\n -> n `mod` 2 == 0) (1 .. 10)
[2,4,6,8,10]

> :t filter
forall a. (a -> Boolean) -> Array a -> Array a
```

Pursuit:

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

## PureScript by Example 4.8

`concat` 。 JavaScript の `Array.prototype.concat` とは違い、`flatten` っぽい動き。

```
> import Data.Array (concat)
> :t concat
forall a. Array (Array a) -> Array a

> concat [[1, 2, 3], [4, 5], [6]]
[1,2,3,4,5,6]
```

Pursuit:

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

`concatMap` 。

```
> import Prelude ((*))
> import Data.Array (concatMap, (..))

> :t concatMap
forall a b. (a -> Array b) -> Array a -> Array b

> concatMap (\n -> [n, n * n]) (1 .. 5)
[1,1,2,4,3,9,4,16,5,25]
```

`map` して `concat` する感じ。語順のイメージは↓の `concat $ map ...` からだと思う。

```
> import Prelude (map, ($))
> concat (map (\n -> [n, n * n]) (1 .. 5))
[1,1,2,4,3,9,4,16,5,25]

> concat $ map (\n -> [n, n * n]) (1 .. 5)
[1,1,2,4,3,9,4,16,5,25]
```

Pursuit:

- [concatMap - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-concat-map]

## PureScript by Example 4.9

配列内包 (array comprehensions) 。因数を見つける関数を書くようだ。

まずは組み合わせを列挙するらしい。

```
> let pairs n = concatMap (\i -> 1 .. n) (1 .. n)
> pairs 3
[1,2,3,1,2,3,1,2,3]

> let pairs' n = concatMap (\i -> map (\j -> [i, j]) (1 .. n)) (1 .. n)
> pairs' 3
[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]

> let pairs'' n = concatMap (\i -> map (\j -> [i, j]) (i .. n)) (1 .. n)
> pairs' 3
[[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
```

```
> import Prelude (map, (==))
> import Data.Array (concatMap, filter, (..))
> import Data.Foldable (product)
> let pairs'' n = concatMap (\i -> map (\j -> [i, j]) (i .. n)) (1 .. n)
> let factors n = filter (\pair -> product pair == n) (pairs'' n)
> factors 10
[[1,10],[2,5]]
```

`product` はソースによると `foldl (*) one` 。`one` は `Semiring` のもの。

https://github.com/purescript/purescript-foldable-traversable/blob/v2.0.0/src/Data/Foldable.purs#L255

Pursuit:

- [product - Data.Foldable - purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable-product]
- [one - Data.Semiring - purescript-prelude - Pursuit][pursuit-prelude-one]

## まとめ

再帰関数。個人的には特にはまることなく、とんとんと進んだ。次は後半。

## 参考

- [purescript-maybe - Pursuit][pursuit-maybe]
- [purescript-arrays - Pursuit][pursuit-arrays]
- [purescript-strings - Pursuit][pursuit-strings]
- [purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable]
- [purescript-console - Pursuit][pursuit-console]
- [null - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-null]
- [tail - Data.Array.Partial - purescript-arrays - Pursuit][pursuit-arrays-tail]
- [unsafePartial - Partial.Unsafe - purescript-partial - Pursuit][pursuit-partial-unsafe-partial]
- [map - Prelude - purescript-prelude - Pursuit][pursuit-prelude-map]
- [(<$>) - Prelude - purescript-prelude - Pursuit][pursuit-prelude-map-op]
- [(..) - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-range-op]
- [range - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-range]
- [filter - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-filter]
- [concat - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-concat]
- [concatMap - Data.Array - purescript-arrays - Pursuit][pursuit-arrays-concat-map]
- [product - Data.Foldable - purescript-foldable-traversable - Pursuit][pursuit-foldable-traversable-product]
- [one - Data.Semiring - purescript-prelude - Pursuit][pursuit-prelude-one]

[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
[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/

[pursuit-prelude-one]: https://pursuit.purescript.org/packages/purescript-prelude/2.1.0/docs/Data.Semiring#v:one
[pursuit-foldable-traversable-product]: https://pursuit.purescript.org/packages/purescript-foldable-traversable/2.0.0/docs/Data.Foldable#v:product
[pursuit-arrays-concat]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:concat
[pursuit-arrays-concat-map]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:concatMap
[pursuit-arrays-filter]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:filter
[pursuit-arrays-range]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:range
[pursuit-arrays-null]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:null
[pursuit-arrays-range-op]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array#v:(..)
[pursuit-arrays-tail]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0/docs/Data.Array.Partial#v:tail
[pursuit-arrays]: https://pursuit.purescript.org/packages/purescript-arrays/3.1.0
[pursuit-console]: https://pursuit.purescript.org/packages/purescript-console/2.0.0
[pursuit-foldable-traversable]: https://pursuit.purescript.org/packages/purescript-foldable-traversable/2.0.0
[pursuit-maybe]: https://pursuit.purescript.org/packages/purescript-maybe/2.0.1
[pursuit-partial-unsafe-partial]: https://pursuit.purescript.org/packages/purescript-partial/1.1.2/docs/Partial.Unsafe#v:unsafePartial
[pursuit-prelude-map]: https://pursuit.purescript.org/packages/purescript-prelude/2.1.0/docs/Data.Functor#v:map
[pursuit-prelude-map-op]: https://pursuit.purescript.org/packages/purescript-prelude/2.1.0/docs/Data.Functor#v:(%3C$%3E)
[pursuit-strings]: https://pursuit.purescript.org/packages/purescript-strings/2.0.2
[purescript-book-4]: https://github.com/paf31/purescript-book/tree/8ad7d2af75ad4c795d5075018e9ee45005799e6f/exercises/chapter4