CS SYD - Cursors, Part 1: Introduction with the List Cursor
This is the first post in a series about cursors. It explores the motivation behind cursors and uses the list cursor as an example. Disclaimer: cursor is a library based off the concepts outlined in this blog post. It originated in the work on smos, a Purely Functional Semantic Editor. Motivation: The cursor problemSuppose you are writing a terminal user interface (TUI), with brick for example. So
Elias-Fano encoding: 単調増加する数列をほぼ簡潔に表現する - モナドとわたしとコモナド
Haskell Advent Calendar 2018 20日目 単調増加する自然数の列を、最低限のビット数で表現するための興味深いテクニックと、Haskellによる実装を紹介する。 Elias-Fano encoding この手法は、簡潔データ構造に分類されるもの一つであるが、厳密には条件を満たさないため疑似簡潔データ構造と呼ばれる。1970年代、Peter EliasとRobert Mario Fanoによって独立して発見された。 例題として1, 1, 4, 10, 17, 22, 23, 30という列をエンコードしてみよう。まず、それぞれの数を上位3ビットと下位2ビットに分割する。列の長さをNとしたとき、上位のビット数はとする。 上位ビットの列は000 000 001 010 100 101 101 111となる。これをヒストグラムのようにして23個のビンに分ける。 000: 2個
20分でわかるPurely Functional Data Structures (PDF)
20分でわかる Purely Functional Data Structures k.inaba (http://www.kmonos.net/) Apr. 4, 2010 あらすじ イ ミ ュ ー タ ブ ル デ ー タ 構 造 は 遅 い Immutable Object だけで作るデータ構造 この本の 内 容を 全速力で 布教する お題：キュー (Queue) • FIFO (First-In First-Out) • pushBack(e) でデータeを入れる • popFront() で取り出せる • 入れた順に出てくる • 以上 破壊的キュー Immutable Object でない 打倒すべき目標 代 入 手続き型でよくある interface Queue<E> { void pushBack(E e); E popFront(); } よくある実装 1 2 3 ・ 4 ・
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - nikita-volkov/acc: Sequence optimized for monoidal construction and folding
GitHub - ekmett/heaps: Asymptotically optimal Brodal/Okasaki heaps
GitHub - treeowl/compact-sequences: Stacks and queues with compact representations
GitHub - ocramz/depq: Double-ended priority queues
GitHub - mtth/more-containers: A few more container types
GitHub - PaulJohnson/Ranged-sets
GitHub - ocramz/trie-perf: Performance shootout of various trie implementations
GitHub - kowainik/treap: :leaves: :fallen_leaf: Efficient implementation of the implicit treap data structure
Data.Tree.Zipper
GitHub - ChrisCoffey/cuckoo-filter: A pure cuckoo filter library
GitHub - k0ral/euler-tour-tree
二分木の操作 (Haskell Quiz No.16)
A Practical Introduction to Finger Trees
GitHub - sgraf812/pomaps: Haskell data structure for maps and sets with partially ordered keys
GitHub - robdockins/edison: Edison: A Library of Efficient Data Structures