Haskellのカレンダー | Advent Calendar 2022 - Qiita に参加させていただきます! 突然ですが Haskell でダイクストラ法を実装します。 ダイクストラ法は重み付きグラフで最短経路問題を解くアルゴリズムのひとつです。ダイクストラ法 - Wikipedia に詳しい解説があります。 ダイクストラ法は、重み付きグラフにおいて、その重みに負の値がない･･･つまり重みが正であることを前提にしています。この構造上の仮定によって、貪欲的手法を取ることができるのがその特徴で、結果ベルマン・フォード法などの汎用的なアルゴリズムよりも計算量的に有利になります。 ダイクストラ法では、始点から各頂点への到達コストを最初に \infty と置いて、そこから緩和操作によって徐々にそれらを最適コストまで収束させていくわけですが、このとき グラフの頂点集合からその時点で最小のコスト
この記事は、Haskell Advent Calendar 2022の23日目の記事です。 だいぶ荒削りですので、間違いがあるかもしれません。 目的 OSSのプロジェクトで4年ほどNixを使い続けてきました。 NixのHaskellのサポートの現状のいいところと課題を整理するのが目的です。 なぜNixを使うのかを確認したあと、NixのHaskellサポートをみて課題をまとめます。 なぜNixか、なにがやりたいのか？ Nixはパッケージマネージャーです。各種Linuxディストリビューション, MacOSに入れられるものです。 Nixに期待していることはなんでしょうか？ それは再現性と効率性ではないかと思います。 まずは再現性についてです。nixosのポータルの一番はじめにでてくるように再現性がもっとも重要でしょう。 手元の開発環境やクラウドの開発環境、各種のメンバーで開発するソフトウェアのバ
超関数型プログラミング
この記事はFOLIO Advent Calendar 2022の23日目です。 ソフトウェア2.0 ソフトウェア2.0 という新しいプログラミングのパラダイムがあります。これは Tesla 社のAIのシニアディレクターだった Andrej Karpathy が自身のブログ記事（"Software 2.0"）で提唱した概念で、 ニューラルネットワーク のような最適化を伴うプログラムを例に説明されています。 従来のプログラム（Software 1.0）は人間が命令に基づいたプログラムを作成し、望ましい挙動を行わせます。それに対してニューラルネットワークのようなプログラム（Software 2.0）では人間はある程度の自由度をパラメータという形で残したプログラムを作成し、「入出力のペア」や「囲碁に勝つ」というような教師データや目的を与えてプログラムを探索させるというものです。 画像出典: "So
C++にモナドはいらない - Qiita
C++ Advent Calendar 2022 の 3 日目の記事 を読んだのですが、C++の規格を作っている人の中にモナドが好きな人がいるようで、仕様書の中にモナド的などという単語を必要もないのに入れようしているようです。それでモナドに興味を持った人もいるかと思って記事を書いてみることにしました。巷にモナドの説明自体はいっぱいあるんですが、Haskellを使って説明するものばかりで読みにくいですし、なんだか要領を得ないものが多いので、C++で説明する需要はあるだろうと思っています。ただし、C++でモナドを作っても意味がないよという否定的な意見を書きますので、そういうのがお好みでない方は許してください。 シンタックスシュガーがないのに、モナドを作るんですか？ とりあえず説明のために簡単なIOモナドっぽいのものを書いてみます。まず、文字列を表示する動作を次のように書けるようにします。これは
>>> pretty $ Let [("x", 3), ("y", 5)] (Var "x" * Var "y") -- if it fits into a single line: let {x = 3; y = 5} in x * y -- otherwise: let x = 3 y = 5 in x * y Fancy! But a bit magical. What do the group and align functions do exactly? The core trick First let us summarize our goal. We want alternative layouts: The newline version is narrow but long, the flat version is short but wide. The layoutin
December 17, 2022 A thirty-one minute read 2 comments 4 🗣️ 3 ❤️ 8 🔁 Tags: haskellprogrammingbuild-systems 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 hostin
A new JavaScript backend was merged into GHC on November 30th, 2022! This means that the next release of GHC will be able to emit code that runs in web browsers without requiring any extra tools, enabling Haskell for both front-end and back-end web applications. In this post, we, the GHC DevX team at IOG, describe the challenges we faced bringing GHCJS to GHC, how we overcame those challenges, and
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には問題がありました。同期例外と非同期例外の区別がなされていないことです。 同
皆さんおはようございます。見ている人は見ていたかもしれませんが、昨夜はかなり遅くまで巷で話題沸騰のChatGPTによくわからんクエリを投げて、その結果をみてげらげら笑っていました。特に存在しないプログラミング言語であり「ScalaにHaskellと同じ型推論を加えた」言語Scalayがあることにしたら、ChatGPTが本当にHaskellぽい（単なるHMでなく、Haskellぽいというのは型クラスまで推論される辺り）型推論を持つ架空のScalayコードを解釈実行してくれたりしたところは、控えめに言っても予想外の結果で深夜なのに部屋で忍び笑いをしていました。 Scalaに引数の型推論を追加したようなパチもんのプログラミング言語Scalay（仮）ができてしまった（ChatGPTと対話してる間だけの短い命）。 一応、add: (Int, Int) => Int が推論されてるのすばらですね。 p
Haskellの環境構築2023
この記事はHaskell Advent Calendar 2022の1日目の記事です。 この記事では、2022年12月時点のHaskellの環境構築手順を紹介します。2023年になっても通用するといいなあ。 対象とする環境 対象とする環境は以下の通りです： Unix系 macOS (Intel / Apple Silicon) Linux (x86_64 / aarch64) WSL2を含む（WSL1は不具合があった気がするので避けてください） Windows (x64) Arm系CPU搭載のコンピューターを使っている場合は、別途LLVMが必要になる場合があります。以下に当てはまる場合は、「補遺：LLVMバックエンドを使う」も読んでください： 64ビットArm（Apple Silicon Macや、Raspberry Pi OSの64ビット版など）で、GHC 9.0またはそれ以前のバージョ
型推論器の実装① Hindley-Milner型システム
Damas-Milner 型システム Damas-Milner 型システムとは、型の注釈を必要とせずに多相型を推論する、ラムダ計算の型システムである。ブログタイトルでは、より一般的に使われる Hindley-Milner という名称を用いたが、本稿では Damas-Milner の名称を用いたい。というのも、本稿では Robin Milner と Luis Damas による "Principal type-schemes for functional programs" で示されたアルゴリズムを直接実装するからである。 続き 型推論器の実装 ② Algorithm M 型推論器の実装 ③ 副作用のあるアルゴリズム 1. 言語（The language） 項（Term） 通常多相ラムダ計算では、ラムダ抽象に型がついたり、型適用、型抽象が構文に必要となるが、Damas-Milner 型システ
Haskellの型システム(+拡張)を実装して学ぶ
導入 Mark P. Jones: Typing Haskell in Haskellという論文があります。この論文は、題通りHaskellでHaskellの型チェッカを実装するというものです。詳細な解説がされており非常にわかりやすく、また型システムの体系的な知識が無くても理解できるように構成されています。 しかしながら、この論文にはソースコードを入力にとって型チェックを行うまでに必要な実装の全ては含まれておらず、プログラムを入力に取って動作させるまでにはいくつかの変換や解析が必要です。Titan Type Checkerは、これら不足している機能(+拡張)を実装し、実際にスタンドアロンに動作する型チェッカを実装したものです。本記事では、論文で解説されていない事柄を中心に振り返りたいと思います。 Typing Haskell in Haskellの動作まで 構文解析 (Parser.hs)
Tweag has been working on a GHC WebAssembly backend for some time. Recently, the WebAssembly backend merge request has landed in GHC, and is on course to appear in the upcoming 9.6 release series. This post will give a quick demonstration of how to try it out locally, and explain what comes in this patch and what will be coming next. Playing with WASM locally If you’re using nix on x86_64-linux, c
Haskellでちょっとしたスクリプトを書く
Haskellで本格的に開発する際はcabalなりstackなりでプロジェクトを作るわけですが、ファイル一つで済むような（書き捨て）スクリプトをHaskellで書きたい場合があります。 依存関係のないスクリプトであれば、普通にファイルを作って runghc/runhaskell すれば良いでしょう。しかし、Haskellには標準ライブラリー（base）以外にも「準標準」と呼べる外部のライブラリーが多数あり（例：bytestring, text, vector）、それらに明示的に依存することは runghc ではできません。 そこで使えるのが、cabal scriptやstack scriptと呼ばれる機能です。 cabal script cabal run コマンドを使うと、ファイル中に {- cabal: 形式の特殊なコメントを含むHaskellコードをその場でビルドして実行することがで
限定継続いろいろ | 雑記帳
このブログでは限定継続について過去に何回か記事を書きました： LunarMLと継続限定継続と例外とモナド 今回、LunarML向けのVMに限定継続を実装してみて理解が深まったので、改めて記事にします。 限定継続：スタックを使ったざっくりとした説明 今回はスタックを使って限定継続をざっくりと説明してみます。 関数という概念を持つプログラミング言語では、スタックを使って関数の呼び出しを管理することが多いです。コールスタックとか、スタックのバックトレースとか言いますよね。ここではネイティブのスタックか仮想マシンのスタックかというのは問いません。 関数を呼び出すと、フレームと呼ばれる領域がスタックに確保されて、関数への引数やローカル変数はそこに確保されたりします。 例えば、以下のプログラムを考えます： void g() { // すごい計算 } void f() { double j; g();
Welcome This site describes the various messages that can be returned by Haskell-related tools, including both errors and warnings. For example GHC, the most-commonly-used Haskell implementation, started emiting a code with the format [GHC-12345] for its messages in version 9.6.1. These codes can be looked up below for further information. Other Haskell-related tools are welcome to add their own m
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
フロントエンドのパラダイムを参考にバックエンド開発を再考する / TypeScript による GraphQL バックエンド開発
2022年10月1日に開催された #postdev での発表です
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
Rustのドキュメントを読んだりTwitterで型について話している人が使う用語でわからないものが結構ある。CSを体系的に学ぶ過程でおそらく共通で皆通ってきているのだろうが自分には抜け落ちている。この分野の用語を最低限自分も理解して使えるようになりたい。
Exceptions kind of suck in Haskell. You don’t get a stack trace. They don’t show up in the types of functions. They incorporate a subtyping mechanism that feels more like Java casting than typical Haskell programming. A partial solution to the problem is HasCallStack - that gives us a CallStack which gets attached to error calls. However, it only gets attached to error - so you can either have Str
結論から言うと, 名前を付けることなく再帰的な関数を定義することは可能. 特定のプログラミング言語でどうかというよりは抽象概念としての関数の再帰を名前なしに実現可能かどうかという話(名前なしに実現できるプログラミング言語は存在するかという話). 発端 id:naoyaさんがこういうツイートをしていた. 再帰を書くときに何気なく関数に名前つけたり let で束縛したりしてたけど「再帰には三項関係が必要でありその実現には記号が本質的に関わる」とあり、名前づけの行為が必然だったことが分かった。プログラミングするときの視点が変わるな— naoya (@naoya_ito) 2022年8月12日 たとえば以下のように書いたときのlet fact =みたいな話. let fact = n => n <= 1 ? 1 : n * fact(n-1) ちなみに, 話は一見逸れるけど, こう書けると必然的に
Avoiding space leaks at all costs Created: August 8, 2022 Haskell is a purely functional lazy programming language. The world doesn’t have a lot of lazy-by-default PLs. In fact, all mainstream languages have eager evaluation models. You may argue it’s because eager evaluation is better (because this is how the world works, obviously, only good things are popular). I tend to think this happened bec
Haskellのコードでしばしば見かける幽霊型について。 Phantom type(幽霊型)の特徴 左辺で定義した型変数が右辺に全く現れない型 具体的な値に興味はなく、型の情報さえあれば十分な時などに使われる 型の情報だけでやりたいことを実現するため、型レベルプログラミングの一種と捉えられる Pantaom type（幽霊型）の例 例として、次のようなものを考えます。 時刻の「分」と「時間」を区別できる型を作りたい ただし、「分」・「時間」を表す値の型は同一の型としたい 時刻に関する計算の処理も同一のものとしたい 時刻を保持する型を定義 まず、時刻を保持する型を定義します。 -- 型変数unitは右辺に現れないので幽霊型と呼ぶ newtype Time unit = Time Int deriving (Num, Show) ここで注目すべきは、型変数の'unit'が右辺で使用されていない
これは何 Rubyは「DSLが書きやすい言語」という説明がされることがあります。 なぜRubyはDSLが書きやすい、と言われるのかを僕なりにまとめてみました。 「こういう要素もあるからだよ」などあればぜひコメントや編集リクエストをいただけると嬉しいです。 DSLの例 DSLとは直訳するとドメイン固有言語です。 簡単なイメージで言うと、「ユーザーが自由に構文に近い仕組みを実装、提供できる」ようなものです。 詳しい説明はWikipediaにお任せします。 RubyやRailsで使われているDSLで有名なものはActiveRecord周りの実装などでしょうか。 例を記載します。
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
Type-Signature
Who Wants to Be a Millionaire - but with Types
まとめ 黒魔術を使うと米田の補題による制限を回避して自由闊達に関数が書けます。 前提知識 Haskell の知識、多相関数に関する知識を仮定します。圏論の知識はほとんど仮定しません。 説明 記法 F や A などの大文字始まりの型名はすべてなんらかの具体的な型がそこに入ります。 x や a などの小文字始まりの型名は型変数です。(Haskell での流儀と一緒です。) 自然変換 Functor インスタンスが実装されている 2 種類の型 F と G、および多相関数 u :: forall x. F x -> G x について、以下のような法則が成り立つ時、u は自然変換であるといいます。
You may be aware of Nix or NixOS. Users love them for being superior tools for building, deploying, and managing software. Yet, Nix is generally perceived as notoriously hard to learn. The core Nix ecosystem consists of several distinct components: Nix is a build system and package manager that comes with a configuration language to declare software components, the Nix language. Software made avai
Functional programming is finally going mainstream | Hacker News
My experiences with the encroachment of FP into otherwise imperative or OO languages has mostly been:1. Write a bunch of functional code. 2. Marvel at how clean and neat things are. 3. Get customer reports of performance problems. 4. Spend a lot of time ripping out FP components and replacing them with imperative code. The big mistake is in believing there is any value in this- or that-oriented pr
Paul Louth had a great development team at Meddbase, the healthcare software company he founded in 2005. But as the company grew, so did their bug count. That’s expected, up to a point. More code and more features mean more defects. But the defect rate was growing faster than Louth expected. “We were seeing more and more of the same types of bugs,” Louth says. “It was clear that there was an issue
GitHub - b3nj5m1n/xdg-ninja: A shell script which checks your $HOME for unwanted files and directories.
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
代数的データ型と初等代数学
「関数プログラミングとはなんですか？」と問われたときには「デ，データファースト……(震え声)」と答えることが多いのだが，実際 Haskell や OCaml などの言語を特徴付けるものとして，代数的データ型 (Algebraic Data Type; ADT) の存在は無視できないだろう．その有用性ゆえに，近年では新たな言語の策定の際にその概念が輸出され，Rust や Swift などの言語にも採用されている． 「代数的データ型とはなんですか？」と問われたときには——問われたことがないのでわからないのだが——おもむろに ghci か utop を立ち上げて，解説を始めるのではないかと思う．ひとしきり解説をした後，「つまり直積の直和なんですよ〜🙌✨」と言って話を締めくくるだろう． int 型や float 型など，「メモリ上の表現」という計算機の気持ちに極めて寄り添ったプリミティヴなデータ
こわくない関数型プログラミング
関数型プログラミングは全部理解しようとすると難しいですが、簡単な部分の中にも有用な知見がたくさんあります。 関数型プログラミングにまだ親しんでいない人向けに、明日からのプログラミングにすぐ役に立つ考え方をできるだけわかりやすく伝えます。
This is the first of the two parts of our Parsing with Haskell series. Looking for the second part instead? You can find it here. This two-part tutorial will look into two tools often used together by Haskellers to parse programs: Alex and Happy. We’ll use them to parse a small programming language from scratch. Both Alex and Happy are industrial-strength tools powerful enough to parse even Haskel
GitHub - zesterer/tao: A statically-typed functional language with generics, typeclasses, sum types, pattern-matching, first-class functions, currying, algebraic effects, associated types, good diagnostics, etc.
You can now test Tao in the browser! A statically-typed functional language with polymorphism, typeclasses, generalised algebraic effects, sum types, pattern-matching, first-class functions, currying, good diagnostics, and much more! For more example programs, see... hello.tao: Hello world input.tao: Demonstrates a more complex example of IO effects calc.tao: A CLI calculator, demonstrating parser
余代数な有限機械のHaskell実装
概要 この記事は Bart Jacobs による "Introduction to Coalgebra" という大変面白い本の一部を Haskell で実装し確認したメモである。余代数や終余代数の概念をHaskell での実装を弾幕としてできるだけさりげなく導入する。またその適用例としてStream と有限オートマトンを構成する。結果として余代数が時間発展の構造(structure)を与えるとき、終余代数はその振る舞い(behaviour)を与えることを見る。また余帰納的（余再帰的）定義ということについても補足する。圏論の語彙は本質的な理解には差し替えないと思われる範囲で未定義のまま用いている。 Stream と余代数 Stream 有限オートマトンを扱う前に Stream でウォーミングアップする。Stream とはある型の値の無限個数の列である。いま Pair Functor を次のよ
「関数型言語とは何か？」について解説します。「オブジェクト指向の複雑さを軽減する」として関数型言語は近年注目を集めています。しかし「関数を中心にプログラムを組み立てる」といっても、具体的なイメージができない方も多いのではないでしょうか。 本書では「強い制約を課して、本来すべきことに集中する」という視点から関数型言語の概要を紹介します。「変数の値を後から変更できない・副作用を禁止する」など、関数型プログラミングならではの特徴を学んでいきましょう。
Ante
For exploring algebraic effects, safe shared mutability, and other novel features Ante is currently in active development and the compiler is in a very early state. In addition, the features listed on this website detail the language itself rather than the subset that is implemented by the current compiler. If you are interested to see which features are implemented, please look at the github page
GitHub - Bodigrim/linear-builder: Strict Text and ByteString builder, which hides mutable buffer behind linear types and takes amortized linear time.
String builders in Haskell serve the same purpose as StringBuilder in Java to prevent quadratic slow down in concatenation. Classic builders such as Data.Text.Lazy.Builder are lazy and fundamentally are dlist with bells and whistles: instead of actually concatenating substrings we compose actions, which implement concatenation, building a tree of thunks. The tree can be forced partially, left-to-r
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Haskell で、優先度付きキューを使ったダイクストラ法
haskellとnixの話 - Qiita
How does Prettyprinter print pretty?
Writing a Static Site Generator Using Shake
JavaScript backend merged into GHC | IOG Engineering
ChatGPTはプログラミング言語マスター（語弊ありまくり） - kmizuの日記
WebAssembly backend merged into GHC
The Haskell Error Index — Haskell Error Index
型に関連するよく分からん用語がありすぎる - 技術メモ
Dynamic Exception Reporting in Haskell
関数の再帰的な定義に名前付けは必要か - 貳佰伍拾陸夜日記
kodimensional :: Avoiding space leaks at all costs
関数型プログラミング~Phantom type（幽霊型）ってなんだろう~ - Qiita
RubyでDSLが書きやすい理由を整理する - Qiita
米田の補題、Free theorem と病的な Haskell の関数 - Qiita
Nix – taming Unix with functional programming
Functional programming is finally going mainstream
Parsing With Haskell (Part 1): Lexing With Alex
関数型言語とは何か？(Haskellで学ぶ)