integers = [1..]リストに見るストリームとイテレータ
リストは (ちょうど Haskell と同じように) Frege では最もよく使われるデータ構造です。
Java のバックグラウンドから来た人にとっては、リストの性質に関して気になるところが多数あるかもしれません。
-
メモリ空間の消費
-
参照の方法
-
更新の方法
-
使用可能な機能
-
イテレーション操作の方法
-
ストリーム、イテレータ、シーケンス、コレクションとの関係
Frege では、これらの性質のうちかなりの部分が全く異なっており、はるかに汎用的で強力な形になっています。無限の大きさを持つデータを扱うことができ、ストリームとしても使用でき、そしてイテレータやシーケンスを代替することができるのです。
メモリ消費
Frege のリストはしばしば、メモリをほとんど使用しません。正の整数全体からなる無限リストの例を見れば明らかです。
無限リスト
無限に続くにもかかわらず、integers がメモリを食い潰すことはありません。また、無限でなくとも巨大なリストの場合も同様です。
巨大なリスト
large = [1..100_000_000]さて、これはレンジ指定リストでのみ使える特殊な機能だと思われるかもしれません。しかし遅延評価の恩恵により、個々の要素が何らかの方法で生成されるような任意のリストに対してこの機能が使用可能です。
その他の無限リスト
-- derive next value from predecessor
cardinals = iterate (+1) 1
-- derive by repeating
toggles = cycle [true, false]
-- derive by mapping
data BigData = BigData { number :: Integer }
infiniteBigData = map BigData [1..]Java プログラマにとって、巨大なリストや Collection データ構造一般に対してもともと持っている不安を払拭するのは、いくらか訓練が必要です。
心得その一 : リストは評価されない限り、そのリストを定義するロジック (これを「サンク」と呼ぶ) の分しかメモリを占有しない。サンクを保持するために必要なメモリ空間はほぼゼロである。
心得その二 : 要素は必要となった時にだけ生成される。例えば infiniteBigData の 1000 番目の要素を問い合わせた場合、生成される BigData の値は (1000 個ではなく) ただ 一個 のみである。
参照と更新
リストの要素を参照するために以下に挙げる関数が使用できますが、これは特に驚くようなことではありません。与えられた添え字に対して値を取得するには !! 演算子を使用しますが、追加でインポートする必要があります。
!! 演算子のインポート
import Data.List(!!)予想通りの動作をするリスト関数
head [0..10]
last [0..10]
length [0..10]
[0..10] !! 5
-- pattern match with cases
doWithHead [] = ... -- when empty
doWithHead (head : tail) = ... -- use headFrege のリストはコレクションのように使えることがわかるでしょう。しかし、コレクション的な操作を行う関数には落とし穴があります。
コレクション的な関数は大抵の場合、パターンマッチによる場合分けのようなアプローチに置き換えた方が賢明です。こちらのアプローチは常に安全ですから。
リストの不変性
典型的な Java の書き方でリストの扱う場合、更新は in-place で行います。Frege の場合、このようなことは 決して 行いません。リストは不変データです。
Java 8 のストリームは破壊的に扱われます。例えば、ストリームに対して skip(1) を呼ぶと、そのストリームは更新され対応する要素は失われます。Frege ではこうはなりません。以下の関数は、ちょうど Java のストリームの方で対応する関数と同様、リストに対して呼ぶことができますが、戻り値はリストから効率よく作られた 「コピー」あるいは「ビュー」になります。元のデータは決して変更されません。
非破壊的なストリームとしてのリスト
drop 2 [0..10]
take 5 [0..10]
map (+1) [0..10]
filter (<10) [0..10]
fold (+) 0 [0..10]|
Note
|
効率が良いのは、元のリストが不変データであり、それゆえにほとんどの場合においてサブリストのビューはすべての要素をコピーする必要がないからです。例えば drop 2 で必要なのは、要素ふたつ分進んだ地点を開始点として保持することだけです。さらに遅延性も効率に寄与しており、例えば map (+1) では、マップされた結果の値が必要とならない限り決して計算が行われません。
|
しかし、リストは単に遅延コレクションかつストリームであるというだけではありません。リストはまた、イテレータあるいはシーケンスとして捉えることも可能です。
イテレータとしてのリスト
イテレータはリストの各要素を一つずつ、引数として関数に渡します。
1 から 10 までの数字を出力
for [1..10] println|
Note
|
for は forM_ の別名であり、バージョン 3.22.524 から使用可能です。さらに利点として、リストだけでなく任意の ListSource (toList 関数を持つ型クラス) のインスタンスに対して使用できます。
|
しかしそれだけではありません。
リストがアクション (IO () 型の値) を含む場合、sequence 関数を使用することでアクションを真に逐次実行することができます。
列内のすべてのアクションの実行
actions = map println [1..3]
sequence actions全体をまとめると
それでは、ここまでに登場したテクニックを使って平方数を出力してみましょう。面白くするために、純粋に (乗算ではなく) 数え上げを用いた極めて初歩的な方法で計算します。
鍵になるのは、任意の平方数は奇数の和で表されるという事実であり、まず奇数のリストを作る必要があります。Frege にはこのような場合に使用できる組み込みの記法 ([1,3..]) もありますが、どうせなので奇数からなるストリームを自前で作ってみましょう。
1 から始めて、直前の値に 2 ずつ加算することで次の奇数が得られます。
奇数のストリーム
unevens = iterate (+2) 1さて、n 番目の平方数を得るためには、最初の n 個の奇数を加算でたたみ込んで合計する必要があります。
最初の n 個の奇数を合計
square n = fold (+) 0 $ take n unevens|
Note
|
sum 関数を使えばもっと短く書けますが、それでは面白味がないので。
|
square 関数 (これ自体もストリーム unevens 上に作用する) を使用することで、任意の数からなるストリームをその自乗にマッピングし、すべての平方数からなるストリームを作り出すことができます。
平方数からなる無限ストリーム
squares = map square [1..]squares を出力するためには、単にシェル上で評価するだけでも可能で、シェル上で結果を確認することができます。それ以外に、squares それ自体を出力するためのイテレータとして使用することもできます。しかし、無限ストリームを出力するのはうまい方法ではないため、イテレーションを制限して必要な部分だけを切り出します。
必要な部分だけイテレーションする
for (take 10 $ drop 100 squares) println最後にひとつ例を
Frege のリストを単にコレクションとして捉えるのではなく、ストリーム、イテレータ、そしてシーケンスでもあると考えるには最初はやや慣れが必要です。しかし、リストの持つ力を最大限引き出すには避けては通れません。
先日私は、Frege に落書きを書かせようとしてみました。点と線をつなぐことで無限階段のように見せるだまし絵です。
Figure 1. 無限階段の落書き
与えられた出発点と次の段を計算するロジックからなる、文字通り (！) のコードです。
stairs = iterate step start画像の出力自体には描画のための (FregeFX REPL を使用する) グラフィックスコンテクストが必要ですが、描画すべきデータそのものは、以下のように単に計算の各ステップをつないだ列になります。
doodle ctx = map (connect ctx) stairsここに至っても、扱っているコードは 純粋 関数的であることに注意しましょう！ ここまででアクションからなるような無限リスト、ストリームあるいはイテレータを作ることはほとんどありませんでした。
そして、シーケンスを必要なだけの断片に制限し、paint (sequence_ . take 500 . doodle) のように paint 関数に渡すことによって実際の描画が行なわれます。
ここに挙げたのは、私がリストの持つ多様な用途をまさにありがたく感じた例です。この性質を利用することで、何をすべきか という仕様と、その仕様を実行することとを切り離すことができます。これを知った時、最初は「でも結果的に巨大な、メモリを食い潰すリストになるんじゃないかな」と感じ、そうはならない理由を理解するのにはやや時間がかかったものです。
参考文献
| The FregeFX REPL |
https://github.com/Dierk/frepl-gui The latest Version contains the stairs doodle as an example of how to load code from the web. |
| Code of stairs doodle |