1001コメント285KB

関数型プログラミング言語Haskell Part22

■ このスレッドは過去ログ倉庫に格納されています

0001デフォルトの名無しさん

2013/03/23(土) 12:34:19.09

haskell.org
ttp://www.haskell.org/

日本語サイト
ttp://www.sampou.org/cgi-bin/haskell.cgi
ttp://www.shido.info/hs/

過去ログ
関数型プログラミング言語Haskell
Part1 ttp://pc.2ch.net/tech/kako/996/996131288.html
Part2 ttp://pc2.2ch.net/test/read.cgi/tech/1013846140/
Part3 ttp://pc8.2ch.net/test/read.cgi/tech/1076418993/
Part4 ttp://pc8.2ch.net/test/read.cgi/tech/1140717775/
Part5 ttp://pc8.2ch.net/test/read.cgi/tech/1149263630/
Part6 ttp://pc11.2ch.net/test/read.cgi/tech/1162902266/
Part7 ttp://pc11.2ch.net/test/read.cgi/tech/1174211797/
Part8 ttp://pc11.2ch.net/test/read.cgi/tech/1193743693/
Part9 ttp://pc11.2ch.net/test/read.cgi/tech/1211010089/
Part10 ttp://pc12.2ch.net/test/read.cgi/tech/1231861873/
Part11 ttp://pc12.2ch.net/test/read.cgi/tech/1252382593/
Part12 ttp://hibari.2ch.net/test/read.cgi/tech/1272536128/
Part13 ttp://hibari.2ch.net/test/read.cgi/tech/1286706874/
Part14 ttp://hibari.2ch.net/test/read.cgi/tech/1299385928/
Part15 ttp://hibari.2ch.net/test/read.cgi/tech/1310199414/
Part16 ttp://toro.2ch.net/test/read.cgi/tech/1317958045/
Part17 ttp://toro.2ch.net/test/read.cgi/tech/1325510368/
Part18 ttp://toro.2ch.net/test/read.cgi/tech/1331902463/
Part19 ttp://toro.2ch.net/test/read.cgi/tech/1340760070/
Part20 ttp://toro.2ch.net/test/read.cgi/tech/1350428908/
Part21 ttp://toro.2ch.net/test/read.cgi/tech/1358702176/

0653641

2013/06/27(木) 08:31:53.67

>>652
ついでに整理してください。
末尾再帰だと何が起こるのですか。

0654デフォルトの名無しさん

2013/06/27(木) 09:24:25.91

呼び出しが、行ったきりのジャンプに最適化される

0655デフォルトの名無しさん

2013/06/27(木) 22:47:52.52

よく考えたらこっちから行くのになんで呼び出しっていうんだろう

0656デフォルトの名無しさん

2013/06/27(木) 23:11:08.43

callの直訳

0657デフォルトの名無しさん

2013/06/27(木) 23:14:55.19

電話掛けるもの、スパイ活動を指令するのもcall

関係ないけど、コールドゲームはcoldじゃなくてcalled game。
試合終了が宣言されたゲームだから。

0658デフォルトの名無しさん

2013/06/27(木) 23:15:12.96

>>656
なぜ call なのか、という質問ではないのか？

0659デフォルトの名無しさん

2013/06/27(木) 23:17:58.67

なぜ呼び出すなのか、という質問だ。

0660デフォルトの名無しさん

2013/06/27(木) 23:32:21.34

returnが戻るだから、本来対になる言葉はgo？

0661デフォルトの名無しさん

2013/06/27(木) 23:38:55.24

もともとサブルーチンはjumpするものだった
誰かがcallの方がいいと考えたんだと思う

0662デフォルトの名無しさん

2013/06/27(木) 23:53:53.65

捉え方の違いじゃね
ハードウェアを意識するか　しないか

0663デフォルトの名無しさん

2013/06/28(金) 00:04:06.32

お前ら、冷静になってよく考えろ

どーでもいい質問じゃね？

0664デフォルトの名無しさん

2013/06/28(金) 00:25:00.39

どーでもいい質問をスルーしたらこのスレで話すこと無くなるだろ……

0665デフォルトの名無しさん

2013/06/28(金) 00:50:25.68

東洋哲学的な精神やな

0666デフォルトの名無しさん

2013/06/28(金) 09:55:25.48

