この記事は Haskell Advent Calendar 2023 の7日目の記事です。 zip関数について Haskellには zip 関数というものがあります。この関数は、2つのリストを受け取って、それぞれから取り出した要素を組にしたリストを返します。
前回の記事は魔法のように見えるStateモナドの実装も、順を追って見ていけば理解することは難しくないという話でした。 しかし状態の変更を順番に処理するというような手続き的な考え方にかなり近い構造が、うまくモナドになってくれるというのは少し不思議ですよね。 この記事では タプル (a, b) 関数 a -> b カリー化 curry :: ((a, b) -> c) -> a -> b -> c uncurry :: (a -> b -> c) -> (a, b) -> c といったHaskellの基本的な要素が随伴と呼ばれる関係を構成することを見て、 その随伴からStateモナドが導かれることを説明していきたいと思います。 随伴 二つの圏 C, D と二つの関手 F : C \rightarrow D, G : D \rightarrow C が与えられたとしましょう。 もし GF = {
第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
Codensity という型がある. 定義は以下. newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b } instance Functor (Codensity k) where fmap f (Codensity m) = Codensity (\k -> m (k . f)) instance Monad (Codensity f) where return x = Codensity (\k -> k x) m >>= k = Codensity (\c -> runCodensity m (\a -> runCodensity (k a) c)) これの何が良いかと言うと, これは以下のようにMonadFreeな作用を持つ. instance (Functor f, Mon
Programming with Universal Constructions Posted by Bartosz Milewski under Programming 1 Comment As functional programmers we are interested in functions. Category theorists are similarly interested in morphisms. There is a slight difference in approach, though. A programmer must implement a function, whereas a mathematician is often satisfied with the proof of existence of a morphism (unless said
class Functor m => Monad m where return :: a -> m a (>>=) :: (a -> m b) -> m a -> m b join :: m (m a) -> m a join = (>>= id) k >>= m = join $ fmap k m extract は return と、extend は >>= と、duplicate は join と、それぞれなんとなく反対になってるような気がしますよね?(m と w も上下反対の対応がありますねw) コモナドの感覚を掴むために具体的な実装を見てみましょう。 -- | List Zipper data Z a = Z [a] a [a] left, right :: Z a -> Z a left (Z (l:ls) c rs) = Z ls l (c:rs) right (Z ls c
Hask圏 Haskellをラムダ計算とみなした時のsyntactic categoryをHask圏というのがよく言われる定義である(と思う)。 Haskellのtypeをobject, hom(A,B) をjudgement x:A |- M:B 全体(を適当な同値関係で割ったもの)とみなして圏を作る(このときしばしばjudgementとこのjudgementから作ったfunction λx.M を区別しない)。 さて基本的な結果として次のことが知られている。 Hask#Is Hask even a category? Hask is not a category というわけでHask圏は圏にならないのでそのようなものは存在しない。 Why not? これはundefinedというヤバイ元の存在とcall-by-needの悪魔的評価規則が合わさりこのような現象が生み出される。 主にこの2
層とプログラミング はじめに Haskellは、モナドという圏論用語を言語仕様に採用した初めての実用プログラミング言語です。歴史的には、Godementが1958年に、層コホモロジーの計算のため使ったのが(コ)モナドの最初の例だと言われています。 層は何らかの空間の「形」を代数的に計算するための仕組みで、局所的な性質と大域的な性質の関係を圏論的に表現するフレームワークと言えます。 一言で言えば、層とは関数とその定義域の組の集りのようなものです。いろいろな大きさの鉱物の結晶が積み重なって、地球全体を地層が覆っている様子をイメージするとわかりやすいかもしれません。層を使うと、定義域が重なりあう部分関数の関係と、それらが全体に波及していく様子を、圏論的に、すっきり表すことができます。 層はいわゆる"幾何的論理(geometric logic)"のモデルでもあり、実はモナドも幾何的論理で表現できる
Functor(関手)の話です。 HaskellのFunctorクラスはHask圏からHask圏への関手しか表現できません。 そこで、Hask圏以外の圏についても使える関手のクラスを書いてみました。 よろしくね (*´σー`)エヘヘ 基本的な用語と、HaskellのFunctorクラス 別のところにまとめました この章に書こうとしていた、「基本的な用語の確認とHaskellのFunctorクラス」についての内容は、別の記事にまとめさせて貰いました。 内容としては、「HaskellのFunctorクラスはHask圏からHask圏への関手しか表現できません。」という文章の説明なので、それを読んで「そらそうだろ」って感じなら読み飛ばして次の章を読んで頂いて大丈夫です。 HaskellのFunctorは、Hask圏からHask圏への関手を表現しています。 しかし、HaskellではHask圏以外の
圏論の歩き方 作者: 圏論の歩き方委員会出版社/メーカー: 日本評論社発売日: 2015/09/09メディア: 単行本この商品を含むブログを見る オフィスの机の上に新たな挑戦状(上記の本)が置いてあったので読んでみると、Kleisli tripleとMonadの関係が説明されていて、「そういえば、Kleisli tripleとMonadの同値性って、ちゃんと証明したことなかったなー」と思って書き始めたのがこのエントリーです。 いったい何の寝言を言ってるのかと思われそうですが・・・ HaskellのMonadを圏論の言葉に置き換えて理解する際に、圏論における「Kleisli triple」に対応させる方法と、圏論における「Monad」に対応させる方法があります。圏論の世界で「Kleisli triple」と「Monad」は互いに変換可能なので、どちらを用いても理論的には同じなのですが、Has
どうもこんばんは、south37です。今日も引き続きHaskellネタでいこうと思います。Functorって概念を知ったので、ちょろっとまとめてみたいと思います。 そもそも、Functorってなんですか? さて、Functorって聞いて、ピンと来ますか? 僕は、全然ピンと来ませんでした。Wikipedia先生の定義を見ても、 関手(かんしゅ、functor)とは、圏の間の対応付けのことである。関手は対象関数と射関数の組からなる。 などと、何だかよくわからない感じで書かれています。 じゃあ一体なんなんだって話ですが、ポイントはどうやら「対応付け」って点のようです。「圏(と呼ばれるよく分からないモノ)」から「圏」への対応付けをしてくれるのが、Functorです。そうすると、今度は「圏」がなんなんだって話になる訳ですが、これもWikipedia先生によれば 数学における圏(けん、category
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く