Arantium Maestum

プログラミング、囲碁、読書の話題

OCamlのlambda IRをいじる(はじめに)

OCamlコンパイラの話題でよく聞くflambdaという最適化ステップについて資料を読んでいた:

https://ocaml.org/meetings/ocaml/2013/slides/chambart.pdf

スライド5にコンパイラの中間表現のステップと説明が書いてあったのが面白かった。

parse tree: AST
typed tree: AST with types
lambda: untyped lambda
clambda: lambda + closures
cmm: simple C­like
mach: instruction graph (llvm­like)
lin: almost like assembly

とのこと。大体の流れは知っていたものの、はっきりと書いてあるのを読むと勉強になる。

そう言えば昔@no_maddoさんのブログでこんな記事を読んだ:

no-maddojp.hatenablog.com

この記事に出ているとおり、ocamlcocamloptコンパイルする場合-dlambda-dclambdaといったコンパイラフラグを渡すことで中間表現が出力される。これを眺めていろいろあーだこーだと考えてみたい。

理由としては:

などが全部当てはまる。

とりあえず以下のことを調べてみたい:

  • 簡単なprintだけのプログラム
  • 変数(モジュールレベル・ローカル)
  • 関数(モジュールレベル・ローカル・部分適用)
  • データ(タプル、レコード、リスト、代数的データ型)
  • モジュール・ファンクタ
  • 複数ファイルにまたがるプログラム

ちなみにここらへんはもちろんコンパイラのバージョンに依存するところが大きい。私が現在使っているのはOCaml 4.11.1である。

何もしないプログラム1

まずはこれだけのプログラムをempty.mlとして保存し、lambda IRに出力してみる:

let () = ()

見ての通り何もしない。

これをocamlopt -c -dlambda empty.mlコンパイルすると:

(seq (let (*match*/81 = 0a) 0a) 0a)

こんな出力になる。

初めてこれだけを見るとわかりにくいが、まず大事なポイントとしては

  • 0a()に対応している
  • モジュールは(seq ... 0a)という形にコンパイルされる(...の中には1個以上のS式が入る)
  • let () = ()(let (*match*/81 = 0a) 0a)コンパイルされている
  • *match*/xxというのが左側の()に対応している。xxの部分は「変数名がユニークであることを保証する」α変換処理によって振られる数字。
  • (let (.. = .. ...) X)という形のXの部分で「変数を束縛した環境で評価するべき式」が入るのだが、このケースだと何も評価する必要がないので()を表す0aが入っている

ちなみに最後のポイントに関して、(.. = ..)で=が中置演算子になっているのはS式から外れてしまって少し悲しい気がする。まあ人が読みやすいようにADTを文字列出力しているだけだからどうでもいいのだけど・・・

何もしないプログラム2

次にこんなプログラムについて考える:

let () = ()

let () = ()

これはこんな感じに出力される:

(seq (let (*match*/81 = 0a) 0a) (let (*match*/83 = 0a) 0a) 0a)

seqの中にほぼ同一の要素が増えただけ。*match*/xxに振られた数字が違っていてユニークな変数名になっているのがポイント。

print_int

次に整数を標準出力に出すプログラム:

let () = print_int 1
(seq (let (*match*/81 = (apply (field 43 (global Stdlib!)) 1)) 0a) 0a)

今まで(*match*/81 = 0a)だったところの0a(apply (field 43 (global Stdlib!)) 1)に置き換わっている。

ポイントは:

  • (global X!)Xモジュールにアクセス
  • (field n X)でXモジュールのn番目のフィールドにアクセス(モジュール以外のデータ構造でも可能)
  • (apply X Y)で関数Xに引数Yを適用

という流れ。print_intStdlibモジュールのインデックス43に入っている、というのがlambda IRに変換される時点で解決済みなわけだ。なのでprint_intという変数名・文字列はIRには全く出てこない。

次回

次回はモジュール内で定義された変数がどうlambda IRで扱われるかを見ていく。