>>661
EDSACの用語で言うなら、インライン展開で使うもの（呼ぶわけでもジャンプするわけでもない）は
オープンサブルーチン、ジャンプして使うものはクローズドサブルーチンと言ったけど、
後者の場合、戻り番地をレジスタで渡して、自己書き換えして戻ってたから、事実上callと言える。
スタック的なものが無かったから再帰呼び出しは（簡単には）できなかったけど。

0667デフォルトの名無しさん

2013/06/28(金) 20:04:26.42

EDSACに行って戻るサブルーチンがあったのはその通りだけど
戻る仕組みを含めて（Wheeler）jumpと呼んでいたわけで、
やはりcallになったのはきっかけが別にあったんじゃないの

0668デフォルトの名無しさん

2013/06/29(土) 21:49:35.70

呼び方にこだわるんなら、68kでもJSRだからジャンプだし、それにこだわる意味は無いんじゃない？

0669デフォルトの名無しさん

2013/06/29(土) 22:04:34.25

すごくどうでもいい話だな。

0670デフォルトの名無しさん

2013/06/29(土) 23:28:51.62

haskellには関数呼び出しなどという命令的な概念はない。
あるのは関数適用式とその評価のみ

0671デフォルトの名無しさん

2013/06/29(土) 23:53:18.52

なんかのセリフみたい

0672デフォルトの名無しさん

2013/06/30(日) 01:27:45.52

>>670
>>655の疑問はHaskellに対して言っているのではなくて
それを実装しているレイヤーに対して言っているんだよ。

0673デフォルトの名無しさん

2013/06/30(日) 07:15:04.04

マクロアセンブラの calling sequence の CALL だろう。

0674デフォルトの名無しさん

2013/06/30(日) 11:19:45.78

>>672
>>670 は暗に「スレチだ馬鹿」というニュアンスを込めているのかもしれん。

0675デフォルトの名無しさん

2013/06/30(日) 11:50:40.16

我々の間にはチームプレイなどという都合のよい言い訳は存在せん。
あるとすればスタンドプレーから生じるチームワークだけだ。

0676デフォルトの名無しさん

2013/06/30(日) 12:31:28.27

知的ぶってるけど何も生産性のない
そして芸術としてもゴミに等しい無価値なやつら
哀れ

微生物以下

0677デフォルトの名無しさん

2013/06/30(日) 12:54:17.39

>>676
久しぶり！元気してた？

0678デフォルトの名無しさん

2013/06/30(日) 15:13:01.09

パール忍者最近見ないな

0679デフォルトの名無しさん

2013/06/30(日) 15:19:27.70

召喚するなよ

0680デフォルトの名無しさん

2013/06/30(日) 15:42:44.49

自分で自分を召還したんですか？

0681デフォルトの名無しさん

2013/06/30(日) 15:47:20.05

あとAransk

0682デフォルトの名無しさん

2013/06/30(日) 16:21:33.89

random-1.0.1.1 パッケージの System.Random モジュール内の関数に関して質問です。

左閉半開区間 [0, 1) のランダムな浮動小数点のリストを確実に得るには、
random 関数を使って自分でリストを作るしかないでしょうか。

randomR 関数は直接リストを得られますが、閉区間 [lo, hi] なんですよね。
しかも、次の説明も何やら怪しいですし。

For continuous types there is no requirement that the values
lo and hi are ever produced, but they may be, depending on
the implementation and the interval.

しかし、randomR の実装を見てみると、結局 random 関数を使っています。
正確には、random 関数の戻り値の乱数の方を v とすると、
2.0 * (0.5 * lo + v * (0.5 * hi - 0.5 * lo)) です。
random 関数が左閉半開区間なので、randomR も左閉半開区間になりますよね。
（もちろん、浮動小数点の場合の話です）

説明と違うような気がしますが、この違いを説明したのが上記の英文の部分でしょうか。

0683デフォルトの名無しさん

2013/06/30(日) 16:29:09.55

randomsは？

0684デフォルトの名無しさん

2013/06/30(日) 16:47:23.96

>>683
あぁそうか、randoms 関数を使えばいいのか。
馬鹿だったわ、ありがと。

でもそれとは別に、randomR 関数の説明って、
なんであんな変な条件みたいなのがあるんだろ。

0685デフォルトの名無しさん

2013/06/30(日) 16:57:00.42

