Finding your way back after a recursive descent into madness Indexing schemesToday, we are going on a deep dive to show how recursion schemes may be extended by the addition of indexing. Last time, we defined over 30 related functions, and this time we're making indexed variants of all of them, so at least 30 more, plus any supporting functions we might need. It could be a descent into a labyrinth
さる8月1日、計算機科学の根幹を揺るがすドドスコ問題が出題され、エンジニアたちは震撼した（意味: 面白問題が出たので、なるべくヘンテコな解法を使って己の技巧を誇示するためにエンジニアたちは競ってコードを書きはじめた）。 【問題】配列{"ドド","スコ"}からランダムに要素を標準出力し続け、『その並びが「ドドスコスコスコ」を3回繰り返したもの』に一致したときに「ラブ注入♡」と標準出力して終了するプログラムを作成せよ(配点:5点)— ((🐑++)) (@Sheeeeepla) 2022年8月1日 そこで、関数型テクニックをなんとかねじこんだ解法を作ったのでここに示す。 import higherkindness.droste.Coalgebra import higherkindness.droste.data.list.{ListF, ConsF, NilF} import higherk
class: center, middle # An introduction to recursion schemes Nicolas Rinaudo • [@NicolasRinaudo] • [Besedo] --- class: center, middle # Recursive Data Types --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[![Linked List - Cons](img/
In today's post, I explain how comonads can be used to create a tailor-made recursion scheme to perform computations based on multiple simultaneous folds over a single recursive data type. The technique is based on the theoretical heavy paper named "Recursion Schemes from Comonads", but I will try to explain it as much as possible in an approachable way from a pragmatic point of view. I will assum
Unifying Structured Recursion Schemes Ralf Hinze Nicolas Wu Jeremy Gibbons Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, England {ralf.hinze,nicolas.wu,jeremy.gibbons}@cs.ox.ac.uk Abstract Folds over inductive datatypes are well understood and widely used. In their plain form, they are quite restricted; but many dis- parate generalisations hav
██████╗ ███████╗ ██████╗██╗ ██╗██████╗ ███████╗██╗ ██████╗ ███╗ ██╗ ██╔══██╗██╔════╝██╔════╝██║ ██║██╔══██╗██╔════╝██║██╔═══██╗████╗ ██║ ██████╔╝█████╗ ██║ ██║ ██║██████╔╝███████╗██║██║ ██║██╔██╗ ██║ ██╔══██╗██╔══╝ ██║ ██║ ██║██╔══██╗╚════██║██║██║ ██║██║╚██╗██║ ██║ ██║███████╗╚██████╗╚██████╔╝██║ ██║███████║██║╚██████╔╝██║ ╚████║ ╚═╝ ╚═╝╚══════╝ ╚═════╝ ╚═════╝ ╚═╝ ╚═╝╚══════╝╚═╝ ╚═════╝ ╚═╝ ╚═══
Thomas HeartmanFebruary 17, 2020 · mod: 20:58, March 15, 2020 You know that feeling where you hear about something and you immediately need to look into it? I had that while listening to the most recent episode of Adam Gordon Bell's /Corecursive/ podcast today, where they were talking about where the name of the podcast came from. Up until then I had just assumed that corecursive meant /mutually r
先日 Gotanda.hs #1 @HERP というイベントがあって、そこでRecursion Schemesで考える並べ替えアルゴリズムというタイトルでA Duality of Sortsという論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている挿入ソートと選択ソートの双対性について書いていきたいと思っています。 ソートアルゴリズムの復習 まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。 挿入ソートは与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。 出典: [Insertion sort - Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort) これをHaskellで実装す
再帰関数の再帰構造だけを抜き出して抽象化した概念。例えばRecursion Schemesの一つであるcataはリストにおけるfoldrトリックの一般化と言える。このように再帰関数から再帰構造を独立させることは法則を使った等式論証を可能にしたりコンパイラによる最適化を期待することが出来る。再帰を直接使わずにRecursion Schemesを使ってプログラムを書くことは、gotoを使わずにfor, whileを用いることで構造的なプログラムを書くことに例えることもできる。ある関手Fの始代数/終余代数として定義される代数的データ型からは、その始対象/終対象としての性質から別の(余)代数との間にユニークに伸びる射が存在する。この射を利用してRecursion Shemesは定義される。Recursion SchemesはSquiggolやBird–Meertens formalism (BMF
Recursion Schemes, Part VI: Comonads, Composition, and Generality 2019-02-28 Previous installments: 1, 2, 3, 4, 4½, 5. Now that we’ve covered folds (cata, para, and histo), unfolds (ana, apo, and futu), and refolds (hylo, hypo, elgot, and chrono), I hope I have showed that recursion schemes are a useful tool to organize programs, beautify code, and clarify human intent. The above schemes provide s
はじめに Recursion schemes(再帰スキーム)とは，再帰的なデータ構造に対する汎用コンビネータの総称のことである．ところで， recursion schemes から導出される再帰構造を捉えた Functor (代数) による再帰データの表現は，コンパイラやインタプリタでASTを扱う際便利な場合が多い．しかし，この表現は相互再帰に弱いという欠点がある．ここでは，高階代数で同様のことを考えることにより，この欠点を克服する手法を紹介する． なお，以下のものを想定している． GHCのバージョン: 8.6.3 前提とするGHC拡張 BlockArguments DataKinds DeriveFunctor FlexibleInstances FlexibleContexts FunctionalDependencies GADTs LambdaCase MultiParamType
TLDR; Basic Catamorphisms & F-Algebras Following my new "* By Example" brand I'm launching "Recursion Schemes By Example" a collection of example-driven easy to understand guides to using recursion schemes! When learning RS I had a really tough time figuring out what sort of use-cases the combinators in the library were good for (zygo, para, apo, elgot, etc); this site aspires to be the guide I wo
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
