Egisonで整数論

Egison Advent Calendar 1日目の記事です。 Egisonで整数を使って遊んでみます。

無限自然数列nats

EgisonはHaskellなどのように純粋関数型言語でもあるので無限列を素直に扱うことができます。 以下のように、take関数を使って先頭いくつかの要素を無限列から取り出します。

> (take 10 nats)
{1 2 3 4 5 6 7 8 9 10}

ピタゴラス数

ピタゴラス数をパターンマッチで取り出します。

> (take 10 (match-all nats (list integer)
   [<join _ <cons $x
     <join _ <cons $y
      <join _ <cons (& ?(lambda [$z] (eq? (* z z) (+ (* x x) (* y y)))) $z)
       _>>>>>>
    [x y z]]))
{[3 4 5] [6 8 10] [5 12 13] [9 12 15] [8 15 17] [12 16 20] [7 24 25] [15 20 25] [10 24 26] [20 21 29]}

無限素数列primes

これからは以下の様な素数列で遊んでみます。

> (take 10 primes)
{2 3 5 7 11 13 17 19 23 29}

双子素数、三つ子素数

双子素数をパターンマッチで取り出します。

> (take 10 (match-all primes (list integer)
   [<join _ <cons $n <cons ,(+ n 2) _>>> [n (+ n 2)]]))
{[3 5] [5 7] [11 13] [17 19] [29 31] [41 43] [59 61] [71 73] [101 103] [107 109]}

三つ子素数をパターンマッチで取り出します。

> (take 5 (match-all primes (list integer)
   [<join _ <cons $n <cons ,(+ n 2) <cons ,(+ n 6) _>>>> [n (+ n 2) (+ n 6)]]))
{[5 7 11] [11 13 17] [17 19 23] [41 43 47] [101 103 107]}
> (take 5 (match-all primes (list integer)
   [<join _ <cons $n <cons ,(+ n 4) <cons ,(+ n 6) _>>>> [n (+ n 2) (+ n 6)]]))
{[7 9 13] [13 15 19] [37 39 43] [67 69 73] [97 99 103]}

素数砂漠

素数砂漠とは素数でない連続した自然数の列のことを言います。 パターンマッチでそれを取り出してみます。 以下のパターンマッチで50以上の連続で素数が現れない自然数の列を取得しています。

> (take 5 (match-all primes (list integer)
    [<join _
      <cons $m
       <cons (& ?(gte-i? $ (+ 50 m)) $n)
        _>>>
     [m n]]))
{[19609 19661] [25471 25523] [31397 31469] [31907 31957] [34061 34123]}

まとめ

全探索を行うようなプログラムはEgisonのパターンマッチを使ってシンプルに記述することができます。
全探索を一部に含むアルゴリズムは多いので、Egisonのパターンマッチはそのような全探索をアルゴリズムの本質の部分の記述から切り離すのに大いに役立つはずです。
上に挙げたような例以外にも面白い例があれば私まで是非メール下さい。
Twitter上で@__Egiか@Egison_Langに話しかけてくださるのも歓迎しています。

次の題材

次はEgisonである程度大規模なグラフのパターンマッチをして遊んでみたいと思います。 現在そのための機能を開発中です。 月末までに完成させてデモする予定です。 どうぞご期待ください。

[Top]