連続だと閉区間でも上限下限は絶対に出力しないというのは一種の制約だから。
[lo, hi]なのに(lo, hi)と同じ実装を許容するなら但し書きを書くのが適切。

0686デフォルトの名無しさん

2013/06/30(日) 18:01:43.49

>>685
でも、>>682 の作り方なら下限は出力されるんじゃない？

「絶対」ではなく「実装依存」ってこと？

0687デフォルトの名無しさん

2013/06/30(日) 21:38:38.36

>>684
足下は初めは平身低頭に知恵を乞いておきながら、用が済めば急にタメ口になるとは何としたことか

0688デフォルトの名無しさん

2013/06/30(日) 21:55:55.54

死ぬほどどうでもいい

0689デフォルトの名無しさん

2013/06/30(日) 22:16:19.65

>>687
ホントごめん。

初めは質問者専用の口調で書いたのだけど、2回目の時にそれを忘れてて、
3回目で、なんかもういいや、ってなってしまった。

0690デフォルトの名無しさん

2013/06/30(日) 22:44:07.97

かまへん、かまへん

0691デフォルトの名無しさん

2013/06/30(日) 23:11:37.34

書いてる途中で自分の口調が分からなくなるのはたまにある
まあ自分はやらかしたことないけど（梯子外し）

0692デフォルトの名無しさん

2013/07/01(月) NY:AN:NY.AN

せやな

0693デフォルトの名無しさん

2013/07/02(火) NY:AN:NY.AN

wikipediaとは違うwikibooksに項目があった
ttp://ja.wikibooks.org/wiki/Haskell/%E5%9C%8F%E8%AB%96
あと英文のmonadの項目誰か訳してくれい（泣

0694デフォルトの名無しさん

2013/07/02(火) NY:AN:NY.AN

人に頼ってないで英語の勉強を始めろ！

0695デフォルトの名無しさん

2013/07/03(水) NY:AN:NY.AN

英語が俺の勉強をすべき

0696デフォルトの名無しさん

2013/07/03(水) NY:AN:NY.AN

>>695
勉強したが、こいつは無理って諦められたんだよ

0697デフォルトの名無しさん

2013/07/03(水) NY:AN:NY.AN

>>695
思考の柵が吹き飛んだ

0698デフォルトの名無しさん

2013/07/03(水) NY:AN:NY.AN

>>693
まってろよ、今大熊さんの本を読んでるところなんだ

0699デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

Lispがある程度わかってる人（SICP半分ぐらいまで読んだ）向けの
Haskell入門書ってないでしょうか

0700デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

シクプってなに？そんなに凄いの？
読んでないとモグリなの？

0701デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

>>700
読み終わるころにはlisp処理系の自作ができる

0702デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

>>699
結論から言えば、Lisp が分かる人をターゲットにした Haskell の入門書はありません。

Haskell を学ぶに当たって、Lisp が分かっている事そのものはたいして役に立たちません。
強いて言えば、Lisp で参照透過性を意識したプログラミングに慣れていれば、
Haskell のその部分で躓くことはないだろうという程度です。
なので、そのような入門書を出版する動機がないのでしょう。

しかし、Haskell の Haskell らしさが出る部分はそれだけではありません。
どのような入門書にも、参照透過性を含め他の Haskell らしさの部分は解説してあります。

ちなみに、SICP で学んだ事は他のどのような言語でプログラムする際にも活きます。

0703デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

過去スレにこんなのがあった。
http://ja.wikibooks.org/wiki/48時間でSchemeを書こう

> このチュートリアルの対象読者は主に以下の2種類です。

LispかSchemeを知っていて、Haskellを学びたい人
プログラミング言語を何も知らないけれども、一定の背景知識を持っていてコンピュータに詳しい人

0704デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

>>703
それを入門書の代わりに使うのなら、
素直に普通の入門書を読んだ方が良いような気がするなぁ

まぁターゲットとしては >>699 にドンピシャだけど

0705デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

lispもCも経由せずに、はじめてのコンピュータ言語でいきなりhaskellを教えるカリキュラムがあってもいいはず

0706デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

IFPHは学部初年度向けと書いてあるしプログラミングの事前知識も必要なかったはず

0707デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