PythonでリテラルなしIfなし変数束縛なしFizzBuzzワンライナー〜ラムダの力を讃えよ〜

前回こう書いた通り:

追記:前回の記事に書き忘れたが、walrus operatorことAssignment Expressionsを多用しているのでPython3.8以降が必要。

これまで見てきたワンライナーはPython3.8から導入された変数束縛式:=を使っていて、そのせいで最近のPythonバージョンに依存している。

このコードだと:

(f:=lambda ...)(z:=len(a))そして(k:=sorted(f.__kwdefaults__))の三ヶ所で利用している。

そのうち後者二つは文字数を減らすために使っているようなもので、冗長でいいなら省略できる:

(f:=lambda *a,x=id,Fizz=id,Buzz=id:
  len(a) or 
  print(
    sorted(f.__kwdefaults__)[f(f)]*(x%f(f,f,f)==len(a))+
    sorted(f.__kwdefaults__)[len(a)]*(x%f(f,f,f,f,f)==len(a))
    or x)
  or f(x=x+f(f)))(x=f(f))

(読みやすいように改行付き)

しかしfという関数名をつけるのは再帰的な定義の要。やっぱり変数束縛は必要だろう。

そのように安直に考えていると

ラムダを崇めよ、ラムダの力を讃えよ

どこからともなく迷える子羊を導く声が聞こえた。多分内なるアロンソ・チャーチかハスケル・カリーが語りかけてきているのだろう。あるいはラムダマンことフィル・ワドラー("Phil Wadler Lambda Man"で検索してください)かもしれない。

そう、ラムダに魂を惹かれた者なら誰でも知っている。再帰がしたいならFixed Pointを使えばいいじゃない。

つまり別の無名関数を使って、再帰させたい無名関数を自己適用することで、関数内でその関数自身が引数として束縛されている状況を作り出せる。

無名関数の中で使われるfを、外部環境を参照するのではなく、この無名関数の仮引数として追加してやる:

lambda *a,f=id,x=id,Fizz=id,Buzz=id:
  len(a) or
  print(
    sorted(f.__kwdefaults__)[f(f)]*(x%f(f,f,f)==len(a))+
    sorted(f.__kwdefaults__)[len(a)]*(x%f(f,f,f,f,f)==len(a)) or
    x) or
  f(f=f,x=x+f(f))

(最後の再帰的呼び出しの時にもちゃんとf=fと渡してやるのを忘れずに)

そしてこの無名関数を引数に受け取り、必要な引数を与えて呼び出すための別の無名関数を使えばいい:

(lambda f:f(f=f,x=f(f)))(
  lambda *a,f=id,x=id,Fizz=id,Buzz=id:
    len(a) or 
    print(
      sorted(f.__kwdefaults__)[f(f)]*(x%f(f,f,f)==len(a))+
      sorted(f.__kwdefaults__)[len(a)]*(x%f(f,f,f,f,f)==len(a)) or
      x) or
    f(f=f,x=x+f(f)))

ちょっと文字数を減らしたいならついでにkも仮引数に追加できる:

(lambda f:f(f=f,k=sorted(f.__kwdefaults__),x=f(f)))(
  lambda *a,f=id,k=id,x=id,Fizz=id,Buzz=id:
    len(a) or 
    print(
      k[f(f)]*(x%f(f,f,f)==len(a))+
      k[len(a)]*(x%f(f,f,f,f,f)==len(a)) or
      x) or
    f(f=f,k=k,x=x+f(f)))

というわけでWalrus Operator使わないで202文字にまとまる:

リテラルも変数束縛もいらない。ラムダさえあればいい・・・

PythonでリテラルなしIfなしFizzBuzzワンライナー

前回の記事FizzBuzzコードをちょこっといじってこんな感じで満足していた:

そうしたらこんなツイートが:

え、IfもなしでFizzBuzzを・・・?

出来らあ!

と啖呵を切って考えてみる。まあ前回のコードでも利用していたand/orの特性を使えばifは当然省けるはず。

