自動微分を実装して理解する（後編） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はFOLIO Advent Calendar 2018、21日目の記事です。昨日はhajipionによる大規模デザインカンファレンス「デザインシップ」の着想から開会まで、超ダッシュで振り返る10ヶ月！ #Designship2018でした。 この記事は近年話題に上がることが多くなってきた自動微分を実際に実装することでより理解を深めようというものです。前回の自動微分を実装して理解する（前編）では自動微分の定義とフォワードモードの実装を見てきました。今回はリバースモードの自動微分の実装にチャレンジしてみましょう。 リバースモード 現
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdo
HaskellDay2016_sakai
SAT/SMT solving in Haskell Masahiro Sakai ( ) Haskell Day 2016 2016-09-17 Self Introduction Masahiro Sakai Twitter: @masahiro_sakai github: https:/ /github.com/msakai/ G+: https:/ /plus.google.com/+MasahiroSakai Translated “Software Abstractions” and TaPL into Japanese with colleagues Interests: Categorical Programming, Theorem Proving / Decision Procedures, … Agenda What are SAT and SMT? Haskell
なぜ Haskell ではキューが軽んじられているか？ - あどけない話
Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(><)や分割(splitAt)が、ならし計算量で O(log N) という優れものである。しかし、内部がfinger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。 もっと単純で、最悪計算量を保証する(両端でない)キューが標準で提供されてもいい気がする。その候補には、リアルタイムキューがある。どうして標準でキューが提供されないのだろう？ 僕なりの答えは「需要がない」だ。 問題を解くときにスタックはよく使うが、キューが必要な問題はそんなに思いつかない。僕はネットワーク屋なので、もちろんルータにはキューが必要なことは知っているが、それ以外で有名どころと言えば幅優先探索ぐらいだ。 幅優先探索 でも、Haskellではキュー
再帰ドリル(1)：数値に対する素朴な再帰 - あどけない話
注意：github に移動しました。 再帰を学ぶためのドリル。使用するプログラミング言語は Haskell。このシリーズは続くかもしれないし、途中で挫折するかもしれない。乞うご期待！ 等差数列の和 差が1の等差数列の和を計算する関数 soap(sum of arithmetic progression) を考える。 soap 0 = 0 soap 1 = 0 + 1 soap 2 = 0 + 1 + 2 soap 3 = 0 + 1 + 2 + 3 soap 4 = 0 + 1 + 2 + 3 + 4 一歩手前を使うとどうなる？ soap 0 = 0 soap 1 = soap 0 + 1 soap 2 = soap 1 + 2 soap 3 = soap 2 + 3 soap 4 = soap 3 + 4 再帰部を一般化するとどうなる？ soap 0 = 0 -- 基底部 soap n
Things that amuse me
Quicksort in Haskell Quicksort is a commonly used example of how succinct Haskell programming can be. It usually looks something likes this: qsort :: (Ord a Bool) => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs) The problem with this function is that it's not really Quicksort. Viewed through sufficently blurry glasses (or high abstraction altitu
Haskellでメモ化する（中級）
前回のpostで、Haskellでメモ化する方法について書きました。そのとき、疑問点として、「なんで、メモ化と不動点が繋がってるねん！なんでやねん！」というのがありました。その疑問が解決したので中級編を書きます。 どうやら不動点コンビネータを利用してやりたいことは、「任意の関数が与えられたときに、その計算をメモ化する関数を作成する」ということのようです。この発想にはびっくりです。どれだけ抽象度の高いことをやるんだよ。という感じです。imparative、あんど、object-orientedな思想に育てられた（毒された？）普通のプログラマーである私には思いもよらない発想でした。。
Haskellでメモ化する（初級）
1つは、参照透明性による壁。Haskellには副作用がないため、再代入ができない。つまり、メモ化する対象を更新していくというような作業ができないのです。外部変数を用意して、その外部変数に計算した値を格納していくという方法は通じないのです。。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
自動微分を実装して理解する（前編） - Qiita
GitHub - jaspervdj/psqueues: Priority Search Queues in three different flavors for Haskell
Programming Praxis – Dijkstra’s Algorithm
How to implement Dijkstra Algorithm in Haskell