この記事は (bouzuya) PureScript Advent Calendar 2016 の 11 日目。 (bouzuya) PureScript Advent Calendar 2016 は bouzuya の PureScript 学習の記録だ。
- ← 10 日目『 PureScript by Example 4 章の前半を読む - Qiita 』
- → 12 日目『 PureScript by Example 4 章の終わりと 5 章の冒頭を読む - Qiita 』
概要
PureScript by Example と PureScript Language Guide を見ながら進めていく。今日は PureScript by Example の 4 章 の後半 (例以外) を読む。
※注意事項: 英語と日本語訳では大きな差異がある。0.10.x に対応している英語の側で進める。
- PureScript by Example 2016-12-05 時点で 0.10.x 向け
- 実例による PureScript 2016-12-05 時点で 0.7 向け
- PureScript 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 を見れば分かる。
> import Prelude (pure)
> (pure [1,2]) :: Array (Array Int)
[[1,2]]
Array は Functor のインスタンスだから map が使えるし、 Applicative のインスタンスだから pure が使えるし、 Bind のインスタンスだから bind が使える。それぞれ Functor Array, Applicative Array, Bind Array を見れば分かる。
あと do 記法の Language Guide にはいろいろ書いてあるのだけど、これもまた後で出てくるはずなのでスルー。
Pursuit:
Language Guide:
PureScript 4.11
guard を使う。 purescript-control パッケージの Control.MonadZero モジュールにある。
> import Control.MonadZero (guard)
> :t guard
forall m. (MonadZero m) => Boolean -> m Unit
Pursuit:
ソースコードを見ると引数が true なら pure unit そうでなければ empty みたいだ。
guard :: forall m. MonadZero m => Boolean -> m Unit
guard true = pure unit
guard false = empty
Pursuit:
で、この 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
- foldr - Data.Foldable - purescript-foldable-traversable - Pursuit
> 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 で試すと手軽だ。
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:
PureScript by Example 4.15
再帰よりも畳み込みを選べ、と。そりゃそうだ。ぼくは先に foldl が出て来たことに違和感を覚える。foldl / foldr の引数の一方はまさにアキュムレーターなわけだし……。
まとめ
くたびれたのでここで区切り。
再帰関数のことは他の言語でも使える知識なので良さそう。PureScript に関して言うと末尾再帰の最適化処理が入っていることと、do 記法の紹介が大きそう。 do 記法はまた出て来るはずだ。
参考
- PureScript by Example
- 実例による PureScript
- Language Guide
- Language Guide - Do notation
- Pursuit - pure - Prelude - purescript-prelude
- Pursuit - unit - Data.Unit - purescript-prelude
- Pursuit - guard - Control.MonadZero - purescript-control
- Pursuit - empty - Control.Plus - purescript-control
- Pursuit - foldl - Data.Foldable - purescript-foldable-traversable
- Pursuit - foldr - Data.Foldable - purescript-foldable-traversable
- Pursuit - snoc - Data.Array - purescript-arrays
次回以降の TODO
- PureScript by Example & PureScript Language Guide を読み進める
-
Array以外でのdo記法 - Tagged Unions / Newtype
psc-package- PureScript IDE の導入
- 24 Days of PureScript, 2016
- 24 Days of PureScript, 2014
- 某氏の記事の紹介
- github.com/purescript のコードを読む
- github.com/purescript-node のコードを読む
- github.com/purescript-contrib のコードを読む