Pythonだと真偽値以外もTruthinessを持ち、特に空文字列は偽なので("Fizz" if x%3==0 else "")+("Buzz" if x%5==0 else "") or xのようなロジックを使うのが一番スマート。

もう一つハック的なポイントとして、PythonTrueFalseはほぼ10と同等なので("Fizz" * (x%3==0))+("Buzz" * (x%5==0)) or xと書ける。

これでコア部分のロジックはifなしでいけそう。

前回の記事でも紹介した通り、"Fizz", "Buzz", 3, 5はリテラルなしで簡単に作れる。しかし0は(無名関数の定義の仕方のせいで)作れなくなっている。f(f)-f(f)のようにして作ってもいいのだが、長くなるのでイマイチ。

まず考えたのは関数内の式の順番を入れ替えるやり方:

FizzBuzzのプリント・ループ処理に入る条件をA!=idにして、len(a)は関数の最後に持ってきた。これでf()が0になる。

しかし、よく考えるとf()で0を表現するまでもなく、プリント・ループ処理に入った時点でlen(a)という0の値をすでに評価していることに気づいた。この値を変数束縛して使ってしまえばいい。

さらに二つ修正点がある:

  • X if Y else Zという構文を使っていた時はXZの部分は評価されないケースがあった。それに対してX + Y or Zの場合、Xの部分は必ず評価される。なのでX(k:=sorted(f.__kwdefaults__))という変数束縛を持ってこれる
  • 0が表現できるので仮引数をソートして"Buzz"が先頭に来ても問題ない。ので仮引数にAを使う必要がなくなり、"Fizz"と"Buzz"をアクセスするインデックスに1と0を使える(文字数を減らせる)。

これらを踏まえて、とりあえず現在の最終形:

ifなしという制約がつく前に比べて文字数が減ってる・・・ (この記事の冒頭のコードが211文字、最終形のコードが162文字)

制約がついて工夫しないといけなくなるといいアイデアが出る、というケース。

追記:前回の記事に書き忘れたが、walrus operatorことAssignment Expressionsを多用しているのでPython3.8以降が必要。

PythonでリテラルなしFizzBuzzワンライナー

ツイッターでこういう話が出ていた(@nishio さん、面白いお題をありがとうございます!):

リテラルなしでFizzBuzz?出来らぁ!

数字は「*argsで可変長引数をとって、その長さを返す」関数で表現できる。

b = Fizz.Buzz
one = b(b)
two = b(b,b)
three = b(b,b,b)

といった使い方ができる(ちなみに引数の値自体はなんでもいい)。

文字列はオブジェクトの__name__を取れば大丈夫。

ガハハ、勝ったな、と思ったら:

え、リテラルも改行もなしでFizzBuzzを・・・?

この縛りだとクラスや関数をclass/defで定義できなくなってしまう。

ならば・・・

私が勝手に「Guidoの置き土産」と呼んでいるWalrus Operator:=を使えば一つの式の中で変数束縛し放題。「改行なし」をさらに制限して「式一つ」で出来てしまう。

X and Y and ZXYTruthyな値なら順次に評価していって最終的な値はZになる。

lambdaを使った無名関数二つにWalrus Operatorでgfという名前を束縛している。

順番が前後するが、まずf関数を見てみる。これは必要な数字と文字列を得るための関数で、「*argsで可変長引数をとって、その長さを返す」アイディアはそのまま、そしてlambda *a, Fizz=id, Buzz=id:...FizzBuzzをデフォルト値のあるkwargsとして追加している。これでf.__kwdefaults__{ "Fizz": ..., "Buzz": ... }といったdictionaryが入手できて、キーから文字列が得られる。

g関数はFizzBuzzロジックと再帰によるループを、X if Y else Zand/or、walrus operatorを使いまくって一つの式に詰め込んでいる。

個人的に一番のポイントだったのはx%(y:=f(f,f,f)) * x%(z:=f(f,f,f,f,f))とx%3が0だった時に右側がショートサーキットで飛ばされないよう、andではなく*にしてあるところ。

