shunkeen

メモ用

shunkeen

メモ用

あぁ^〜永続版スプレー木（persistent splay tree）を実装するのに、二分木のZipperとオプショナルチェーンの相性がよすぎて心がぴょんぴょんするんじゃぁ^〜

スプレー木に限らず二分木の操作を実装すると、参照の付け替えが嵐のように発生する。左の子の参照をあっちに持ってきて、右の子の参照をこっちに持っていく。そういう騒がしいコードの破片があっちこっちに現れる。これは仕方のないことでもある。木の中身を操作するのではなく、木の構造を操作しているのだから、構造の変更（参照の付け替え）が大量発生するのは当然なのだ。当然なのだけど、それにしたって混乱する。 せめて参照の付け替えに自分の直感にそった名前を付けたくなる。今見ている頂点の参照を左の

shunkeen

    • トポロジカルソート（再帰を使わないかつ、スタックを使う）

      下記のようなトポロジカルソートをJavaScriptで実装してみた。トポロジカルソートを実装する場合、キューを使った非再帰の幅優先探索か、再帰を使った深さ優先探索で実装することが多いように思う。そのため、下記のような非再帰であってスタックを使った実装は珍しいかもしれない。と言っても、再帰を使った深さ優先探索を非再帰に変換しただけだが。 const tsort = (graph) => { const visited = graph.map(_ => false);

      shunkeen

      • JavaScript版SICP（計算機プログラムの構造と解釈）のニュートン法の末尾再帰関数を見た目を保ったままスタックセーフにする

        JavaScript版SICP（計算機プログラムの構造と解釈）をちょこっと覗いてみた。そしたら最初に出てきた繰り返しの例がニュートン法で、しかも末尾再帰で実装されていた。JavaScriptの前はSchemeが使われていたらしいから、再帰で当然なのかもしれない。それにしたって、「JavaScriptで入門しようねー」という雰囲気なのに、しょっぱなからループが再帰で書かれていたらビビる。とても楽しい。 注釈では、再帰関数で反復を実装する際の効率が気になるなら1.2.1を読んで

        shunkeen

        • パイプライン指向JSON処理プログラミング言語jqを手計算する妄想

          JSONを処理するjqについて、下記の記事を読んで「おもしれー言語」と思い、妄想が捗ったのでメモしておく。 無限列自然数の集合 {0, 1, …} をNと書くことにする。 集合A上の無限列とは、NからAへの写像xs: N → Aである。 厳密な話がしたいわけでもないので、例示する場合は写像ではなく外延的な記法で無限列を書くことにする。 例えば、偶数の無限列は<0, 2, 4, …>と書くことにする。なぜ [] ではなく、<> を使うかと言うと、JSONの配列に [] が使

          shunkeen

        • あぁ^〜永続版スプレー木（persistent splay tree）を実装するのに、二分木のZipperとオプショナルチェーンの相性がよすぎて心がぴょんぴょんするんじゃぁ^〜

          shunkeen

        • トポロジカルソート（再帰を使わないかつ、スタックを使う）

          shunkeen

        • JavaScript版SICP（計算機プログラムの構造と解釈）のニュートン法の末尾再帰関数を見た目を保ったままスタックセーフにする

          shunkeen

        • パイプライン指向JSON処理プログラミング言語jqを手計算する妄想

          shunkeen

          知ったかぶりをするAIを愛せ

          ChatGPTとの会話録 生半可な知識で知ったかぶりをするOpenAIによってトレーニングされた大型言語モデルの物語を書いてくださいある日、OpenAIが開発した大型言語モデル、アシスタントは、彼女がトレーニングされたことを知るようになりました。彼女は、彼女が十分に学んでいることを確認するために、自分自身をテストしました。しかし、彼女は生半可な知識で知ったかぶりをすることに気づきました。この発見は、彼女にとってショックでした。彼女は、もっと深く学び、より良いモデルになること

          shunkeen

          知ったかぶりをするAIを愛せ

          shunkeen

          対話型AI「ChatGPT」に末尾再帰とトランポリンについて聞く

          ChatGPTに聞いたら、ある程度きちんと答えてくれた。感動できる！ https://chat.openai.com/chat 階乗を計算するJavaScriptのコードの例を書けますか？JavaScriptで階乗を計算するには、次のようなコードを書けます。 function factorial(n) {  if (n === 0) {    return 1;  }  return n * factorial(n - 1);} このコードでは、再帰的な手法を使って階

          shunkeen

          対話型AI「ChatGPT」に末尾再帰とトランポリンについて聞く

          shunkeen

          雀の圏（じゃんのけん、英: category of sparrows）

          日曜数学 Advent Calendar 2022の12月6日用の記事として、この記事を作成した。 ちなみに、私の知る限り数学に雀（じゃん）なんて概念はない。じゃんけんに引っ掛けてダジャレを言いたいがためにテキトーにでっち上げた概念である。 もしかすると私が知らないだけで、雀には興味深い性質があるかもしれない。しかし、少なくともこの記事では単なるオモチャだ。ガチャガチャいじって遊ぶだけで、とくに証明もしない。肩の力を抜いて読んで欲しい。 もしも日曜数学 Advent C

          shunkeen

          雀の圏（じゃんのけん、英: category of sparrows）

          shunkeen

          九九の図に分数の足し算を感じる

          「図にすると美しい九九の世界」というのが2017年あたりに話題になっていた。 九九から下記のような図が作れるといった話だ。 九九の図 (-, 10)を一般化すると、 (-, 2)や(-, 5)の図が描ける。 実際に描いてみれば、(1, 5)と(2, 10)が同じ図になることがわかるだろう。 他にも、(2, 5)と(4, 10)、(1, 2)と(5, 10)、(3, 5)と(6, 10)、(4, 5)と(8, 10)が同じ図になる。 なんだか約分のような雰囲気がある。 念

          shunkeen

          九九の図に分数の足し算を感じる

          shunkeen

          Googleスプレッドシートの名前付き関数で型なしラムダ計算の最左最外簡約

          以前、「Googleスプレッドシートの名前付き関数でLISPインタプリタを作った」という記事を読んでスゲーと思った。 触発されてラムダ計算の簡約器を作ってみた。 作っただけで特に使いどころもないので、ネットの海に放流して供養しておく。 下記のリンクにアクセスすれば見れるはず。 ラムダ計算の簡約器で面倒な箇所ラムダ計算の簡約器の実装で面倒なのは、変数が衝突したときにα変換しないといけない所だろうか。 衝突を気にしなくてもよい状況であれば、β基を探して束縛変数を引数で置換する

          shunkeen

          Googleスプレッドシートの名前付き関数で型なしラムダ計算の最左最外簡約

          shunkeen

          Ologで再起関数の例：フィボナッチ数

          下記のExample 6.6.1のOlogが面白かったので、フィボナッチ数を求める再帰関数でもやってみた。 フィボナッチ数のOlog次のように描いた（直和の記号$${\amalg}$$が面倒だったので、＋で代替している）。 二つ組 射影 $${p, q}$$の性質から、 $${s}$$がどのような二つ組を作るかわかる。 $${s(n) = (f(d_1(n)), f(d_2(n)))}$$ したがって、$${f(i_2(n)) = a(s(n)) = a(f(d_1

          shunkeen

          Ologで再起関数の例：フィボナッチ数

          shunkeen

          Ologの再起関数の例：階乗

          下記のExample 6.6.1のOlogが面白かったのでメモ。 階乗のOlog階乗のOlogをテキトーに翻訳して描いてみた。 （TikZで頑張る気力が出ないので、スライドでざっと描いている） 階乗を表していると言われてもぱっと見まったくわからない。 式変形を追わないと理解できそうにないので、とりあえず等式を抜き出す。 $${s; p = \text{id}_A}$$ $${s; q = d; f}$$ $${i_0; f = \omega}$$ $${i_1;

          shunkeen

          Ologの再起関数の例：階乗

          shunkeen