FOOP で DAG する

 前回の DAG スクリプトは如何だったでしょうか?
 search-XXX なんて関数名は有りがちな名前。そんな時、関数名の衝突を避けるには FOOP(Functional-Object Oriented Programming )なんてもってこい。
 とは言え、newLISP の目玉でもある FOOP を使ってこなかった私。この辺で覚書きでも作っておこうかと、、、
 
 ということで、コードは、

(new Class 'MAIN:DAG)

(define (DAG:DAG lst)
    (list DAG lst))
(define (DAG:nodes)
  (self 1))
(define (DAG:search-pre)
  (letex (_x (args 0))
    (if (find-all '(? _x) (self 1)) $it "start")))
(define (DAG:search-next)
  (letex (_x (args 0))
    (if (find-all '(_x ?) (self 1)) $it "end")))
(define (DAG:search-all)
  (letex (_x (args 0))
    (local (res)
      (dolist (x (self 1))
         (if (match '(? _x) x) (push x res -1)
             (match '(_x ?) x) (push x res -1)))
      res)))

 ポイントは、オブジェクト・データ部分のアクセスが self になること。
 とわかっていも、私には慣れが必要かも。引数の扱いが、、、
 さて、使い方は、

> (set 'mydag (DAG '((a c) (b c) (c d) (c g) (d e) (d f))))
(DAG ((a c) (b c) (c d) (c g) (d e) (d f)))
> (:nodes mydag)
((a c) (b c) (c d) (c g) (d e) (d f))
> (:search-all mydag 'd)
((c d) (d e) (d f))
> (:search-pre mydag 'd)
((c d))
> (:search-next mydag 'd)
((d e) (d f))
> (:search-pre mydag 'a)
"start"
> (:search-next mydag 'g)
"end"
> 

 こんな感じ。

 以上、如何でしょうか?

newLISP で DAG する...または、match な find-all

 DAG (Directed acyclic graph) とは有向非巡回グラフのことらしい。
 といっても、DAG が何かわからずにコードを書いた私。
 きっかけは、newLISP Foram の投稿から。
 これは簡単にコード化はできそうだと思い、書いて投降したのですが、、、
 何か、しっくりこなかったのです。newLISP らしくないというか、、、
 同投稿で rickyboy 氏が findmatch を使っているのを見て、思い出しました。 find-all がリストに対して match になる(第二構文)ことを。

(if (replace nil (map (fn (x) (match '(? _x) x true)) lst)) $it "start")

 なんて、長ったらしいコードは、find-all を使えば、

(if (find-all '(? _x) lst) $it "start")

 ああ、すっきり。
 前にも、こんなことがあったのを思い出し、忘れないよう blog に(笑)
 先に newLISP Foram に投降したコードは、こんな感じに変わります。

(define (search-pre lst)
  (letex (_x (args 0))
    (if (find-all '(? _x) lst) $it "start")))
(define (search-next lst)
  (letex (_x (args 0))
    (if (find-all '(_x ?) lst) $it "end")))
(define (search-all lst)
  (letex (_x (args 0))
    (local (res)
      (dolist (x lst)
         (if (match '(? _x) x) (push x res -1)
             (match '(_x ?) x) (push x res -1)))
      res)))

 ついでに newLISP らしく、ifcond 的な使い方も(笑)

 以上、如何でしょうか?

projecteuler15...または、再帰による組み合わせ

 projecteuler問題15 は、格子の道筋を数える問題。
 とは言え、N×Nの正方格子で下と右の二つを半分ずつ選ぶことになるから、その組合せ数を求めるだけなら、以下の計算で十分。

> [cmd]
(int (/ (apply * (map bigint (sequence 40 21)))
        (apply * (map bigint (sequence 20  1)))))
[/cmd]
137846528820
> 

 bigint大整数にしておくのがみそ(笑)
 さて、具体的に道筋を求めるには、下と右をそれぞれ '1''0' とすれば、

(define (test n m (bit '()) res)
  (let (c (count '(0 1) bit))
    (if (= (length bit) (+ n m)) (push bit res -1)
      (begin
        (when (< (c 0) n) (setq res (test n m (cons 0 bit) res)))
        (when (< (c 1) m) (setq res (test n m (cons 1 bit) res)))
      ))
  res))

 として、

> (test 2 2)
((1 1 0 0) (1 0 1 0) (0 1 1 0) (1 0 0 1) (0 1 0 1) (0 0 1 1))
> (length (test 2 2))
6
> 

 再帰を使っているので 20×20 を実行させると恐ろしく時間がかかります。ご注意を(汗)

 以上、如何でしょうか?

newLISP マニュアル v.10.6.0 日本語訳公開

 if が anaphoric if になり、macro組込関数に昇格した安定版のリリースです。
 特に macro.lsp を使っている人は、ロードしないように気を付けましょう(笑)
 もちろん、ウェブ・ブラウザ上の newLISP in a browser も v.10.6.0 になっていますから、インストールしなくても試せます。
 ということで、newLISP の User Manual and ReferenceGUI functionsCode Patterns の全訳のリリースです。

newlisp_manual-10600
guiserver_manual-161
CodePatterns-10507
こちらからダウンロードしてください。

 目次も含め日本語併記にしてあります。
 Lutz氏のご好意によりこちらから見ることもできます。

 いつものように、間違いやおかしな点が有りましたら、こちらの blog までご一報ください。

 以上、如何でしょうか?

newLISP マニュアル v.10.5.8 開発版日本語訳公開

 v.10.5.8 から、macro が組込関数に昇格します。つまり、macro.lsp を読み込まなくても使えるようになると言うこと。
 マニュアルにある macro の動作例を試すには、v.10.5.8 をインストールしなくても、ウェブ・ブラウザ上の newLISP in a browser で試せます。便利ですね(笑)
 そろそろ、安定版のリリースも近い?
 さて、開発版 newLISP の User Manual and Reference の全訳のリリースです。

newlisp_manual-10508
こちらからダウンロードしてください。

 目次も含め日本語併記にしてあります。

 いつものように、間違いやおかしな点が有りましたら、こちらの blog までご一報ください。

 以上、如何でしょうか?

ウェブ・ブラウザで newLISP チュートリアル

 JavaScript 版 newLISP を使った newLISP チュートリアルが、ここにあります。

http://www.newlisp.org/newlisp-js/index.html

 考えてみれば、newLISP をインストールしなくてもウェブ上で使える JavaScript 版 newLISP 。チュートリアルに持って来いですよね。さずが、Lutz 氏。
 チュートリアルのベースは〝Introduction to newLISP〟。まだ、〝The basics〟編だけですが、順次残りも載る予定のようです。(2014/2/18追記:tutorial.lsp が無くなり。代わりに index.html に 〝Introduction to newLISP〟の紹介が記載されるようになりました。よって、”tutorial-jp.lsp” の掲載も外します)
  そこで、”tutorial.lsp” の日本語併記版”tutorial-jp.lsp”を用意しました。

newlisp_manual-10507
こちらからダウンロードしてください。

 中には、開発版 newLISP の User Manual and Reference と JavaScript 版 newLISP の使い方である README.html の全訳も入っています。
  newLISP サイトの “index.html” 下部の open ボタンをクリックして、ダウンロードしたzipファイル内の “tutorial-jp.lsp” を読み込んでから、eval ボタンをクリックすれば日本併記のチュートリアルが始まります。
 zipファイル内の “index-jp.html” を使えば、info ボタンや doc ボタンで日本語併記の html が表示されます。但し、”newlisp-js-lib.js” が別途必要ですので、こちらからダウンロードして同じフォルダーに置いてください。

 以上、如何でしょうか?

newLISP マニュアル v.10.5.7 開発版日本語訳公開

 この開発版の目玉は何といっても newlisp-js-lib.jsJavaScript 版 newLISP です。
 つまり、ウェブ・ブラウザで JavaScript のように newLISP が使えるのです!
 使い方は、同梱の “README.html” でどうぞ。(日本語版は、下の URL からダウンロードできます)
 newLISP の全ての関数が使えるわけでもありませんが、これを使えば newLISP の入出力をブラウザで簡単に行えるかも。”README.html” の他に同梱の “index.html” や “app.html” が参考になります。
 また、JavaScript 版 newLISP 専用の関数もありますので、詳細はマニュアルの日本語訳をどうぞ。

 開発版 newLISP の User Manual and Reference と README.html の全訳のリリースです。

newlisp_manual-10507
こちらからダウンロードしてください。

 目次も含め日本語併記にしてあります。

 いつものように、間違いやおかしな点が有りましたら、こちらの blog までご一報ください。

 以上、如何でしょうか?

newLISP マニュアル v.10.5.6 開発版日本語訳公開

 このバージョンは開発版ですが、ifanaphoric if に変身しています。どういう事かと言うと、if の条件式の結果をシステム変数 $it で参照できるのです。と言うことは拙作 aif が不要に、、、
 冗談はさておき、Lutz 氏に感謝!ますます使いやすくなる newLISP です。
 さて、詳細はマニュアルの日本語訳でどうぞ(笑)。

 newLISP の User Manual and Reference の全訳のリリースです。

newlisp_manual-10506
こちらからダウンロードしてください。

 目次も含め日本語併記にしてあります。

 いつものように、間違いやおかしな点が有りましたら、こちらの blog までご一報ください。

 以上、如何でしょうか?

projecteuler14...または、再帰か繰り返しか

 projecteuler問題14 は、コラッツの問題から、百万以下で最も長い数列をもたらす数値を求めるもの。
 数値を与えて、コラッツの数列を求める関数は、再帰を使うと簡単に定義できます。

(define (collatz n lst)
  (push n lst -1)
  (if (even? n) (collatz (/ n 2) lst)
      (and (odd? n) (> n 1)) (collatz (++ (* 3 n)) lst)
      lst))

 newLISP の ifcond 的な記述ができるので、楽です(笑)。

> (collatz 13)
(13 40 20 10 5 16 8 4 2 1)
> 

 再帰を使うと見通しはいいですが、難点は速度。
 そこで、newLISP には豊富にある繰り返し関数から while を使って、再度定義してみます。

(define (Collatz n)
  (let (lst (list n))
    (while (> n 1)
      (if (even? n) (setq n (/ n 2)) (setq n (++ (* n 3))))
      (push n lst -1))
    lst))

 この程度なら、再帰と比べて見通しも悪くありませんし、早さは 5 ~ 6 倍違います。

> (Collatz 13)
(13 40 20 10 5 16 8 4 2 1)
> 

 これで、コラッツの数列を求める関数はできました。
 後は、百万回繰り返して、最長のリストを求めるだけ。

> [cmd]
(let (res)
  (for (i 1 1000000)
    (let (x (Collatz i)) (if (> (length x) (length res)) (setq res x))))
  res)
[/cmd]
(837799 2513398 1256699 3770098 1885049 5655148 2827574 1413787 4241362 2120681 6362044 
 3181022 1590511 4771534 2385767 7157302 3578651 10735954 5367977 16103932 8051966 
 :
 :
 4025983 12077950 6038975 18116926 9058463 27175390 13587695 40763086 20381543  911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 
 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1)
> 

 最長の数列の長さは 525 。繰り返し関数 for も newLISP では標準です。
 さて、問題の要求しているのは、数列の最初の数値 837799 だけですから、もう少し工夫して、

> [cmd]
(let (res '(0 0))
  (for (i 1 1000000)
    (let (x (length (Collatz i))) (if (> x (res 1)) (setq res (list i x)))))
  (res 0))
[/cmd]
837799
> 

 こんな感じ。

 以上、如何でしょうか?

projecteuler13...または、有効桁数について

 projecteuler問題13は、既にやっていますが、今回は番外編。
 大整数(big integers)が使えるようになった newLISP には簡単な問題ですが、求める答えが和の最初の 10 桁だけなら、大整数を使うまでもありません。
 組込関数 bigint前回bigint の代わりに eval-string を使っています)で大整数にせずとも、float を使って浮動小数点数で計算しても、こと足りるのです。
 何故なら、問題は高々 50 個の加算ですから、10 桁の値を得るには、12 桁の精度を保持しておけば十分です。そして、

> (format "%f" (float 37107287533902102798797998220837590246510135740250L))
"37107287533902104311025740304689820495323647180800.000000"
>

 このように、newLISP の浮動小数点数は 64 ビット長倍精度なので、16 桁くらいまでは精度が保たれます。つまり、問題13 は newLISP の浮動小数点数で十分対応可能です。
 浮動小数点数に変換したリストを入れた data を使って、結果だけ記せば、

> (apply add data)
5.53737623e+051
> (format "%f" (apply add data))
"5537376230390877287140145935443224959721771787878400.000000"
> (0 10 (format "%f" (apply add data)))
"5537376230"
> 

 こんな感じで、答えは合っています。
 まっ、大整数のある newLISP には要らぬことですが(笑)。
 今回の例ではピンと来ないかもしれませんが、技術計算では有効桁数を常に頭に入れて置くことが必須です。newLISP を使っていると往々にして忘れがちですが(汗)。
 ちなみに v.10.5.5 から、大整数の整数演算における引数が二つという制限がなくなり、ますます使いやすくなります。また、浮動小数点数の標準表記も 10 桁から 15 桁になるようです。詳しくは、こちらでどうぞ。

 以上、如何でしょうか?

フォロー

新しい投稿をメールで受信しましょう。