皆んなHaskellを何に使ってる？
俺は趣味で、ゲートICの立体構造をアルゴリズムと見なして、どんな構造なら性能を上げられそうかのシミュレーションに使ってるけど。

0708デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

はあ、そうですか

0709デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

事務処理のスクリプト最強

0710デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

クイックソート

0711デフォルトの名無しさん

2013/07/05(金) NY:AN:NY.AN

世界平和のために使ってる

0712デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>710
それは本物のクイックソートか？

0713デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>712
1) クイックソートって、列から適当な要素を選択して、
2) それよりも小さい要素を集めた列と、大きい要素を集めた列を作り、
3) 作られた2つの列に対して 1)、2) を施し、列を連結する、ものだよね。

このアルゴリズムの骨組みを守りつつ、
平均・最良の計算量が O(n log n) で、最悪が O(n^2) になっていれば、
どれほど馬鹿な実装方法を使おうが、どれほど処理に時間かかろうが、
どれもみんなクイックソートを名乗っていいと思う。

Haskell の稚拙なクイックソートの例は入門サイトや入門書にはたいてい載ってるし、
どんなバカでも理解できるだろうし実装できる。

だから >>710 のは、いくら何でも偽物ってことはないだろ。
というか Haskell の偽物のクイックソートの例を見てみたい。

と思ったのだが、どうだろう？

0714デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

至高のクイックソートを用意しました

0715デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

このクイックソートを実装したのは誰だあっ！

0716デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

俺のクイックソートは一味違うぜ

0717デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

でもHaskellも悪いんですよ

0718デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

実はHaskellとクイックソートって相性悪いよね

0719デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

Haskellerは
zipperの説明を読むだけでエクスタシーに達します

0720デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

なんで大元の論文を引きもしないんだろうか

0721デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

面倒だから

0722デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

都合の悪いものはモナドにしてネイティブで実装すればよい

0723デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

わずか2ページってクイックソートの論文だったっけ？

0724デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>713
>>712じゃないけど、Haskellのよくあるクイックソートは、
空間計算量が最悪O(n^2)になるという点で普通のクイックソートと違って怪しい

0725デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>724
量子コンピュータが実現した世界で何言ってんだ？

0726デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

またHaskellのクイックソートが偽物とか言う奴が現れたか…

twitterでも今年に入ってからこの話題で盛り上がったようだ
まとめのタイトルが笑える
http://togetter.com/li/445854

0727デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>724
怪しいというのが曖昧でよく分からないのですが、
「空間計算量が最悪でもO(nlogn)である」というのは、
クイックソートである事の必要条件なのでしょうか。

0728デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>727
俺にも分からん

0729デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

名前のとおり速けりゃいいんだよ

0730デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

そうやってフザケる話の流れではないような気がする

0731デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

とりあえず、よくあるもっとも簡単な実装はこれかな。

qs :: (Ord a) => [a] -> [a]
qs [] = []
qs (x:xs) = qs (filter (< x) xs) ++ [x] ++ qs (filter (> x) xs)

空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？

0732デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

>>713で正しいよ

なんかwikipediaのクイックソートのページにも実用性が云々と書かれているけど、そもそもリストという
データ構造自体がソートと相性が悪いんだから、そんなこと言っても仕方ないと思うけどね

大量のデータを扱うなら他のデータ構造を使うべきだし、ごく少量のデータなら入門書の実装の
方がむしろ実用的だろう

>>731
それだと重複した要素が消えることないかな？

0733デフォルトの名無しさん

2013/07/06(土) NY:AN:NY.AN

なんかの入門書でHaskellにはクイックソートよりよいソートがあるって書いたあったんだけど何ソート？

0734デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>733
データモデルとデータの追加でよいソートは異なる

0735デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>731
>空間計算量が最悪O(n^2)になるケースってのは、どういうリストに適用した時？
入力が既に正順か逆順にソートされている場合。O(n^2)になるのは正順か逆順のどちらか
だけなんだけど忘れた。この板のHaskell関係の過去スレの一つに議論があったはず
(ちょっと探したけど見つからなかった、曖昧でごめん)

0736デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

見つけた。Part 7の881から

0737デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>715
コーディングの合間に喫煙していたと何故判ったのですか！？

0738デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

Cで作ってHaskellから呼び出すだけのライブラリ

Haskellで一から作ったライブラリ

