Nix Expression Languageで遅延リストを作ってみる

この記事はCAMPHOR- Advent Calendar 2018 15日目の記事です．14日目の記事は@Rtm6Lgoのとある研究室の運営のエモいお話でした．

Nix Expression Languageを用いて遅延リストを作る．普段は「ジェネレータを作ったり、遅延評価してみる」だが，Nix Expression Languageは基本的に純粋なので，mutableなstateをもつイテレータや，それを生成するジェネレータという概念はなじまない．

これまでの流れ#

Nixとは#

純粋関数型パケッジマネジャー．公式サイトでは以下のように紹介されている．

Nix is a powerful package manager for Linux and other Unix systems that makes package management reliable and reproducible. It provides atomic upgrades and rollbacks, side-by-side installation of multiple versions of a package, multi-user package management and easy setup of build environments.

Nix Expression Languageとは#

HomebrewではRubyが使われるが，NixではNix Expression Languageが用いられる．例えばGNU Helloのderivationは以下のように記述される^*1．

{ stdenv, fetchurl }:

stdenv.mkDerivation rec {
  name = "hello-${version}";
  version = "2.10";

  src = fetchurl {
    url = "mirror://gnu/hello/${name}.tar.gz";
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };

  doCheck = true;

  meta = with stdenv.lib; {
    description = "A program that produces a familiar, friendly greeting";
    longDescription = ''
      GNU Hello is a program that prints "Hello, world!" when you run it.
      It is fully customizable.
    '';
    homepage = https://www.gnu.org/software/hello/manual/;
    license = licenses.gpl3Plus;
    maintainers = [ maintainers.eelco ];
    platforms = platforms.all;
  };
}

以下混同の恐れが無い限り，Nix Expression Languageやその処理系を指してNixと呼ぶ場合がある．

基本的な文法については雰囲気で読めると思われるので，以下ではこの記事を読むにあたって必要な部分の解説のみ行う．

lists#

listはいくつかの値を順に並べたもので，square bracketを用いて[ 42 "Hello" ]のように書かれる．listはそれぞれの値についてはlazyであるが，listの長さについてはstrictである．なので，無限の長さを持つようなlistを作ることはできない．

nix-repl> let xs = [ 42 ] ++ xs; in xs
error: infinite recursion encountered, at (string):1:20

sets#

setは名前と値の組をいくつか集めてきたもので，Pythonの辞書，JavaScriptのオブジェクト，Rubyのハッシュに相当する^*2．それぞれの組は"attribute"と呼ばれる．

nix-repl> person = {
            name = "ryota-ka";
            age = 25;
          }

nix-repl> person.name
"ryota-ka"

また，各attributeはlazyに評価される．

nix-repl> person = {
            name = "a lady";
            age = abort "ouch";
          }

nix-repl> person.name
"a lady"

setの先頭にrecというキーワードを付けると，set内のattributeを再帰的に参照できるようになる．

nix-repl> { name = "lib-${version}"; version = "0.1.0"; }
error: undefined variable 'version' at (string):1:17

nix-repl> rec { name = "lib-${version}"; version = "0.1.0"; }
{ name = "lib-0.1.0"; version = "0.1.0"; }

関数#

pattern: bodyという形で書かれるものは関数である．patternと書いたが，本記事では単一の識別子を用いたパターンマッチ以外は登場しないので，arg: bodyと読み替えてもらっても構わない．

nix-repl> double = x: x * 2

nix-repl> double 42
84

f xは適用である．念のため．

遅延リストを作る#

とりあえず遅延リストを作っていく．遅延リストは先頭の値hdと後続の遅延リストtlとの組(hd, tl)で表すことにする．ただし，列が打ち止めになる場合，tlにnullを入れておくものとする．Nixにタプルは存在しないので，組を表現するためにsetを使うことにする．

以下では無限に1が続く列を定義している．

nix-repl> let
            ones = {
              hd = 1;
              tl = ones;
            };
          in
            ones
{ hd = 1; tl = { ... }; }

また，フィボナッチ数列は以下のように定義できる．

nix-repl> let
            fib =
              let
                aux = a: b: { hd = a; tl = aux b (a + b); };
              in
                aux 0 1;
          in
            fib
{ hd = 0; tl = { ... }; }

`toList`関数#

このままだと取り扱いに困るので，遅延リストをNixのlistに変換できるようにしたい．これを実現するtoList関数を以下のように再帰的に定める．

nix-repl> let
            ones = { hd = 1; tl = ones; };
            toList = xs: [ xs.hd ] ++ (if xs.tl == null then [] else toList xs.tl);
          in
            toList ones
zsh: segmentation fault  nix repl

onesは無限の長さを持つのでセグメンテーション違反が発生してしまった．

`take`関数#

遅延リストの先頭のいくつかの要素だけを取り出すtake関数を実装する．

nix-repl> let
            fib = let aux = a: b: { hd = a; tl = aux b (a + b); }; in aux 0 1;
            toList = xs: [ xs.hd ] ++ (if xs.tl == null then [] else toList xs.tl);
            take = n: xs:
              if n == 0
              then null
              else { hd = xs.hd; tl = take (n - 1) xs.tl; };
          in
            toList (take 10 fib)
[ 0 1 1 2 3 5 8 13 21 34 ]

関数をファイルに定義する#

定義すべきものが増えて，すべてをREPLに打ち込むのが大変になってきたので，汎用的な関数はファイルに記述していくことにする．lazy-lists.nixというファイルを用意して，以下のように書いておく．

rec {
  toList = xs: [ xs.hd ] ++ (if xs.tl == null then [] else toList xs.tl);
  take = n: xs:
    if n == 0
    then null
    else { hd = xs.hd; tl = take (n - 1) xs.tl; };
}

REPL上で:lコマンドを使うと，このsetのattributesが変数として展開され，利用できるようになる．

nix-repl> :l lazy-lists.nix
Added 2 variables.

nix-repl> toList
«lambda @ /Users/ryota-ka/lazy-lists.nix:2:12»

nix-repl> take
«lambda @ /Users/ryota-ka/lazy-lists.nix:3:10»

以降，遅延リストを扱う関数はここに追記していくものとする．

`map`関数・`filter`関数#

mapとfilterくらいがあると安心して年を越せそうなので，定義しておく．

map = f: xs:
  {
    hd = f xs.hd;
    tl = map f xs.tl;
  };

filter = f: xs:
  let
    tl = filter f xs.tl;
  in
    if f xs.hd
    then { hd = xs.hd; tl = tl; }
    else tl;

tl = tlと書いた部分は，Nixらしくinherit tlと書くこともできる．

いつものやつ#

フィボナッチ数列をそれぞれ2乗し，奇数のもののみ抜き出し，先頭から10個の要素を取り出してリストにしたものがこちら．

nix-repl> :l <nixpkgs>
Added 9706 variables.

nix-repl> :l fib.nix
Added 1 variables.

nix-repl> :l lazy-lists.nix
Added 4 variables.

nix-repl> let
            sq = n: n * n;
            odd = n: builtins.bitAnd 1 n != 0;
          in
            toList (take 10 (filter odd (map sq fib)))
[ 1 1 9 25 169 441 3025 7921 54289 142129 ]

過去のもの#

おわりに#

CAMPHOR- Advent Calendar 2018，明日は@tomokortnの記事です．お楽しみに！

脚注#

*1: https://github.com/NixOS/nixpkgs/blob/703827f36cc65b137eed4d759b31827d29733072/pkgs/applications/misc/hello/default.nixより引用．

*2: https://nixos.wiki/wiki/Nix_Expression_Languageによる．