Tweet Haskellは他の多くのプログラミング言語と異なった特徴を備えており、しばしばそれらが議論を呼ぶことがあります。その中でも特によく俎上に上がるのが、遅延評価です。遅延評価は、適切に扱えば不要な計算を行わず、計算資源を節約してくれるステキな仕組みですが、一歩使い方を間違うと「サンク」という「これから実行する(かも知れない)計算」を表すオブジェクトが無駄に作られてしまい、却ってメモリー消費量が増えてしまう、などといった問題を抱えています。この現象は「スペースリーク」と呼ばれ、かつて専門のAdvent Calendarが作られたことがあるほど、Haskeller達の関心を集めてきました。 そんなHaskeller達の悩みの種を軽減しようと、GHC 8.0以降、StrictとStrictDataという言語拡張が搭載されました。これらの拡張は、大雑把に言うと、 StrictData:
この記事では, Haskellに用いられる「遅延評価」の仕組みを, 図に描いて説明します. 更に, 遅延評価版のフィボナッチ数の無限列を, JavaScriptで実装します. 遅延評価とはどのように動くのか, 考えて行きましょう. HaskellのコードとJavaScriptのコードの比較 Haskellでの x = y y = 10 と, JavaScriptの var x = y; var y = 10; というコードを考えてください. Haskellのコードは, これだけでは何も起こりません. print xとすると, x = y = 10 となって 10 が表示されます. 一方, JavaScriptのコードは var x = y; を評価した瞬間, 「ReferenceError: y is not defined」というエラーが出ます. 更に, main = let x = 1
Haskellスペースリーク Advent Calendar 2015 9日目 Haskellerとて、時には厳しくならなければいけないこともある―― @fumieval, 2015 Haskellは遅延評価を基本としているため、場合によっては未評価の式が積もり非効率な状況に陥ることがある。これを防ぐため、部分的に正格評価にするための仕組みが用意されている。もちろんこれらは闇雲に使えばよいというものではない。使うべきポイントを把握し、これらを見逃さないようにしよう。 この記事では、それらの機能の正しい使い方、間違った使い方を紹介していこう。 カウンター・カウンターズ・サンクス 条件を満たす要素の個数とそうでない要素をそれぞれカウントするプログラムについて考える。アキュムレータ(ループの中で積み上げていく変数)は正格にしないといけないらしいので、BangPatterns拡張を使ってみた。どん
main = do n <- readLn print $ div10 n div10 :: Int -> Int div10 n | n == 0 = 0 | otherwise = result where result = 10 `div` n div10は10を引数の数字で割るような実装となっており、0で割られる時に0を返す実装になってます。 そして今回の問題なのですが、div10関数に0が渡った時に、Strict拡張なしでは0を返すのに対し、Strict拡張をつけてコンパイルしていた場合はdivide by zeroの例外が発生します(は?)。 Core言語でダンプして中身を読んでみた ソース上では何も変化がないので、仕方なくCore言語のソースを比較することにしました。とりあえず通常のStrict言語拡張なしのソースをダンプしてみます。 33 main :: IO () 34
-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the -- generator function to the already constructed part of the vector. -- -- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c> -- constructN :: Int -> (Vector a -> a) -> Vector a ソース コメントからわかるように、constructNは引数として整数nと配列の要素を生成する関数fを受け取って長さnの配列を生成する。 この時、生成関数fは「0からn-1番目まで生成された配列」から「n番目の要素」を返すようにする。 さてこの関数を使
Posted on June 25, 2018 translated by pythonissam, Shinya Yamaguchi authored by Michael Snoyman Last Updated July 2, 2018 Original post: ALL ABOUT STRICTNESS Haskell は (もしかすると、評判のよろしくない?) 遅延 (lazy) 言語です。遅延性の基本的なアイデアは「値は必要となったときにのみ計算される」という、たった一言で説明できるぐらい簡単なものです。しかし、この裏には様々なことが隠れています。特に、メモリと時間について効率的なコードを書こうとしたときに、必要不可欠なトピックがいくつもあります。 弱頭部正規形 (WHNF) と 正規形 (NF) seq と deepseq の使い方 (と関連する概念) データ型の正格性注釈
One question I have often been asked when it comes to Haskell is ‘how do I do dynamic programming?’. For those of you unfamiliar, dynamic programming is an algorithmic technique where you solve a problem by building up some kind of intermediate data structure to reduce redundant work. This can sometimes turn exponential-time algorithms into polynomial-time ones. One classical example of a problem
#include <iostream> using namespace std; int foo(int a, int b) { return a; } int bar(int a) { return bar(a - 1); } int main(int argc, const char* argv[]) { cout << foo( 2, bar(1) ) << '\n'; } 上のプログラムは main 関数で foo 関数を呼んでいます。foo 関数は第一引数の a を返すだけなので b は必要無いです。しかし、正格評価 をする言語では b の値も先に計算しようとします。bar 関数 は終了条件が無い再帰関数なので b の値を計算できないです。従って、このプログラムはセグメントエラーかプログラムが終了しないです。
こんにちは、しいたけです。 某所で関数型プログラミングとはリスト処理のことなのか、と燃えているのを見て、関数型プログラミングとは何か、ということを自分なりの考えを述べたいと思いました。春なので。 この資料は2年ほど前にSupershipの社内勉強会で使ったものですが、この中で関数とオブジェクトを対比している箇所があります。 関数もオブジェクトも、変数や関数の引数戻り値として扱える第1級の値であり、状態を持ち(メンバー変数/クロージャ)、組み合わせが可能(delegate, composition/関数合成)、である、と。 ではオブジェクト指向と関数型プログラミングで何が決定的に異なるかというと、設計・実装のアプローチに何を中心に据えるか、ということだと思います。 オブジェクト指向では、クラス・オブジェクトをモデリングし、各種のオブジェクト指向的デザインパターンを用いてオブジェクト同士を組み
Non-strict languages like Haskell often require the programmer to reason about strictness to achieve good performance. A while ago, Michael Snoyman wrote a blog post about this, giving an introduction on the matter as well as an overview over the tools at our disposal. In this post, I want to offer another, more surgical approach to plugging space leaks that works hand in hand with optimizations c
これは「Haskell (その2) Advent Calendar 2017」の1日目の記事です。遅くなってすいません。 読者として末尾再帰ぐらいは理解しているHaskellerを想定しています。 トップレベルとローカル関数 再帰を用いて関数を書いているとき、トップレベルで再帰するか、ローカル関数で再帰するか、ときどき迷う。この記事では、僕なりの判断基準を示したい。 Data.Listで定義されている再帰が必要な関数は、ほとんどがトップレベルで再帰している。代表例のmapの例を見てみよう。 map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs mapをローカル関数を使う実装にしてみよう。この記事では、ローカル関数名としてgoを用いる。(loopを使う流儀もある。) map' :: (a -> b)
「Rubyで遅延評価」と言えば、Enumerator::Lazyをよく見かけますが、それ以外の手段を使うことになった話をしてみます。 遅延評価、とは Rubyを含め多くの言語では、a = foo(b)のようにすれば、foo(b)の処理が行われて、その結果がaに代入される、という挙動になります。これを先行評価といいます。 一方で、Haskellでは、(そもそも変数は再代入不可、関数も結果は引数のみで一意に決まる、という特徴があるからこその話という面も大きいですが)実際にaの値が必要となるまでfoo(b)の処理は行われません。これを遅延評価といいます。 遅延評価が便利な面 遅延評価にしてメリットがあることといえば、 無限リストや、ものすごく長いリストも簡便に扱える(Enumerator::Lazyもこれです) 引数に渡すために計算はしたけど、関数内で使わなかった…という余計な計算をカットできる
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く