はてなブックマーク

プログラムで文字列を組み立てていると、 "(" ^ なにか ^ ")" のように、文字列結合で段階的に結果を組み立てたいことがある。 文字列が小さいことがわかっているうちはこれでもよいのだけれど、文字列が大きくなってくると段々と計算量が気になってくる（特に最適化をしていなければ、文字列の長さを n とすると結合のたびに O(n) のコストがかかる）。 左から右に組み立てることがわかっていれば、OCamlなら Buffer モジュールが使えるが、括弧のようなものがからむとそうも言っていられない。 stringを使うのをやめて、ropeのようなデータ構造を使う手もあるけど、依存ライブラリを増やしたくない場合もある（言語処理系によっては文字列の内部表現がropeになっていて以下のような小細工をする必要がない場合もある）。 ということで、自分でデータ構造をつくってみる。

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

この記事は Lisp Advent Calendar 2017 の 17 日目の記事です。 eval は強力ではあるものの、その強力さ故に現代的な Lisp ではあまり使われない。 Lisp 以外の eval のある言語、例えば JavaScript ではその存在はほとんど忘れられているような気がするし、 Ruby でも instance_eval や class_eval といった表現力を弱めた変種が使われることはあれど、素の eval が使われることはほとんどないように思う。 Lisp の場合でも、普通は eval を使わずに簡単な DSL を作って自分でインタプリタを書いてしまうことが多いのだけど、 DSL が複雑になってくると少し面倒さを感じないでもない。 そんなときに R7RS Scheme の eval がちょうどうまく使える例があったので紹介したい。 R7RS Scheme

いろいろな言語で、キーと値とを対応づけるデータ構造、いわゆる連想配列、辞書、……たちがどのように呼ばれているか、気になったので調べてみた。 おおよそ、対応表（map）、辞書（dictionary）、実装の名前をそのまま（hash-table）、 Perl風（hash）に分けられると思う。 Common Lisp: hash-table Scheme: hash-table (SRFI-69, SRFI-125 → R7RS-large), hashtable (R6RS Scheme, SRFI-126), map (SRFI-44), mapping (SRFI-146) Haskell: Map OCaml: Hashtbl, Map SML: hash_table (sml-nj-lib) C++: map, multimap, unordered_map, unordered_mu

この記事は ML Advent Calendar 2015 の 7 日目の記事です。 ML 系言語を含め、多くの関数型言語はリストの畳み込み関数を持っている。動作についてはひとつの言語を知っていれば他の言語で困ることはないのだけれど、引数の取り方が違って迷うことがある。 リストの畳み込み リストの畳み込みと呼ばれる演算には右畳み込みと左畳み込みがあり、リスト [e1, e2, ..., en] と初期値 z、二項演算 ⊕ に対して以下のように定義される。 右畳み込み (e1 ⊕ (e2 ⊕ ... (en ⊕ z) ... )) 左畳み込み (( ... ((z ⊕ e1) ⊕ e2) ⊕ ...) ⊕ en) 右畳み込みはリストの右側の要素から順に取り出して初期値 z と組み合わせていき、左畳み込みはそれを左側の要素から行なう。 末尾呼び出しの最適化があれば、左畳み込みは固定のスタック領

Free モナドを使うと Functor f からモナド則を満たす Free f が得られる。 Freer Monads, More Extensible Effects の Freer1 モナドを使うと、 Functor であることすら必要とせずモナドが得られると聞いたので Scheme （Gauche）で実装してみた。 （ちなみに、 Freer モナドの定義は2013年ごろに話題になった Operational モナドと同一である。 Operational モナドを知っている人にはこの記事で得られるものは少ないかもしれない。 Operational については例えば Freeモナドを超えた！？operationalモナドを使ってみようなどを参照。元論文はさらに Operational モナドの効率的な実現法や Extensible Effects との組み合わせについて扱っている） F

Scheme は比較的オーバーロードの少ない言語で、標準の手続きでオーバーロードが使われているのは数値計算とポートまわりくらいだろうか。 しかし、構文レベルで見ると非常に大きなオーバーロードがある。括弧だ。 こんな指摘がある。 全くの初心者にschemeをやらせた経験では、文法を理解するのに苦労するみたいだった。引数リストの()とcondの条件節の()と関数適用の()……等々がみんな同じ見た目(だけど解釈がそれぞれ違う)だから何がどうなってるのかわからなくなる。 — むとう (@masa_edw) July 14, 2011 関数定義するときの (define (func args...) ...) の(func ...)は関数呼び出しではない! なにそれ! (cond (c0 value0) (c1 value1) ...) の (c0 value0)は関数呼び出しではない! — むとう

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?