なんでfgのあとに出てくるかというと、もともとf:=lambda *a,Fizz=id,Buzz=id:...と定義していたのだが(組み込み関数の中でidが一番短い)、gと定義順を逆にすれば文字数が削れるのと関係ないidが出てこなくて済む、ということに気づいて順番を入れ替えたから。Pythonでは関数のデフォルト引数は「件数呼び出し時」ではなく「関数定義時」に評価されるので、すでに定義済みの変数しか使えない(例えば再帰的にデフォルト引数をfにすることもできない)。

これでg(f(f))すると1からmax recursion depthに到達する995までの数字のFizzBuzzが表示される。

その後少し修正を加えて、今現在の最終形はこちら:

変更点は以下の通り:

  • 単一の無名関数に詰め込んだ(そのため新しいkwargsであるAを定義している。f(f,f,f)のように引数を普通に入れる場合は整数を返し、f(A=1)のようにすれば先ほどのg関数のようにFizzBuzzループが始まる)。ちなみに可変長引数aの長さを条件にどっちの処理を行うかの分岐をするという実装の関係でf()で0が表現できなくなっている。そのせいで新しいkwargsはFizzとBuzzよりもlexographicに小さい文字列である必要が出てくるので大文字のAにしてある。また無名関数が一つになった関係でプレースホルダーとしてidを使う必要が出てきたのは無念。
  • list(f.__kwdefaults__)だとどの順番で文字列が得られるかが微妙に実装依存な気もする(最近のPythonでは違うとは思うが)のでsorted(f.__kwdefaults__)にして文字列の順番が一意に定まるようにした。
  • walrus operatorによる変数束縛を減らした。束縛されるのはf関数自体とkw:=sorted(f.__kwdefaults___)の二つだけ。前者は(特に再帰のために)絶対必要(いや、やろうと思えばFix operator的なことができるのか?)で、後者はツイートに入れるための文字数制限の関係で必要。

リテラル禁止FizzBuzz、問題としてなかなか楽しかったのでもっと流行ってもよかったのになー、と少し寂しい気持ちがある。

Coqの演習問題、あるいはifとapplyについて

Logical Foundationsを進めがてら、基礎固め的に簡単な命題論理の命題を証明してみたいと思ってググったらこんなスレに遭遇した:

coq.discourse.group

このうちの最初の問題が簡単ながらもいくつか面白い点があったのでメモ。

証明する命題:

Lemma a1 : forall (A B C D : Prop),
    (A -> B) -> (A -> C) -> (B -> C -> D) -> (A -> D).

まずは命題と仮定を導入しておく:

Proof.
  intros A B C D.
  intros Hab Hac Hbcd Ha.

この時点での仮定とゴールは以下のようになっている:

  A, B, C, D : Prop
  Hab : A -> B
  Hac : A -> C
  Hbcd : B -> C -> D
  Ha : A
  ============================
  D

解1

ここで一番スッキリした解法は

  apply Hbcd.
  - apply Hab. apply Ha.
  - apply Hac. apply Ha.
Qed.

になると思う。

  • B -> C -> Dという仮定を適用してゴールDを二つのサブゴールBCに変換
  • サブゴールBは仮定A -> BとAで証明
  • サブゴールCは仮定A -> CとAで証明

となる。

ここで個人的に面白いポイントは

apply Hbcd(仮定B -> C -> D)でゴールDB -> Cになるのではなく、BCという独立したサブゴールになること。

よく考えたらB -> Cになってしまっては意味がおかしくなってしまうのだが、この「二つのサブゴールを導入する」挙動は最初何が起きたのかわからず混乱した。

B -> C -> D(B /\ C) -> Dと等価なので、まずB /\ Cに変換してからsplitしていると考えればいい。

解2と仮定の複製

別解を考えてみたいので、命題と仮定をintrosで導入した時点まで戻る:

Proof.
  intros A B C D.
  intros Hab Hac Hbcd Ha.
  A, B, C, D : Prop
  Hab : A -> B
  Hac : A -> C
  Hbcd : B -> C -> D
  Ha : A
  ============================
  D

