xiangzeのブックマーク - はてなブックマーク

超関数型プログラミング
この記事はFOLIO Advent Calendar 2022の23日目です。ソフトウェア2.0 ソフトウェア2.0 という新しいプログラミングのパラダイムがあります。これは Tesla 社のAIのシニアディレクターだった Andrej Karpathy が自身のブログ記事（"Software 2.0"）で提唱した概念で、ニューラルネットワークのような最適化を伴うプログラムを例に説明されています。従来のプログラム（Software 1.0）は人間が命令に基づいたプログラムを作成し、望ましい挙動を行わせます。それに対してニューラルネットワークのようなプログラム（Software 2.0）では人間はある程度の自由度をパラメータという形で残したプログラムを作成し、「入出力のペア」や「囲碁に勝つ」というような教師データや目的を与えてプログラムを探索させるというものです。画像出典: "So
xiangze 2022/12/30
programming
リンク
Levelsモナドを使った幅優先探索の仕組み
Haskellは関数型プログラミング言語と呼ばれますが、関数だけでなく型も重要な役割を担っています。アルゴリズムを考える時、手続きの最適化だけでなく、正しいデータ型を選択することがシンプルなアルゴリズムを導き、実装をコンパクトにできるというのはよくある話です。今回は非常に単純な型でありながら幅優先探索というアルゴリズムのエッセンスを詰め込んだ Levelsというデータ型について紹介したいと思います。ピタゴラス数を列挙するピタゴラス数とはピタゴラスの定理における関係式 a^2 + b^2 = c^2 を満たす自然数の三つ組です。 Haskellのリストは遅延評価なので全ての自然数の三つ組を列挙する列挙した自然数の中から関係式を満たすものだけ抽出するという手順でピタゴラス数を列挙することを考えてみましょう。実際この方法は有限な探索範囲ではうまく機能します。 pyth :: [(I
xiangze 2021/09/03
haskell

algorithm
リンク
グラフからコミュニティ構造を抽出する〜リッチフローによるグラフの時間発展〜
コミュニティ抽出とは簡単に言えばグラフにおけるノードのクラスタリング手法です。具体的なアルゴリズムとしてはGirvan–Newman法をはじめ様々なアルゴリズムが存在しますが、この記事では去年（2019年）提案された新しい手法について解説したいと思います[1]。 [1907.03993] Community Detection on Networks with Ricci Flow 話の元になっているのはこちらの論文で、グラフをリッチフローによって変形し、伸びたエッジを切断していくことでクラスタを求めるというアルゴリズムです。リッチフローという聞き慣れない言葉が出てきましたが、ちゃんと後で説明するので気にせず進めましょう。まずは実際にグラフのクラスタリングを行う様子をアニメーションで見てみてください。アルゴリズム自体はそれほど難しくありませんが、背景を含めて理解するためには2つの理論
xiangze 2020/12/26
haskell

graph

数学
リンク
1