[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part14 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
268(3): デフォルトの名無しさん [sage] 2011/04/27(水)14:08
的を得る、な。
314(13): デフォルトの名無しさん [sage] 2011/05/01(日)02:42
"Plugging a Space Leak with an Arrow" という論文に、
succ n = n : map (+1) (succ n)
は計算に O(n^2) の時間がかかるが、
succ n = let ns = n : map (+1) ns ; in ns
にすれば改善できる、と書かれていました。
（オーダーが下がるとは明記されていない）
前者は succ n を毎回簡約しなければならないのに対して、
後者は最初に１回だけ簡約すれば、それが ns の参照先として保存されるため、
簡約ステップ数が前者に比べて少なくて済むのは分かります。
しかし、ノートに簡約ステップを書き出してみたところ、
後者も依然として O(n^2) のステップ数が必要に感じたのですが、
オーダーは実際には下がっているのでしょうか？
317(3): デフォルトの名無しさん [sage] 2011/05/01(日)06:57
>>314
>>316のいうとおり、nの大きさは計算量に関係ないが、しかし、take m (succ n)としたとき前者はO(m^2)、後者はO(m)のオーダーになっているように思う。
前者はいわば
let
x1 = n
x2 = n + 1
x3 = n + 1 + 1
x4 = n + 1 + 1 + 1
・
・
・
in x1 : x2 : x3 : x4 ...
のような計算をしている。しかし、後者は
let
x1 = n
x2 = x1 + 1
x3 = x2 + 1
x4 = x3 + 1
・
・
・
in x1 : x2 : x3 : x4...
のような計算をしている。
前者はx1、x2...に相当するようなものを覚えていないが、後者はnsの中で覚えているので。
簡約と一緒に、コンスセルの間の矢印を書いたほうが良い。
そうすれば、前者だといちいち計算しなおしているものを、後者だと共有していることが分かるはず。
327(3): デフォルトの名無しさん [sage] 2011/05/01(日)17:35
c言語でデバッグするときは、適当にprintf文を書きますよね？
Haskellでデバッグするときってどうするんですかね？
putStrを挿入したら、関数の型がIOに変わってしまいますけど、他に方法ないですかね？
361(3): デフォルトの名無しさん [sage] 2011/05/04(水)16:43
素直な人 f (g (h arg))
普通の人 f $ g $ h arg
性格が捻じ曲がった人 f . g . h $ arg
473(5): デフォルトの名無しさん [sage] 2011/05/12(木)20:18
一般項ではなく漸化式で計算される数列の要素を持つリストがあるとします。
例えばフィボナッチ数列のリスト [1, 1, 2, 3, 5, 8・・・] などです。
このような数列の第n項までのリストを返す関数 f :: Int -> [Int] があるとします。
この関数がプログラムの複数の場所で必要とされており、
ある場所では第a項まで、別の場所では第b項まで計算されるという使われ方をします。
この場合、素朴なプログラムでは毎回先頭の項から必要な項まで
順に漸化式を解いていかなくてはなりません。
しかし a < b の場合、ある場所で第a項まで計算したのなら、
別の場所では第a+1項から第b項まで計算すればよく、
先頭項から第a項まで同じ計算をもう一度するのは非効率です。
この問題を解決する方法として２つ思い浮かびました。
ひとつは関数 f の戻り値としてリストの他に、
そのリストに連結する形で以降の項から計算し始める関数 f' も一緒に戻し、
上記の例で言えば第b項まで計算するのに f ではなく f' を使う方法。
ただし、この関数を使う側の方で f' を（State などで）持ち回す必要がある。
もうひとつは、関数 f の中で、計算し終わった分のリストを IORef に入れておく方法。
ただし、関数 f 自体も使う側も（関数 f のためだけに）IO モナドとなる。
他に方法はあるでしょうか。
（例に挙げたフィボナッチ数列は一般項が計算できますが、
今回の問題では一般項は計算できない前提でお願いします）
474(3): デフォルトの名無しさん [sage] 2011/05/12(木)20:40
無限リストにすればいいじゃない
486(3): デフォルトの名無しさん [sage] 2011/05/17(火)01:16
すんません
↓はカウントアップする関数なんですけど、
countUp :: State Int Int
countUp = do
n <- get
put (n+1)
return n
get = State $ \s -> (s, s)
n <- get で get は State Int Int なのに、 n に整数が入る理屈が分かりません
502(3): デフォルトの名無しさん [sage] 2011/05/20(金)17:52
haskellwikiに書いてあるやりかたでwxWidgetsをMinGWでビルドしようとしているんだが、
メモリ使用量がすごいせいかldが落ちる……
MONOLITHIC=1とか無茶だろこれ。
オブジェクトファイルだけで500MB超してるんだぞこれ。
511(4): 507 [sage] 2011/05/20(金)22:02
>>510
ありがとうございます。どうやら成功したみたいです。
最初haskellwiki通りにやってうまくいかなくて、Web探し回っていろんな記述組み合わせて試しにやった方法がそれとほぼ同じでした。
書き込みに気がつかなくて依存関係をしらみつぶしにエラー出るたびに直してたので助かりました。
(あとhaskellwikiに書いてあったBladeバンドル版のGTK使って途中までインストールやったのでゴミが残ったかもしれませんが、気にしないことにします)
後から読む人のために補足しておくと、
・tarボールはcabal unpackで簡単にもってこれる
・Warningで言われるDCABAL_VERSION_MINORはつけなくて平気だった
・cabal unpackで持ってきた「gtk」のgtk/demo/helloでデモできる。runghcで動く。
>>508
どのパッチでしょうか？
>>509
そんな制限があったんですか、知りませんでした。
ただ、物理メモリが1GBからVRAM引いた分しかないので効果があるかどうか。
また時間があるとき試してみます。ありがとうございます。
533(3): デフォルトの名無しさん [sage] 2011/05/22(日)07:34
C++のテンプレート特化に相当する機能無いの？
Map aでaがIntだった時自動的にIntMap使ってくれるみたいな
559(3): デフォルトの名無しさん [sage] 2011/05/24(火)21:15
C++で書かれたライブラリを使いたい場合ってもしかして一旦Cでラッパーライブラリ書いて、
DLLにして、それをさらにHaskellからリンクして使うことになる？
563(5): デフォルトの名無しさん [] 2011/05/24(火)23:39
初心者の基本的な質問で申し訳ない。
funcA a >>= funcB >>= funcC
というような式を評価したとき、最初に呼ばれるbindにわたってくる引数の値は、
引数１ (funcA a)を評価した結果のm a
引数２ （funcB >>= funcC）という式（a -> m c)
と考えていいのでしょうか？それとも、
引数２ （funcB）という式（a -> m b)
と考えるべきなのでしょうか？もしくは
どっちと考えても一緒。なぜなら結合法則が一緒であることを保障してるから。
なのでしょうか？
何を見ても、このへんあんまりきっぱり書いてない気がするもので・・・・
584(3): デフォルトの名無しさん [sage] 2011/05/26(木)16:44
しばらくHaskell漬けになってたら、Cのライブラリとかでグローバル変数使ってる副作用バリバリのライブラリ見ると
一瞬ん？？ってなるようになった。
607(6): デフォルトの名無しさん [sage] 2011/05/28(土)22:34
基本的な質問で恐縮ですが
import Data.Map (empty, insert, member)
f :: Int -> Int -> Bool
f x y = menber y $ insert x empty
g : Int -> Bool
g y = f 3
このように関数 f と g を定義した場合、
g 3 や g 5 などを評価する時に
毎回 insert 3 empty が評価されたりはしないですよね
659(8): デフォルトの名無しさん [sage] 2011/06/13(月)22:25
cabal で glfw をインストールしようとしましたが、
途中で止まってしまいます
cabal install -v3 glfw
でインストールを開始したところ、
Graphics\UI\GLFW.hs のコンパイル中に
GLFW_stub.c の gcc によるコンパイルで止まってます
OpenGL-2.4.0.1 はインストールされており、
system32 ディレクトリには GLFW.dll もあります
（管理者権限でコマンドプロンプトを立ち上げてます）
他に足らないものは何かあるでしょうか
685(3): デフォルトの名無しさん [sage] 2011/06/22(水)23:42
「なぜ関数型言語は普及しないか - id:morchin」
http://d.hatena.ne.jp/morchin/20110614#p1
719(3): デフォルトの名無しさん [sage] 2011/06/25(土)23:43
プログラミングに一度も触れたことのないような何も知らない人に勉強させるときに
手続き型と関数型のどっちが良いのだろうかと考えることはある
734(3): デフォルトの名無しさん [sage] 2011/06/26(日)02:42
>>728-733
リストと配列という特性が全然違うデータ構造でのswapを比較して言語の優劣を議論してる時点で全員論外というか何も理解してないのが丸分かり。
リストは伸縮は自在だが要素のアクセスに関してリスト長Lに比例するO(L)時間が必要、配列は伸縮は困難だが要素アクセスはO(1)時間。
こんなに違うものについての「要素の交換」を同じ土俵の上だと思って比較して関数型と手続き型の優劣を議論するのは何もわかってない証拠。
手続き型の配列に相当するものは関数型言語では定義域が有限区間の写像であってリストじゃない。
逆に関数型でのリストに相当する手続き型でのデータ構造は構造体とポインタで作る普通の一方向リストだ。
手続き型プログラミング言語で一方向リストの先頭要素と最終要素をやるには、Haskellでのlastやinitや++に相当する関数を
先ず自分で再帰的に定義すれば交換そのものは729のHaskellでのとほぼ同じ書き方になる。
（C言語だとinfix operatorは自分で定義できないからHaskellでの++はCでは普通の関数呼び出しになり見た目は綺麗じゃないが本質的な問題じゃない）
823(3): デフォルトの名無しさん [sage] 2011/06/27(月)02:59
>>806
鉄道会社で生きてるプログラムのワニ脳みたいな部分はほとんどがアセンブラ言語
当時の天才連中が高級言語を使わずにニーモニック表だけでバカデカいシステムをバグなく組み立てちゃった
高級言語で組み直す気すら起きないほど品質が良かったためそのまま生存競争に勝ってきた
2000年問題のときに外科手術が必要になって切り開いたけど、そのときはアセンブリ職人がいたからなんとかなった
今はそのアセンブリ職人も退職した
もう怖くて誰も手を出せない
自分でプログラムの才能があると思う人はHaskell捨ててアセンブラやりましょう
859(3): デフォルトの名無しさん [sage] 2011/06/29(水)20:51
関数をとってその関数を別の文脈で使用する関数に変換することを
その文脈に持ち上げるといいますが
定数をとって別の文脈で使用する関数に変換することもそういいますか？
Real World Haskell 231P constPのことです
860(5): デフォルトの名無しさん [sage] 2011/06/30(木)10:46
>>859
そういっても何も差し支えないと思うんだけど。 定数ってのは引数なしで値を返す関数のことなんだし。
861(4): デフォルトの名無しさん [sage] 2011/06/30(木)14:22
>>860
どの引数を受け取っても同じ値を返す関数が定数(0階関数)
877(3): デフォルトの名無しさん [sage] 2011/07/01(金)09:06
Haskellの知識なしにモナディウスのコードを眺めてたのですが
IORef,keyboardMouseCallback,addTimerCallbackなどみてると
手続き型と変わらないように見えました。
みなさんはどのあたりにHaskellで書くメリットを感じているのでしょうか。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.072s