リンクトリストの定義

Perl

HOP（Higher-Order Perl）にしたがって，リンクトリスト*1を考えます．

HOPでいうところのリンクトリストは，それらしく書くと以下のものです．

linked_list = node

node | [ head, tail ]
     | [ head, undef]

tail = node

言葉でいうと次のどちらかが成り立つ構造をリンクトリストと呼んでいます．

  • 要素が二個の配列で，最初の要素がノード，次の要素がリンクトリスト
  • 要素が一個の配列
  • 終端はundef．ただし，終端はないかもしれません．

headはノードの要素，tailはそのノードの次のノードをさすものです．ただし，入れ子構造なのでノードとリンクトリストが同一視されています．また，有限のリンクトリストは終端undefをもちます．この定義では，終端が存在しないリンクトリストも許容されており，これが無限のリンクトリストです．ただし，しばらくは有限のリンクトリストだけを考えます．

この定義にしたがうと，

$list = [1, [2, [3, [4, undef] ] ] ];

というスカラーはリンクトリストになります．

とりあえず，簡単なユーティリティを準備します．

sub head{
    return $_[0]->[0];
}

sub tail{
    return $_[0]->[1];
}

headはリンクトリストから最初のノードの要素を取り出します．tailはリンクトリストの二つ目以降ノードから作られるリンクトリストを作ります．例えば，

use Data::Dumer;

$list = [1, [2, [3, [4, undef] ] ] ];
print Dumper head $list;
print Dumper head $tail;

の出力は

$VAR1 = 1;
$VAR1 = [
          2,
          [
            3,
            [
              4,
              undef
            ]
          ]
        ];

となります．

*1:HOPでいうところのinfinite stream．これをリンクトリストというのはちょっと抵抗がないわけではないですが．