型安全で高速な連鎖行列積の計算
この記事は Haskell Advent Calendar 2021 の22日目の記事です。 次のような３つの行列の積を考えてみましょう。 ABC = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ a_{30} & a_{31} & a_{32} \\ \end{pmatrix} \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \\ b_{20} & b_{21} \\ \end{pmatrix} \begin{pmatrix} c_{00} & c_{01} & c_{02} & c_{03} & c_{04} \\ c_{10} & c_{11} & c_{12} & c_{13}
閉半環を使ってグラフ上の最短距離を計算する！
この記事は Haskell Advent Calendar 2020 21日目の記事です。 以前の記事でトロピカル行列を使ったグラフの最短経路の求め方を解説しました。 ここではトロピカルな隣接行列の累乗を収束するまで繰り返すという方法で最短経路を計算しましたが、実は閉半環という代数を考えると直接的に最短経路を求める計算が可能になります。そこで今回はその方法について解説したいと思います。 以前はHaskellのリスト [a] をベクトルとして行列を実装しましたが、今回はそれだと実装が少し煩雑になるので型レベル自然数を型引数に持つ Vector n a を中心に実装していきたいと思います。この話は以下の Functional Pearl が元になっていますが、この論文もリストを使って実装されているので Vector n a を使ってどのように実装できるかはこの記事で新しく試したところです。 ト
圏論入門｜日本評論社
第1章 圏・関手・自然変換 1.1 集合と写像から 1.2 圏・対象・射 1.3 圏のデータ構造 1.4 関手・反変関手 1.5 忠実関手と充満関手 1.6 自然変換 1.7 Haskの部分圏 第2章 自然変換と圏同値 2.1 関手圏 2.2 圏同値 第3章 普遍性と極限 3.1 始対象と終対象 3.2 積 3.3 余積 3.4 極限 3.5 余極限 3.6 極限の存在 3.7 余極限の存在 第4章 関手と極限の交換 4.1 関手は錐や余錐を写す 4.2 Hom関手と極限 4.3 Hom関手と余極限 4.4 実行可能な例 4.5 極限を関手とみる 第5章 随伴 5.1 随伴とは 5.2 単位と余単位 5.3 三角等式 5.4 普遍射と随伴 5.5 随伴の同値な言い替え 5.6 随伴と圏同値 5.7 随伴の大局的な自然性 5.8 随伴と極限 第6章 モナドとHaskellのMonad 6.1
GitHub - konn/ghc-typelits-presburger: Presburger arithmetic solver for built-in type-level naturals
数式からいい感じに図表が生成できてしまう! Penroseを試す (SIGGRAPH 2020) - Qiita
Penroseとはなにか Penroseは、数式に近い数学的表現から、細かなパラメータの指定なく、いい感じに図表を生成してくれる、カーネギーメロン大発、SIGGRAPH 2020に採択されたプロジェクトです。以下に、論文より、自動生成された図表を抜粋します。 数式にとどまらず、コンピュータグラフィックスのメッシュ図示など、幅広い表現に使えます。 Penroseは、数式に近い数学的表現から、細かなパラメータの指定なく、いい感じに図表を生成してくれる、カーネギーメロン大発、SIGGRAPH 2020に採択されたプロジェクトです。 数式にとどまらず、コンピュータグラフィックスのメッシュ図示などにも使えます。 まずは筆頭著者のKatherine Ye氏のTweetにつけられた動画をご覧ください。 今日現在(2020.6.7)、紹介動画のPenrose Web IDEは未公開 (今後公開予定とのこと
Blazing fast Fibonacci numbers using Monoids
This post illustrates a nifty application of Haskell’s standard library to solve a numeric problem. The Fibonacci series is a well-known sequence of numbers defined by the following rules: In fact, that’s not only a specification of the Fibonacci numbers: that’s also valid Haskell code (with a few gratuitous parentheses to resemble traditional mathematical notation). However, that solution is inef
haskell の Int と Integer の違いや Float や Double や Rational を理解する - Qiita
先日プログラミングコンテストの過去問を haskell でやった時に、べき乗をなんやかんやするロジックを書いた時に最終結果が12340000で欲しかったのに12340000.0になってしまって通りませんでした。恥ずかしい。 恥ずかしいけど、聞くは一時の恥聞かぬは一生の恥の解説とも言うし、知らないことは素直に学んで修めればなかったことにできるんです。できんの？ よくわからんけど、要するに曖昧なまま使ってたIntみたいなものをきっちりまとめるぜって、そんな話。 かるーく背景 普段は java / DDD で契約管理のシステムを作ってるんだけど、扱う数字なんてたかだか数万の整数くらいなんだよね。ちょっとした円だとか契約の数を数えたりだとか、その程度。 なんと月の請求に日割りがないしね。驚きだね。 DDD の value object とかのおかげで、生のIntとかを触ることもあんまりないしね。
自動微分と区間演算で非線形関数の根を全て探索するアルゴリズム - Qiita
自動微分について調べていたら『精度保証付き数値計算の基礎』という本に出会いました。その中に非常に面白い応用が載っていたので紹介したいと思います。 allsol :: (RealFloat a, Ord a) => (forall b. Floating b => b -> b) -- 根を求める非線形関数 -> [Interval a] -- 探索する区間 -> [Interval a] -- 根が含まれている区間 これが今回紹介する、与えられた非線形関数$f$の与えられた区間における根、すなわち$f(x)=0$を満たすような$x$をただ一つ含む区間を全て探索してくれる関数（の型）です。実装を見る前にその威力を実際に使って確かめてみましょう。 > f x = (x - 1) * (x - 2) * (x - 3) > allsol f [-1e6...1e6] [ 0.9837477320
40行でPoisson方程式を解く - Qiita
こんにちは、やきつかです。 Haskellで配列を使ってみたいなーと思っていて、Poisson方程式を数値計算してみたら40行だったので1人で感動しちゃったので残しておきます。 Haskellの表現力の強さを知ってもらえればうれしいです。 注意 とりあえず実装したかったので、処理速度とかは一切考慮してないです。 同じ理由で、精度も可視化していい感じになることを目指しています。 Haskell、数値計算とも初学者なので、間違いとかよりよい作法がありましたら教えていただけると大変うれしいです。 はじめに この記事では、Poisson方程式の概要→差分方程式→アルゴリズム→Haskellで書いたコードという順で説明していきます。 Poisson方程式とは Poisson方程式は二階の偏微分方程式で、次の様に表されるもののことを言います。 $$\Delta\phi=f$$ ここで、$\Delta$
テンソル形状のコンパイル時検査＋実行時アサーション化を今のHaskellで書いてみる - Qiita
はじめに Edward Z. Yang 氏の記事 A compile-time debugger that helps you write tensor shape checks は、テンソルの形状の検査を依存型でコンパイル時に対話的にやりつつ、静的に決まらない部分や静的な検証が難しい部分はアサーションとして実行時検査に遅延するという仕組みの提案。 対話的なアサーションの挿入部分とかはともかく、型付けとアサーションの部分は今のHaskellでも大体出来るなぁと思ったので試しに書いてみた。 (元記事自体Haskellっぽい構文で書かれているし、 Edward Z. Yang 氏自身、ここまでは出来るのは当然知って書いているのだと思うけれど) 結果 元記事での、アサーションを挿入した最終的なプログラムは以下: main() { x = load("tensor1.t") y = load("t
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
natural-arithmetic
GitHub - ucsd-progsys/liquid-fixpoint: Horn Clause Constraint Solving for Liquid Types
GitHub - michalkonecny/cdar
GitHub - nilsalex/safe-tensor: dependently typed tensor algebra in Haskell
Competitive Programming in Haskell: primes and factoring
AC-Angle
GitHub - Bodigrim/mod: Modular arithmetic, promoting moduli to the type level
GitHub - ekmett/linear: Low-dimensional linear algebra primitives for Haskell.
GitHub - msakai/extended-reals: Extension of real numbers with positive/negative infinities (±∞)
自動微分を実装して理解する（前編） - Qiita