ここで個人的には:

  • 仮定にAA -> BがあるからB
  • 仮定にAA -> CがあるからC
  • BCB -> C -> DだからD

という流れで証明した方が自然に思える。Coqでそう証明する場合は:

  assert (Ha' := Ha).
  apply Hab in Ha.
  apply Hac in Ha'.
  apply Hbcd in Ha.
  - apply Ha.
  - apply Ha'.
Qed.

のようになる。

ここで面白いのはassert (Ha' := Ha)の部分で、仮定Ha : AHa' : Aという別の仮定として複製している。

というのもこれを省略して単にapply Hab in HaAA -> Bを適用してしまうと、その適用された仮定Aがなくなってしまい、A -> Cを適用するためのAがなくなってしまうためだ。複製しておけばHa'が残っているのでそちらにA -> Cを適用できるから大丈夫。

複製する方法はStack Overflowから:

stackoverflow.com

ただ、上記の回答でも言及されている通り、「仮定を複製しないといけない」ような証明の仕方はCoqらしくない。仮定をいじり続けてゴールに到達するのではなく、ゴールを変換していく形がCoqとしては自然だ(とLogical Foundationsにも書いてある)。

解3

またしても命題と仮定をintrosで導入した時点まで戻る:

Proof.
  intros A B C D.
  intros Hab Hac Hbcd Ha.
  A, B, C, D : Prop
  Hab : A -> B
  Hac : A -> C
  Hbcd : B -> C -> D
  Ha : A
  ============================
  D

ここでapply Hbcd in Habあるいはapply Hbcd in Hacという手もある。

一般的にH1 : W -> YH2 : X -> Y -> Zという仮定があってapply H2 in H1した場合、H1 : Zと片方の仮定が変換された上でサブゴールとしてWXが追加される。

それを利用すればこんな感じで:

  apply Hbcd in Hac.
  - apply Hac.
  - apply Hab. apply Ha.
  - apply Ha.
Qed.

DB、そしてAというサブゴールを個別で証明して終わり。

仮定に仮定を適用するとサブゴールが作成される、というのはちょっと非直感的な印象だった。

あとHbcd : B -> C -> DでもHbcd : C -> B -> Dでも大丈夫なのに、Hbcd : (B /\ C) -> Dだとapply Hbcd in Hacできない、というのは注意点。そういう意味では->で記述されている方が使い勝手がいいようだ。

雑感

Logical Foundationsの演習問題はinductionやらdestructやらが入り混じることが多く、ガチャガチャやっていたらなんだか証明できてしまった「俺たちは雰囲気で証明している」感があった。

なのでこういう簡単な演習問題で->を含む命題がapplyで使われるとどういう挙動を見せるのか試せてよかった。命題論理をいろいろいじり倒すのも勉強になりそう。

OCamlのGADTでVariadic Function(Stack Overflowより)

このStack Overflow問答が大変面白かったのでメモ:

stackoverflow.com

サンプルコードは少し(自分にとっては)わかりやすいように変えてある。

何をしたいか

第一引数によって、それ以降幾つの引数をとるかが変化するような可変長引数関数を書きたい。

例えば

let g = f 1;;
val g : int -> string = <fun>

let h = f 2;;
val h : int -> int -> string = <fun>

のような関数fが書けるだろうか?

結論から言ってしまえば、このように「引数の数がintの値に依存するような関数」は書けない。(それこそ依存型の出番じゃないか?)

しかし第一引数にGADTな値を当てることで引数の数をコントロールすることはできる。

GADT

というわけで引数の数を表すGADTを定義してみる:

type input = int
type output = string

type _ arity =
  O : output arity
| I : 'a arity -> (input -> 'a) arity

各引数の型であるinputと最終的な出力の型outputを使ってGADTの_ arityを定義していて、例えばI (I O)という値は(input -> input -> output) arityという型になる。ADTの値によって多引数な関数の型が表されているのがわかる。

複数のinput型引数をまとめるアキュミュレータに当たるデータの型accと、そのアキュミュレータの初期値acc_init、逐次アキュミュレートするための関数accumulate、そして最終的にoutput型に変換して返すための関数processを定義する:

type acc = int list

let acc_init = []
let accumulate x xs = x::xs
let process xs = string_of_int @@ List.fold_left (+) 0 xs

これらを使って可変長引数関数を作れる。

まずはアキュミュレータを明示的に使ったf_auxを定義し、それとacc_initを使ってfを定義する:

let rec f_aux : type f. acc -> f arity -> f =
  fun acc arity -> (match arity with
    O -> process acc
  | I a -> (fun x -> f_aux (accumulate x acc) a))

let f arity = f_aux acc_init arity

f_auxではlocally abstract type(かつpolymorphic syntax)を使ってacc -> f arity -> fな関数型を定義している。これでI (I O) : (int -> int -> string)な値を渡されればint -> int -> stringな関数(つまりint型の引数を2つとってstringを返す関数)を返すような高階関数ができる。

使ってみる:

utop # let g = f (I O);;
val g : input -> output = <fun>

utop # let h = f (I (I O));;
val h : input -> input -> output = <fun>

成功。

モジュール化

OCamlなのでモジュール・ファンクタで抽象化してみる。

まずはファンクタの引数のシグニチャ

module type S = sig
  type input
  type output

  type acc
  val acc_init : acc
  val accumulate : input -> acc -> acc
  val process : acc -> output
end

引数のモジュールは

  • 引数と戻り値の型
  • 複数の引数をどう集めてどう最終的に変換するのか

を提供することになる。

ファンクタ本体:

module F (X : S) = struct
  include X
  
  type _ arity =
  | O : output arity
  | I : 'a arity -> (input -> 'a) arity

  let rec f_aux : type f. acc -> f arity -> f =
    fun acc arity -> (match arity with
      | O -> process acc
      | I a -> (fun x -> f_aux (accumulate x acc) a))

  let f arity = f_aux acc_init arity