どっちが幸せになれるの

0739デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

*Main> :type (+) (-)
(+) (-)
:: (Num (a -> a -> a), Num a) => (a -> a -> a) -> a -> a -> a

これを解説してください。(+) を数ではない (-) に適用できる?

0740デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>715で笑ってしまった
恥ずかしい

0741デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>739
ヒント：カリー

0742デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

f :: Num (a -> a -> a) => (a -> a -> a)
x :: Num a => a
y :: Num a => a
（+）（-） f x yのかたちで呼び出すんだろうけど
Num (a -> a -> a)が意味不明すぎる
自然数をラムダ関数で表現するやつかな

0743デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

型クラスNumのインスタンスとして
Numとして解釈できるラムダ関数を定義すれば良いんだよな
えーとどんなだっけ

0744デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

(ﾟдﾟ)

0745デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>739
(-)はデフォルトでは「数」じゃないけど、インスタンスを定義すれば数になる
たとえばNumInstancesパッケージのData.NumInstances.Function
http://hackage.haskell.org/packages/archive/NumInstances/1.3/doc/html/src/Data-NumInstances-Function.html
をインポートすると、
instance (Num b) => Num (a -> b)
が定義されるので、例えば(Int -> Int -> Int)を加減乗除できるようになる

0746デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>732
すまんすまん、= を書き忘れてた。
< か > のどちらかに = を追加して考えて。

>>735 >>736
モリタポ使っても、なぜか Part 7 が見れない。

>>731 のような感じのクイックソートの実装だと、
A ++ B ++ C という形の式が大枠であるよね。

これを順に弱頭部正規形にして評価していくとき、最悪の場合、
左側の ++ 演算子が評価可能になるまで（++の左辺が x:xs の形になるまで）ずっと、
(((・・・((A'' ++ B '' ++ C'') ++ B' ++ C'))・・・))) ++ B ++ C
というような再帰的な形で左側が伸びていくと思う。

未評価の A'' や B' などが何個作られるかというと、
qs 関数が適用するリストの長さを n とすると、ざっと見積もって
3 + 2 * (n - 1) 個かな。
（最初の 3 は一番深い所の A++B++C で、2 は ()++B++C の B と C）

最悪ここまで式が伸びきるので、空間計算量は O(n) ではないか、
と俺は思ったんだが、どこで勘違いをしているのか分からない。

過去ログ Part 7 が見られるようになったら調べてみるけど、
今の所自分の頭ではこう考えた。

0747デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>739

> (+) を数ではない (-) に適用できる?
できない。

*Main> :type (+) (-)
(+) (-) :: (Num (a -> a -> a), Num a) => (a -> a -> a) -> a -> a -> a

これが言っているのは、ざっくりいえば「もし、(-)が数であれば、(-)に(+)を適用できますよ」ということ。

まず、プログラマが何らかの方法で(-)を数(Numのインスタンスの値)になるようにしてあげなければならない。
首尾よくそれが実現できたら、晴れて(+)を(-)に適用できる。

0748デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>747 >>745
ありがとうございます。
> プログラマが何らかの方法で(-)を数(Numのインスタンスの値)になるように
これが実際できてしまう、というのが、Data.NumInstances なのか。

0749デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

Haskellはすごいのでがんばれば何でもできる
Wikipediaのラムダ計算の自然数と算術の項目に
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%A0%E3%83%80%E8%A8%88%E7%AE%97#.E8.87.AA.E7.84.B6.E6.95.B0.E3.81.A8.E7.AE.97.E8.A1.93

0 := \f->\x->x
1 := \f->\x->f x
2 := \f->\x->f (f x)
3 := \f->\x->f (f (f x))
(+) = \m->\n->\f->\x-> m (f (n f x))

としてラムダ関数で自然数の計算をシミュレートする方法が載ってる

0750デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>749
それだと自然数の型が(forall a. (a -> a) -> a)みたいになって、
>>739で要求されてる(a -> a -> a)とは別物

0751デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

ごめん、forall a. a -> (a -> a) -> aね

0752デフォルトの名無しさん

2013/07/07(日) NY:AN:NY.AN

>>749
(+) が間違ってるな。
(+) := \m->\n->\f->\x-> m f (n f x)

■ このスレッドは過去ログ倉庫に格納されています