Haskell の Array
Haskellのカレンダー | Advent Calendar 2023 - Qiita 3日目の記事です。 Haskell の Array (配列) について書こうと思います。Haskell の Array は索引が型クラスの Ix で抽象化されているため、特に配列の次元を拡張する際に柔軟性がありとても便利です。 そんな便利な Array ですが、もともと Haskell はリスト操作が強力ということもあってか、既存の参考書をみても Array の解説はほんの少しにとどまっているか、解説がないことがほとんどです。 Array が必要になる場面の多くは「リストだと !! によるインデックスアクセスで O(n) になってしまい間に合わない」という場面が多いと思います。しかし Haskell にはインデックスアクセスが O(1) の Vector (vector: Efficient Arra
Haskellでグラフアルゴリズムを攻略する(WIP)
はじめに Haskellでは、ListやTreeがよく取り上げられる一方で、グラフの話題はあまり出てこないことがあります。これは、ListやTreeには適切な始代数があり、それに応じたコンストラクタ（パターンマッチング）がうまく機能するためです。しかし、グラフ構造でも実はmatch関数を使ったパターンマッチングで、驚くほど簡潔に各種のアルゴリズムを実装できます。 グラフの基本構造 まず、グラフの基本構造を以下に示します。 import Data.List import Data.IntMap.Strict (IntMap) import qualified Data.IntMap.Strict as IM type Gr a b = IntMap (a, IntMap b) type Node = Int type LNode a = (Node, a) type Edge = (Node
はじめに - Qiita
ある概念を理解することと、使えるようになることは別のことです。 ある概念に関して定義からその性質を追って行き、その結果理解に到達するという手順はもちろん重要なことですが、その手順を毎回追っていってはより高度なことを理解することは難しいでしょう。例えば僕らは小学校で四則演算を苦労して学習していったわけですが、いつの間にかそれらを瞬時にこなし、より高度なことを中学、高校、人によっては大学、大学院と進み、理解し、また使えるようにしてきました。 未知の概念を使えるようにするには、その概念についてイメージを頭に思い浮かべられるようにする必要があります。ここで浮かべるイメージをその概念の「メンタルモデル」と言うことにしましょう。僕らはより高度な概念を理解するためにそのメンタルモデルを思い浮かべながら文章を追いかけます。もしメンタルモデルと文章に矛盾が発生したらメンタルモデルを修正します。そうして矛盾が
「競プロ典型 90問」Smallest Subsequence (最小部分列問題)
最小部分列問題 「 競プロ典型 90 問」の 006 - Smallest Subsequence（★5） (最少部分列問題) という問題を解いてみたのですが、最初は解説をみてもさっぱり分からず打ちひしがれていました･･･。 が、けんちょんの競プロ精進記録 を見るに、どうもこの問題を解く途中で出てくる nex という配列が「極めて汎用性が高いので、実にさまざまな問題で活用できます！！！」ということらしく、ちゃんと理解しといた方が良さそうだ･･･ということで気を取り直して取り組んでみたところなんとか理解できました。 せっかくなので忘れないうちに解説記事を作って記憶を定着させたいと思います。なお後半の実装パートは、Haskell で実装します。 けんちょんさんの解説記事にあるとおり、この問題 (を全探索で解く場合) の解法のキーになるのは事前に「任意の文字が i 番目以降に出現する位置」を二次
Haskell で、優先度付きキューを使ったダイクストラ法
Haskellのカレンダー | Advent Calendar 2022 - Qiita に参加させていただきます! 突然ですが Haskell でダイクストラ法を実装します。 ダイクストラ法は重み付きグラフで最短経路問題を解くアルゴリズムのひとつです。ダイクストラ法 - Wikipedia に詳しい解説があります。 ダイクストラ法は、重み付きグラフにおいて、その重みに負の値がない･･･つまり重みが正であることを前提にしています。この構造上の仮定によって、貪欲的手法を取ることができるのがその特徴で、結果ベルマン・フォード法などの汎用的なアルゴリズムよりも計算量的に有利になります。 ダイクストラ法では、始点から各頂点への到達コストを最初に \infty と置いて、そこから緩和操作によって徐々にそれらを最適コストまで収束させていくわけですが、このとき グラフの頂点集合からその時点で最小のコスト
超関数型プログラミング
この記事はFOLIO Advent Calendar 2022の23日目です。 ソフトウェア2.0 ソフトウェア2.0 という新しいプログラミングのパラダイムがあります。これは Tesla 社のAIのシニアディレクターだった Andrej Karpathy が自身のブログ記事（"Software 2.0"）で提唱した概念で、 ニューラルネットワーク のような最適化を伴うプログラムを例に説明されています。 従来のプログラム（Software 1.0）は人間が命令に基づいたプログラムを作成し、望ましい挙動を行わせます。それに対してニューラルネットワークのようなプログラム（Software 2.0）では人間はある程度の自由度をパラメータという形で残したプログラムを作成し、「入出力のペア」や「囲碁に勝つ」というような教師データや目的を与えてプログラムを探索させるというものです。 画像出典: "So
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またはそれ以前のバージョ
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
GitHub - IHaskell/learn-you-a-haskell-notebook: Jupyter adaptation of Learn You a Haskell for Great Good!
Read the book right now on mybinder.org with this link: (Usually takes a minute to launch) This is a Jupyter notebook adaptation of the book Learn You a Haskell for Great Good! by Miran Lipovača. I learned Haskell from this book in 2014 by following along in GHCI, as the book suggested. In 2019, the Jupyter notebook format would be a nice way read this book. This is one of the best cases for Theod
Learn You a Haskell for Great Good! | A community version
Hey yo! This is an up-to-date open-source fork of the original Learn You a Haskell (LYAH for short) by Miran Lipovača, "the funkiest way to learn Haskell, the best functional programming language around". This guide is meant for people who have programmed already, but have yet to try functional programming. Now, why did I create this fork? ("fork" means a copy of an original which may be modified
「アルゴ式」をHaskellで学ぶための準備
この記事は、CAMPHOR- Advent Calendar 2021 の7日目の記事です。 「アルゴ式」というプログラミングを学んで実践できる非常に良質なWebサービスがあります。 アルゴリズムについて解説された教科書だけでなく、実際にプログラミングを書いて提出してオンラインでジャッジしてくれるシステムを備えた練習問題も用意されているのが特徴です。さらにこのオンラインジャッジシステムは多くのプログラミング言語に対応しており、その中にはHaskellも含まれています。 今回はこのアルゴ式を読むにあたって練習問題をHaskellで解くために必要になりそうな知識についてまとめました。アルゴ式は現在ベータ版なので将来的な変更で変わってしまうものもあるかもしれませんが、2021年12月現在の練習問題を全てHaskellで解いた上で必要になったものをまとめているので参考にしていただけると幸いです。
3. フォーカス・リサーチ（2）HaskellによるQUICの実装 | Internet Infrastructure Review（IIR）Vol.52 | IIJの技術 | インターネットイニシアティブ(IIJ)
3. フォーカス・リサーチ（2） HaskellによるQUICの実装 IIJの目標の1つはインターネットの発展に貢献することであり、技術研究所は貢献方法の1つとして新しいプロトコルの標準化に参加しています。新しいプロトコルの仕様を議論し、その仕様を実装し、他の実装と相互接続性を検証することで、仕様の完成度を高めることに長年取り組んでいます。 2013年以降はHTTP/2とTLS 1.3の標準化に参加しました。最近の2年半は、この2つのプロトコルに関連が深いQUICやHTTP/3の標準化に関わりました。この記事では、QUICやHTTP/3をどのように実装したかについて説明します。 3.1 QUICとHTTP/3 QUICは、UDPを利用する新しいトランスポートプロトコルです。以下の機能を取り込む大きな仕様として定義されています。 TCPが提供する信頼性、フロー制御、及び輻輳制御 HTTP/2
閉半環を使ってグラフ上の最短距離を計算する！
この記事は Haskell Advent Calendar 2020 21日目の記事です。 以前の記事でトロピカル行列を使ったグラフの最短経路の求め方を解説しました。 ここではトロピカルな隣接行列の累乗を収束するまで繰り返すという方法で最短経路を計算しましたが、実は閉半環という代数を考えると直接的に最短経路を求める計算が可能になります。そこで今回はその方法について解説したいと思います。 以前はHaskellのリスト [a] をベクトルとして行列を実装しましたが、今回はそれだと実装が少し煩雑になるので型レベル自然数を型引数に持つ Vector n a を中心に実装していきたいと思います。この話は以下の Functional Pearl が元になっていますが、この論文もリストを使って実装されているので Vector n a を使ってどのように実装できるかはこの記事で新しく試したところです。 ト
とほほのHaskell入門 - とほほのWWW入門
「ハスケル」と呼びます。 数学者・論理学者の Haskell Curry の名前に由来しています。 LISP, ML などの言語の影響を受けています。 関数型プログラミング言語 であり、特に 純粋関数型言語 に分類されます。 金融、セキュリティ、数学・科学解析、構文解析などの分野での利用例があります。 関数型プログラミングに慣れていない人にとっては、多少学習コストが高いようです。 遅延評価 を採用しており、式は記述されていても必要となるまで評価されません。 関数型言語ですが、モナド などを利用することにより、手続き型言語のような記述も可能です。 Haskell 1.0 (1990年)、Haskell 98 (1999年)、Haskell 2010 (2009年) などのバージョンがあります。 コンパイル型言語ですが、スクリプト言語の様にインタプリタで呼び出すこともできます。 処理系は、イン
Haskellの型と直観論理 - 朝日ネット 技術者ブログ
開発部のxgotoです。Haskellの初級・中級者向けのトピックを取り上げたいと思います。 今回は型(Type)についてです。型はHaskellの入門書でも必ず最初のほうに説明されるもので、手元の本によれば、 型とは、互いに関連する値の集合である。 ---- 『プログラミングHaskell』 Graham Hutton 著 / 山本和彦 訳 だとか、 値の世界は型と呼ばれる系統的な集まりへと分割される。 ---- 『関数プログラミング入門 Haskellで学ぶ原理と技法』 Richard Bird 著 / 山下伸夫 訳 などのように書かれています。たとえば Bool は True と False の2つの値からなる集合だし、Intは整数の集合というように、型は値の集合というふうにみることができます。それならば型などと呼ばずに集合と呼べばいいと思いますが、「異なるものには異なる名前をつけろ
"Fast and Accurate Least-Mean-Squares Solvers" in Haskell https://arxiv.org/abs/1906.04705
Main.hs ��7� V {-# LANGUAGE DataKinds #-} {-# LANGUAGE NoStarIsType #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ScopedTypeVariables #-} {-# OPTIONS_GHC -fplugin GHC.TypeLits.KnownNat.Solver #-} {-# OPTIONS_GHC -fplugin GHC.TypeLits.Normalise #-} module Main where import Prelude hiding ((<>)) import Data
Elixir版?①「プログラミングHaskell第2版」 - Qiita
fukuoka.ex／kokura.exのpiacereです ご覧いただいて、ありがとうございます 先日9/7（土）に開催した、「ElixirConf JP 2019」の準備・運営にかかりきりで、約3ヶ月弱ぶりの投稿です（ElixirConf JP 2019のレビューは追ってまとめます） さて最近、Haskellerの方々と、ご一緒することが、ちょくちょくあります ご存知の方は、ご存知ですが、元々、私の関数型初体験は、Haskellでした … それから幾つものプログラミング言語を経由して、現在、Elixirに落ち着いており、恐らく、Elixir以外の言語を選ぶことは、よほどのことが無い限り、無いと思います とはいえ、言語ヲタとして、他言語に学ぶことは多くあり、今回は、先月出たばかりの「プログラミングHaskell 第2版」の第1章を、Elixirで解釈してみようと思います（コラムは、原著の
計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita
皆さん、ソートは好きですか？ 僕はHaskellerのクセにボゴソートが好きです。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 なにやらTLでスターリンソートなるものが流行っていました。 まずO(n)とは何かという事なんですが、これはビッグ・オー記法と言ってアルゴリズムの性能の指標を表すものです。 O(n)の他にO(1)とかO(log(n))とかO(nlog(n))とかO(n^2)とかがありますが、詳しくは割愛します。この辺を参考にするとよく分かると思います。ともかく、O(n)はむっちゃ速い、というかソートアルゴリズムではまず有り得ないです。 にも関わらず、スターリンソートはその壁を打ち破って、O(n)で並べ替えを実現しちゃうんですよね。 というわけでHaskellで
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
関数と型で理解する自動微分