end

ファンクタ部分にtype _ arityf_aux/fを入れているので、可変長引数に関する部分はすべてファンクタ側で持っている。

とりあえず先ほどの例と同じintstringでやってみる:

module M = struct
  type input = int
  type output = string

  type acc = int list
  let acc_init = []
  let accumulate = List.cons
  let process xs = string_of_int @@ List.fold_left (+) 0 xs
end

module MV = F(M)

使ってみる:

utop # let g = let open MV in f (I O);;
val g : int -> string = <fun>

utop # let h = let open MV in f (I (I O));;
val h : int -> int -> string = <fun>

成功。

これで引数・戻り値の型と複数の引数の組み合わせ方をモジュールで定義すれば、あとはファンクタ適用だけで可変長引数な関数を作成できるようになった。

GADTの限界

限界というと言い過ぎかもしれないが、GADTを使って可変長引数を実現したとしても「引数の数は静的に解決できなくてはいけない」という制約は残る。つまり実行時にI (I (I O))のような任意の値を構築してfに渡してやるようなことはできない。

let make_arity n =
  if n = 0 then O
  else if n = 1 then I O
  else if n = 2 then I (I O)
  else if n = 3 then I (I (I O))
  else failwith "n out of range in make_arity"

のような関数を書いたとして

Line 3, characters 21-24:
Error: This expression has type (input -> 'a) arity
       but an expression was expected of type output arity
       Type input -> 'a is not compatible with type output

こんな感じに怒られてしまう。

ポイントはmake_arityの型がint -> ??? arityになってしまうこと。OI OI (I O)I (I (I O))はすべて型が違うので、同じ型の引数で戻り値の型を変えられないのでmake_arity関数は定義できない。

それでもこの手法は実際にPrintfなどの実装で役に立っているらしい(詳細は元のStack Overflow記事を参照)。GADTの利用法についてはもっといろいろと調べていきたい。

OCaml Batteries IncludedのLazyList/Seq/Enumについて

OCamlの標準ライブラリは貧弱なことで知られている。

OCamlコミュニティの間でも「あれはOCamlコンパイラを書くためのライブラリだ」と言われていて、実際INRIAで必要最低限(つまりコンパイラを書くのに必要な分だけ)提供している側面がある。

基本的なデータ構造に関しても、用意されている関数群は微妙に足りなかったりする。(例えばList.rangeのような数字のリストを作成する関数がなかったり)

大抵は自分で3行ほどで実装できるのだが、それにしても頻出するのでめんどくさい。さらにいえばもうちょっと他にもデータ構造がほしいと思うことも多い。(例えばdequeなど)

そういう穴を埋める「準標準ライブラリ」がいくつか存在する。Jane StreetのCore、コミュニティによって維持されているBatteries Included、そして比較的新しいcontainersあたりが有名どころだ。

私はBatteries Includedを使うことが多いが好みの問題だと思う。

そのBatteries IncludedのモジュールLazyList、SeqそしてEnumに関して最近調べたので記録しておく。

これらすべて「作成時にすべての要素がメモリに乗らないリスト」的なものである。なので具体的にどう違うのかを認識しておきたい。

LazyList

LazyListHaskellなどでもお馴染みの遅延リストだ。作成時には要素がメモリに乗っておらず、必要に応じて算出される。

遅延のポイントは

  • 必要に応じて算出される
  • 一度算出された値はメモ化され、再度計算が必要になることはない

の二点だ。

例えばこんな副作用のある関数からLazyListを作るとする:

let f () = print_endline "hello"; 0;;
let ll = BatLazyList.from f;;

llが作成された時点ではなんの計算も起きず、副作用も起きない。

第一要素を初めて求めてみる:

utop # BatLazyList.first ll;;
hello
- : int = 0

しっかり副作用が起きる。

もう一度第一要素を求めてみる:

utop # BatLazyList.first ll;;
- : int = 0

今度は副作用なし。

Seq

SeqはLazyListに似ているが、重要なポイントはdelayedだがlazyではないというところ。

作成時には要素が算出されず、必要に応じて計算が行われるのは同じだが、メモ化が起こらない。

let f n = print_endline @@ string_of_int n; Some (0, n+1);;
utop # let s = BatSeq.unfold f 0;;
0
val s : int Seq.t = <fun>

実際には作成時に第一要素だけは算出されているようだ。

第一要素を初めて求めてみる:

utop # BatSeq.first s;;
1
- : int = 0

しっかり副作用が起きる。(多分第一要素をBatSeq.firstで求めた時点で第二要素を算出している)

もう一度第一要素を求めてみる:

utop # BatSeq.first s;;
1
- : int = 0

また同じ副作用が起きる。

Seqを作成した時点で第一要素が作成されている(そのための関数適用が起きている)というのは記事を書き出す時点では知らなかった。副作用がある場合はちょっとしたハマりどころかもしれない。

Enum

EnumはSeqと同じくlazyではなくdelayedだが、さらに重要なポイントとしては、Enumの要素を算出することは破壊的だという点。Seqがイミュータブルなのに対してEnumはミュータブルなのだ。

let f n = Some (n, n+1);;
let e = BatEnum.unfold 0 f;;
utop # BatEnum.get e;;
- : int option = Some 0

utop # BatEnum.get e;;
- : int option = Some 1

utop # BatEnum.get e;;
- : int option = Some 2

関数型プログラミングファンなら「参照透明性とは・・・」と言いたくなるかもしれない挙動。

これは例えばPythonのジェネレータと同一の挙動で、「一回だけ消費する」ことに特化している。Python2から3への変更の一つに、多くの関数がリストではなくジェネレータを返すようになった点があることからもわかる通り、意外とほとんどのケースでは「一回だけ消費する」場合が多い。

BatteriesでもEnumはちょっと特別扱いされていて、すべてのデータ構造から「要素に順次アクセスする」ためのインタフェースとしてEnumを返す関数M.enumが定義されている。

BatteriesのGithub Issuesにこんなものが立っていたが:

github.com

ちょっと無理筋じゃないかな?という気がする。