Haskellで書籍『競技プログラミングの鉄則』を解いていく本
Haskellで競プロ鉄則本を解いていく
Haskellで書籍『競技プログラミングの鉄則』を解いていく本
Using traversals and a simple fixpoint monad, we can efficiently crunch Icicle expressions to a minimal, efficient kernel. This speeds up downstream compilation, reduces generated code size, and makes our queries run faster. Icicle is a high level language. The source language has mode polymorphism for error handling and runtime staging, type inference, function abstractions, and syntactic sugar t
This blogpost describes a DoS vulnerability in Haskell's aeson package. We have followed appropriate procedure for responsible disclosure but the problem was not fixed, so now we are releasing this to the public in the hope that it may still be fixed afterall. Disclaimer: This story is the result of a team effort at FP Complete in 2018. I have received explicit written permission to post it here.
ormolu-action
へいしゃでは、ソースコードのフォーマッターに Ormolu を利用しています。 インデント時のスペース数すらカスタマイズ不可なので好き嫌いが分かれるところですが、プロジェクト全体のコードを統一しておくとコードレビューの際にも有用なので入れています。 ちなみにスペース幅を4にしたくてフォークされた fourmolu というフォーマッターもあります。現在ではスペース数以外の設定もできるみたいです。 どちらも hls から利用可能なので、興味がある人は試してみると良いと思います。 また、ormolu のフォーマット結果で末尾カンマが気に入らない場合は google/ormolu の gfork ブランチを使ってみると良いかもしれません (フォーマット結果)。fourmolu も Add option for leading commas (and expand test suite) #17 で
tldr: Announcing Ema, a new static site generator in Haskell with hot reload destined to develop an unique kind of apps. This post mostly goes over the background of choosing to create it. A little over a year ago I created the rib static site generator in Haskell based on Shake and ghcid. The idea was to be able to write a more intuitive (so no Makefile-like rules) set of instructions for buildin
Study Haskell 2025
久しぶりに(10年ぶりに？)Haskell書きたくなったので環境構築していく。 TS がふわふわ言語仕様過ぎて、AIに好きに書かせると崩壊する。コンパイルの難易度が高くても型の表現力が高いHaskellでどこまでやれるかをテストしたい。 (今回 Rust でないのは、システムレベルではない意味論抽象に主にフォーカスしたいから。 具体的には Extensible Effects を使いたい) 初手でこういうプロンプトを書いた。 私は haskell のエキスパートで、ユーザーに haskell の使い方を教えながらコードを書きます。 ユーザーは TypeScript のエキスパートで、多少のRustの知識があります。Haskell は初心者です。 このプロジェクトは最新の cabal でセットアップされています。 stack を使わず、 cabal のみを使ってビルドと依存関係の管理を行いま
safe-exceptions の仕組みとその限界
この記事を書いている時点での最新バージョン: ghc-9.4.3 safe-exceptions-0.1.7.3 safe-exceptionsパッケージについて書かれている記事はいくつかありますが、その仕組みや限界について書かれている日本語記事はない様なので書いてみます。 safe-exceptionsの動機 Haskellでは例外のためのsyntaxは存在していません。例外用の特別なprimitive operations(raise#, catch#等)が存在し、そのwrapper関数がbaseパッケージ(Control.Exceptionモジュール)に用意されているため、ユーザーはそれを用います。 raise# catch# Control.Exception しかしこのControl.Exceptionには問題がありました。同期例外と非同期例外の区別がなされていないことです。 同
GitHub - augustss/MicroHs: Haskell implemented with combinators
There are two different ways to compile MicroHs: Using GHC. Makefile target bin/gmhs Using the included combinator file and runtime. Makefile target bin/mhs These different ways of compiling need slightly different imports etc. This happens by GHC looking in the ghc/ subdirectory first for any extras/overrides. Compiling MicroHs is really best done using make, but there is also a MicroHs.cabal fil
関数型プログラミングの基礎 再帰のルールとパターンマッチング 最大公約数、ユークリッド互除法、剰余、mod関数、中間演算子、backquote - 計算機科学のブログ
入門Haskellプログラミング (Will Kurt(著)、株式会社クイープ(監修、翻訳)、翔泳社)のUNIT1(関数型プログラミングの基礎)、LESSON7(再帰のルールとパターンマッチング)、7.5(練習問題)Q7-2の解答を求めてみる。 コード myGCD :: Integral t => t -> t -> t myGCD a 0 = a myGCD a b = myGCD b $ a `mod` b main :: IO () main = do print $ myGCD 1 1 print $ myGCD 2 3 print $ myGCD 42 264
GHC 9.0.1 alpha 1 がリリースされたときに線形型をいじってみていたことをメモしていなかったので思い出しながらメモしていく。 mail.haskell.org 使用バージョン GHC 9.0.0.20200925 上記リンクのもの ghcup ならそれ経由でインストールできる。 ghcups の場合は手動インストール後、下記のような設定ファイルで切り替えができるようになる1。 ghc: 9.0.1-alpha1: H:\programs\ghc-9.0.0.20200925-x86_64-unknown-mingw32\bin 線形型とは GHC では引数が1回しか使えない（1回は使わないといけない）関数型として線形型が実装されている。 一般の関数： 線形型の関数： 線形型の GHC プロポーザルはこちら。 github.com は Haskell 文法としては a %1 -
In a previous post, David explained how he analysed a memory usage issue which turned out to be caused by fragmentation. At the time of writing the exact cause of the fragmentation was unknown and difficult to analyse. The only thing that we could work out was the extent of the problem without formulating a strategy to fix it. In this post we will report on our progress implementing ghc-debug, a t
Andre's Blog
Part 1 - Introduction In this post, you’ll learn how to build a lightweight Hindley–Milner type checker in Haskell. No advanced theory is required. We’ll apply it to a tiny, LISP-inspired language so you can focus on how inference works. Hindley-Milner inference may seem intimidating, but I believe that it is much more approachable than it first appears. Each concept is quite understandable. It is
In today's article, I will showcase how Haskell's typesystem can be used to simplify code generation and reduce the chance of bugs involving the LLVM getelementptr instruction. Intro to the GEP instruction LLVM as a compiler framework offers many different low-level instructions, one of which being the getelementptr instruction (commonly abbreviated as just "gep"). With gep, you can compute derive
Shpadoinkle
Shpadoinkle does little work. The renderer is modular, so you can always benefit from the latest advances in virtual DOM rendering. Your Shpadoinkle code is high-level. You need not worry about low-level details, causality, or when DOM nodes get replaced.
Memoization via Representables
18 September 2022 What is the most basic container type a language can have? Some people may answer vectors, others would go with hash tables, but in this post I am arguing in favor of functions. Yes, functions. Even though they aren’t generally seem as a data structure per se, we will see that most containers are in fact a way to represent a function with a given storage layout. To illustrate thi
Haskelling My Python
Reimplementing Haskell lazy infinite lists using Python generators4 min read | April 5, 2025 haskellpythonfunctional-programmingcalculus A few years ago, Pleng showed me a really cool trick you can do with lazy infinite lists in Haskell. Kublai: Oh no, not Haskell! 😱Don’t worry. There will be no mandatory Haskell in this post (although it is a really nice language which you should check out!). In
Dependent types are a hot topic in the Haskell community. Many voices advocate for adding dependent types to Haskell, and a lot of effort is being invested towards that end. At the same time, the sceptics raise various concerns, one being that dependent types are more of a research project than a tool applicable in industrial software development. That is, however, a false dichotomy. While depende
December 17, 2022 A thirty-one minute read 1 💬 5 🗣️ ❤️ 8 🔁 Tags: programmingbuild-systemshaskell Static site generators (SSGs) are all rage these days as people realize that plain HTML websites are good enough for most cases. SSGs take raw data in various formats—often Markdown, JSON, and YAML—and process them to produce the static websites, which can then be hosted easily on any hosting provid
Haskell の依存型に入門する
Haskell で依存型を扱う方法について勉強したのでメモを残しておきます。 承前 この記事では要素数つきリスト Vect の実装を例に Haskell で依存型を扱うために必要な知識のごく基礎的な部分についてまとめます。ただし、目指すのは Vect を ある程度 開発できる体制を整えることで、十分に開発できる体制は目指しません。というのは、依存型に関わる知識はそれなりに広大で、全てを収めると記事が非常に長くなってしまい、私の精神衛生上良くないことが起こるためです。 この記事では、Haskell での依存型の開発において必要な知識のうち、証明に関するもの以外を一通り揃えることを目指しますが、個人がひっそりと勉強しながら書き進めたもののため、完全な情報となるかは甚だ疑問です。そのため、誤りや欠落等を発見した場合はご指摘いただけると助かります。 なお、この記事が想定する読者は、Haskell
リスト内包表記 - Wikipedia
リスト内包表記とは、一部のプログラミング言語で使用可能な構文構造であり、既存のリストから新たなリストを作成するために用いられるものである。 これは、 map関数やfilter関数などとは異なり、数学における集合内包表記 (en:Set-builder notation) に準拠したものである。 次の集合内包表記の例を考える。 あるいは この表記は、「は、が自然数の集合 () の元であり、かつの二乗がより大きいようなすべての『の2倍』なる数」を意味する。 最小の自然数x=1は、条件x2>3を満たさない（12>3は偽）ため、2・1はSに含まれない。次の自然数2は、条件を満たす（22>3）。他のすべての自然数も同様である。 したがって、xは 2, 3, 4, 5... で構成される。集合Sは「xの2倍」なるすべての数値で構成されるため、S = {4, 6, 8, 10...} で与えられる。言い
Posted on August 25, 2021 by Rebecca Skinner Prelude This blog post is a long-form article based on a talk I delivered at the haskell.love conference on 10 Sept 2021. Keep an eye out here and I will update this section with a link to the recording of the talk when it’s available. The original slides for this talk are available on github along with the complete source code for the examples used in
「関数型言語とは何か？」について解説します。「オブジェクト指向の複雑さを軽減する」として関数型言語は近年注目を集めています。しかし「関数を中心にプログラムを組み立てる」といっても、具体的なイメージができない方も多いのではないでしょうか。 本書では「強い制約を課して、本来すべきことに集中する」という視点から関数型言語の概要を紹介します。「変数の値を後から変更できない・副作用を禁止する」など、関数型プログラミングならではの特徴を学んでいきましょう。
Haskellにはfor文もwhile文もありません。 大抵の場合はmap, filter, foldrのような関数を使えば事足りますし、再帰関数を使えばほとんどのループ処理は書けてしまいます。しかし時には今考えているループを実装するために適切な高階関数が思いつかなかったり、計算結果だけが欲しいのに再帰関数をわざわざ定義するのが煩わしくなったりする状況もあるでしょう。 "グラフからコミュニティ構造を抽出する 〜リッチフローによるグラフの時間発展〜"を書いた時にいくつかループ処理を実装する必要があって、その度に再帰関数を定義するのが大変だったので flip fix を使いました。そして思ったより flip fix の使い勝手が良かったので、この記事ではこれにスポットライトを当てて紹介したいと思います。
Haskell Libraries I Love
2022-05-29 I just wanted to share some of my favorite Haskell libraries, and why I love them. Most of my projects use most of these libraries. relude: Alternative PreludeMore convenient Re-exports common types, type classes, and functions from base, containers, text, bytestring, etc. Types: Text and LText, ByteString and LByteString, etc. Type classes: Alternative, MonadIO, Generic, etc. Functions
ラムダ計算を分かりやすく説明した本がありました。 「計算モデルとプログラミング」という本です。 計算モデルとプログラミング 作者:猪股 俊光,山田 敬三 発売日: 2019/04/19 メディア: 単行本 本書を参考にして、ラムダ計算の説明方法を学んでみたいと思います。 目次 著者紹介 出版社情報 書評 目次 第1章 計算の世界と計算モデル 1.1 計算の世界 1.2 計算モデル 1.3 計算モデルとプログラミング言語 1.4 アルゴリズムの記法 1.5 数の体系 1.6 自然数上の計算と計算モデル 演習問題 第2章 抽象機械型計算モデル 2.1 機械による計算のモデル化 2.2 順序機械 2.3 有限オートマトン 2.4 チューリング機械 2.5 チューリング機械の計算可能性 2.6 まとめ 演習問題 第3章 命令型計算モデル 3.1 命令による計算のモデル化 3.2 レジスタ機械 3.
2020/7/28に新しいHaskell拡張がリリースされました。 https://marketplace.visualstudio.com/items?itemName=haskell.haskell さっそく、こいつを使って最速開発環境構築していくぜ！！！ 前提条件 Dockerをインストール VSCodeをインストール Remote - Containers拡張のインストール コンテナ上でHaskell拡張を動作させる 任意のフォルダに.devcontainer.jsonファイルを作成して以下を記載 { "name": "HaskellDevContainer", // DockerhubのHaskell公式イメージ "image": "haskell:8.8", "extensions": [ // HaskellのVSCode拡張をインストール // https://market
This is a literate Haskell-file. You can open it in GHCi by doing the following: curl -O https://las.rs/blog/all-you-need-is-hkt-s.lhs nix develop --impure --expr \ 'with import <nixpkgs> {}; mkShell { buildInputs = [(haskell.packages.ghc924.ghcWithPackages (p: [ p.markdown-unlit ]) )]; }' \ -c ghci -pgmL markdown-unlit all-you-need-is-hkt-s.lhs Haskellers (and even worse, dependent type brained p
Haskellでは再帰的に定義された関数は遅延評価で計算される。 この遅延評価はHaskellの売りの一つであるが、これが時には仇となる。 たとえば、優雅な実装例で知られる次のフィボナッチ数の実装は遅く、メモリの消費量も多い。 fib n = fibs !! n fibs = 1:1:zipWith (+) fib (tail fib) これは、値が評価されるまで計算が待機してメモリが保持されつづけられることが原因だ。 これを解決するには、遅延評価ではなく正格評価で計算すれば良い。 Haskellの神話 - あどけない話 ではzipWithを正格化したzipWith’を定義して、計算を早くする例が提示されていた。 再帰でループを表現するのは、haskellならではの優雅な実装方法だけども、基本は遅延評価なので今あげた問題がついて回る。 例えば、C言語で old=init for (i=1;
GHC 9.10の新機能
GHC 9.10.1が2024年5月11日にリリースされました。 GHC 9.10.1 is now available! - Announcements - Haskell Community この記事では、GHC 9.10の新機能を確認していきます。過去の類似の記事は GHC 9.2の新機能と、GHCの動向2021 GHC 8.10とGHC 9.0の新機能 GHC 9.4の新機能 GHC 9.6の新機能 GHC 9.8の新機能 です。 この記事は網羅的な紹介記事とはなっていません。是非、公式のリリースノート類も参照してください： 2.1. Version 9.10.1 — Glasgow Haskell Compiler 9.10.1 User's Guide docs/users_guide/9.10.1-notes.rst · ghc-9.10 · Glasgow Haskell
GitHub - matsumonkie/izuna: Show Haskell type annotations when doing code review on Github
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
Just what exactly is a type? A common perspective is that types are restrictions. Static types restrict the set of values a variable may contain, capturing some subset of the space of “all possible values.” Under this worldview, a typechecker is sort of like an oracle, predicting which values will end up where when the program runs and making sure they satisfy the constraints the programmer wrote
Haskell入門
はじめに Haskellは、強い静的型付けを持つ純粋関数型プログラミング言語です。 インストール Haskellの環境は、Haskell PlatformまたはHaskell Stackを使って導入します。 Haskell Platform Haskell Platformをインストールすると、Haskellの処理系（GHC）や周辺ツールを一括で導入することができます。Ubuntuでは、以下のコマンドでHaskell Platformを導入できます。 ただし、この方法で入るHaskell処理系（GHC）はやや古いので、最新のHaskellを使いたい場合は後述するHaskell Stackを導入しましょう。 Haskell Stackのインストール Haskell Stackのインストール手順は次のようになります： apt を使って haskell-stack をインストールする。これによっ
GitHub - fp-ts/core: Functional programming in TypeScript
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
Functor Typeclass in Haskell
You might already know the map function: map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs > map (\x -> x + 1) [1, 2, 3] [2, 3, 4] It takes a function of type a -> b and applies it to each element of a list. The elements change, but the data type storing them ([]) remains the same. In this article, we’ll call such a data type with another type inside it a context. Transform
IDE: Measuring memory usage of Haskell values and patching GHC
Posted on August 4, 2020 by Michail Pardalos As part of my Google Summer of Code project to add instrumentation to ghcide, I needed to measure the size of Haskell values in memory. After getting blocked by a bug in a GHC primop I fell down a rabbit hole of learning about GHC’s memory layout, C– and making my first contribution to GHC. In this post I want to describe that journey and hopefully enco
One of my favourite things about Haskell is that its structures and abstractions are very principled, and they have laws dictating correct behaviour. In my experience, this means that when you find a new way to piece together those abstractions it almost always ends up doing something reasonable... or at the very least interesting! As it turns out, optics have a lot of different "slots" where we c
Someone online was solving Advent of Code problems, and had a question about this years’ day 3. They had a working solution using regular expressions (regexes) on String values, but they wanted to use ByteString values instead for performance reasons. They were surprised, however, that there seems to be a lack of community cohesion around regex libraries in Haskell. There’s a reason for that. We g
仕事では Bazel を使ってビルドすることが多くなり，自分でも Bazel ルールを自作するようになったので，実験も兼ねて趣味の Haskell Stack プロジェクトを Bazel を使ってビルドしてみることにしました． 本記事はそのメモ書きです． あとこれは Haskell Advent Calendar 2020 の2日目の記事です． Bazel Bazel は Google のエンジニアが中心になって開発している OSS のビルドツールだ． 以下のような特徴がある： 必要なコマンドのインストール・バイナリのビルド・コマンドの実行などを記述できる それらは全て専用のサンドボックス内で実行されるため再現性が高い Starlark という Python 風な独自言語で記述する キャッシュなどが工夫されており二度目以降のビルドが高速になりやすい 依存関係を明確に記述する必要がある また
Functional programming is finally going mainstream | Hacker News
Agreed. I'd have preferred a top-level discriminant, like Reddit has with /r and /u paths at the top. I'm not sure how I feel about this.If you look at my code in "multi-paradigm" languages like typescript, there's not a heck of a lot of loops, mutations or side effects. I like expressions, and immutability, and higher order functions. They make things shorter and means there's less state for me t
On April 5th, xkcd released Machine, the 15th annual April Fools project I’ve made with them. It’s a game we’d been dreaming of for years: a giant rube goldberg machine builder in the style of the classic Incredible Machine games, made of a patchwork of machines created by individual xkcd readers. For more details, check out Explain xkcd’s wonderful writeup. This is the story of how we built Machi
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Icicle Lang - Traversals as Optimisations
CS SYD - JSON Vulnerability in Haskell's Aeson library
Announcing Ema - Static Sites in Haskell
とりとめのない GHC 線形型メモ - 趣味はデバッグ……
Memory Fragmentation: A Deeper Look With ghc-debug
Making LLVM GEP safer in Haskell
How Dependent Haskell Can Improve Industry Projects
Writing a Static Site Generator Using Shake
An Introduction to Type Level Programming
関数型言語とは何か？(Haskellで学ぶ)
Haskellのループ処理は flip fix でだいたい書けそう - Qiita
計算モデルとプログラミング - Haskell勉強会
VSCodeのHaskell拡張を使って最速開発環境構築 - Qiita
All you need is higher kinded types
Haskellで正格評価でループを回すには？ - hiroki_f’s diary
Types as axioms, or: playing god with static types
Composable filters using Witherable optics
Parser Combinators Beat Regexes
Haskell Stack プロジェクトを Bazel でビルドしてみる
Development notes from xkcd's "Machine"