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

この記事は以下のページに移転しました.

blog.ryota-ka.me

この記事は 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 Helloderivation は以下のように記述される*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) で表すことにする.ただし,列が打ち止めになる場合,tlnull を入れておくものとする.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 関数

mapfilter くらいがあると安心して年を越せそうなので,定義しておく.

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 ]

過去のもの

ryota-ka.hatenablog.com

ryota-ka.hatenablog.com

おわりに

CAMPHOR- Advent Calendar 2018,明日は @tomokortn の記事です.お楽しみに!