おじいさん、今日のご飯はCatamorphismですよ - Qiita
100年ぶりにポエムを書きます。 F代数から出発して、最終的にはCatamorphismを理解することを目指します。 F代数 ある関手Fに対して、対象と射の組 $(A, a : F(A) \rightarrow A)$ のこと。
挿入ソートと選択ソートは双対 - Qiita
先日 Gotanda.hs #1 @HERP というイベントがあって、そこでRecursion Schemesで考える並べ替えアルゴリズムというタイトルでA Duality of Sortsという論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている挿入ソートと選択ソートの双対性について書いていきたいと思っています。 ソートアルゴリズムの復習 まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。 挿入ソートは与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。 出典: Insertion sort - Wikipedia これをHaskellで実装すると以下のようになります。 insertSort :: [Int] -> [Int] inser
代数的データ型とF代数 - Qiita
$\require{AMScd}$ はじめに Haskellを勉強していると諸々の概念と圏論の繋りが気になってきます。今回は代数的データ型について圏論との関係を述べます。 なお、面倒なので圏と関手、直積、直和はわかっているものとして話しを進めます。 自己関手$F : C \to C$について$F$代数とは$C$の対象$A$と$C$の射$a : F(A) \to A$の組$(A, a)$のことです。このとき$F$代数$(A, a)$と$(B, b)$の間の射とは$C$の射$f : A \to B$であり、以下の図を可換にするものである。
F-Algebras
This is part 24 of Categories for Programmers. Previously: Comonads. See the Table of Contents. We’ve seen several formulations of a monoid: as a set, as a single-object category, as an object in a monoidal category. How much more juice can we squeeze out of this simple concept? Let’s try. Take this definition of a monoid as a set m with a pair of functions: μ :: m × m -> m η :: 1 -> m Here, 1 is
F-algebras or: How I Learned to Stop Worrying and Love the Type System
Speaker: Anthony Burzillo New York Haskell Meetups (https://www.meetup.com/NY-Haskell/events/235377469/) F-algebras are a concept in Category Theory that deal with data structures that can be used as functors. In essence, F-algebras allow the programmer to reduce complicated recursive evaluation schemes into simple rules where the lower-level elements can be thought of as already evaluated, so t
Understanding F-Algebras - School of Haskell | School of Haskell
Interactive code snippets not yet available for SoH 2.0, see our Status of of School of Haskell 2.0 blog post What is algebra? Naively speaking algebra gives us the ability to perform calculations with numbers and symbols. Abstract algebra treats symbols as elements of a vector space: they can be multiplied by scalars and added to each other. But what makes algebras stand appart from linear spaces
F-algebra と catamorphism を Haskell で理解する(2) - らむだ畑でつかまえて (catcher in the λ)
前回の続き。 wikipedia の F-algebra のページ http://en.wikipedia.org/wiki/F-algebra 参照。 上記ページに F(X) = 1 + X という関手の F-algebra の例で (N,[zero,succ]) が出てくる。Haskell で書くと type N = Int a :: Maybe N -> N a Nothing = 0 a (Just x) = x + 1 本当は N は自然数なので負の数も入っている Int とは違うけれどここでは Int でごまかしておく。 a Nothing = 0 の部分が zero に、a (Just x) = x + 1 の部分が succ に対応する。 さて F-algebra (N,a) から別の F-algebra (B,b) b :: Maybe B -> B に対する射 f はど
F-algebra と catamorphism を Haskell で理解する - らむだ畑でつかまえて (catcher in the λ)
wikipedia の F-algebra のページ http://en.wikipedia.org/wiki/F-algebra 参照。 上記ページに集合圏から集合圏への関手F として F(X) = 1 + X という例がでてくるが 1 + X は Haskell では Maybe X である。 Maybe の定義 data Maybe a = Nothing | Just a の「Nothing」が「1」に、「|」が「+」に、「Just a」 が「X」にそれぞれ対応する。 F(f) は fmap f である。 F-algebra の説明にでてくる A を Bool、B を Int とし a :: Maybe Bool -> Bool a Nothing = False a (Just x) = x b :: Maybe Int -> Int b Nothing = 0 b (Just
F-Algebras for expression evaluation | burz.io
Feval: F-Algebras for expression evaluation Using f-algebras to produce a statically typed functional programming language A few months ago, I stumbled upon the article Understanding F-Algebras by Bartosz Milewski. After reading the article I became interested in trying to implement a functional programming language using f-algebras. The result was the statically typed functional programming langu
You Can’t Make an Algebra without Breaking a Few Eggs
You Can’t Make an Algebra without Breaking a Few Eggs Posted by Bartosz Milewski under Category Theory, Functional Programming, Haskell, Monads, Programming [6] Comments In my previous post I worked on stretching the intuition of what a container is. I proposed that, in Haskell, any functor may be interpreted as some kind of container, including the hard cases like the state functor or the IO func
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Reddit - Dive into anything
Review: Sorting with Bialgebras and Distributive Laws :: Reasonably Polymorphic
https://github.com/burz/presentations/blob/master/f-algebras/slides.md
Reddit - Dive into anything
Catamorphisms, part eight