AtCoder の新環境テストの問題を解いてみる

Posted on 月 17 2月 2020 in 学習 • Tagged with Haskell, GHC, AtCoder, 競技プログラミング

AtCoder が現在新環境のテストをしている: https://atcoder.jp/contests/language-test-202001

今までの環境では GHC 7.10.3 だったのが,新環境では 8.6.5 になるので,この機会に参加してみるかということで,テストで公開されてる問題を解いてみた.そのコードと解説.なお,当方 AtCoder の …


Continue reading

State モナドの代わりに Reader モナドを使う

Posted on 木 30 1月 2020 in プログラミング • Tagged with Haskell, GHC, モナド

注意
この記事は公開当時主張に誤りを含んでいたため,大幅に書き直しています.また,公開当時の主張の誤りについても,付録として載せておきました.

Haskell で State モナドはモナドの代表格だ.Haskell 入門者は,多くの場合,状態を伴った計算を State モナドで書くことを習うだろう.しかし,実用上の多くの場面では,State モナドではなく他の選択肢を選んだ方がいい場合がある.一つの選択肢が,Reader モナドと可変参照を使う方法だ.今回は,この手法を使う利点と利用場面について考えていこうと思う …


Continue reading

多相関数を第一級で取り扱う

Posted on 金 06 12月 2019 in プログラミング言語 • Tagged with Haskell, GHC拡張, GHC, 多相関数

今回は,GHC拡張の一つ RankNTypes の紹介をしようと思う.もうちょっとちゃんとまとめたのをいつか Haskell-jp かどっかに投稿したいと思ってるんだが,時間が (さっさと書け).

さて, Haskell のプログラミングにおいて多相関数はかなり重要な役割を持つ.しかしながら,標準の範囲では多相関数自体を第一級の値として扱うことはできない.私たちに許されるのは,多相関数を定義することだけだ.まあ,それだけでもかなり有用なんだけど,多相関数を第一級で扱えると,色々プログラミングの幅が広がる.今回は,多相関数を第一級として扱うというのはどういうことか,そしてそれをするにはどうすればいいか,そうすることで何がうれしいのかを簡単に触れられたらと思っている.

多相関数を第一級で扱うとはどういうことか …


Continue reading

type family を使って再帰的 ADT をオープンにする

Posted on 日 17 11月 2019 in プログラミング • Tagged with Haskell, GHC, GHC拡張

元ネタは Trees that grow . Haskell では代数的データ型 (ADT) を使ってプログミングに使うデータ構造を定義し,その構造を操作することによりプログラミングを行う. ADT はパターンマッチが容易で,再帰的に定義でき,基本的に閉じた構造になっている.そのため便利な反面,その機能が保守で仇となる場合もある.この問題は古くから知られており,いくつかの解決策も提案されてきた.今回はこのうち,現在 GHC で採用されつつある type family を使った解決方法を紹介する.

なお …


Continue reading

リテラルをコンパイラ時にチェックする

Posted on 月 28 10月 2019 in フレームワーク • Tagged with Haskell, GHC, リテラル, GHC拡張

Haskell はいくつかのリテラルで型クラスを使用したオーバーロードを許容している.例えば,Haskell で 1 と書いた場合,この型は 1 :: Num a => a になり, Num のインスタンスを定義することで,リテラルに対する実体をユーザも制御できるようになっている.GHC拡張で文字列に対してのオーバーロードなども提供されている.ただ,提供するデータ型とリテラルによっては,プログラムが意図通りに動かなかったりクラッシュしてしまったりすることがある.これを事前にチェックする仕組みを,コンパイラプラグインで実装する方法を紹介する.

なお,環境として以下を想定している.

GHC …

Continue reading

Local Do と型クラス

Posted on 土 27 7月 2019 in プログラミング言語 • Tagged with Haskell, GHC, GHC拡張, do構文, 型クラス

現在, GHC に 線形型の提案 がされていて活発に議論されている.プロトタイプも ここ から利用可能だ. Docker イメージも利用可能なので,気軽に試せると思うので,ぜひ試してみてくれ.

さて,そんな線形型の提案の裏で,副産物として Local Do という拡張が提案されている.今回は,その拡張の紹介と最近思ってることのお話.

Local Do 拡張

Haskell の …


Continue reading

Call Arity と融合変換

Posted on 金 26 7月 2019 in プログラミング言語 • Tagged with Haskell, GHC, 融合変換, コンパイラ, 最適化

GHC は,最適化のため Call Arity と呼ばれるコード解析を行っている.この解析で,自由変数が何個引数を持っていいかを判定し,イータ展開を可能にする.リストにおける融合変換とも密接な関係のある解析だ.こいつの存在とどういうことをやっているかはだいたい知っていたんだけど,ちょっと詳しく知りたい事例があったので調べてみた.そのメモ.

なお元ネタは,Breitner (nomeata) 先生の Call Arity

イータ展開と最適化

Haskell は知っての通り関数型プログラミング言語なので,息を吐くように関数を第1級として使うし,標準ライブラリに無数の高階関数がある.関数は全てカリー化されていて …


Continue reading

GHC の線形型プロトタイプのお試し環境を作る

Posted on 金 28 6月 2019 in プログラミング言語 • Tagged with Haskell, 線形型, GHC, Docker

現在, GHC に 線形型の追加提案 が出ている.その提案に合わせて,プロトタイプも公開されている.内容はあまり詳しく追ってないけど,お試し環境は作ってみたのでその備忘録.

線形型プロトタイプ実装

線形型の提案は, GHC Proposals (https://github.com/ghc-proposals/ghc-proposals/pull/111) で議論されている. https://arxiv.org/abs …


Continue reading

GHC で LLVM を通したビルドを行う

Posted on 金 17 5月 2019 in 環境構築 • Tagged with Haskell, GHC, LLVM, macOS, Homebrew

GHC で LLVM を通してビルドをしたかったので,設定した.その備忘録.

macOS で LLVM を GHC が使えるようにする

GHC が対応してる LLVM のバージョンは,標準で入ってるのよりちょっと古くって,さらにバージョンごとにサポートされてる範囲が違う.各 GHC でサポートされてる LLVM のバージョンは,以下に載ってる:

https …

Continue reading

GHC IO モナドの中身

Posted on 金 17 5月 2019 in プログラミング言語 • Tagged with Haskell, GHC, IO

Haskell の IO モナドって,中身どうなってたんだろと気になってて,ちょっと調べてみた.そのメモ.

IO モナドと RealWorld

まずは基本から. IO モナドは, Haskell の根幹となるモナドで, main も IO で書く. GHC では中身は次のように定義されている [1]:

-- In GHC.Types …

Continue reading