関数型プログラミング言語Haskell Part29 [転載禁止]©5ch.io
■ このスレッドは過去ログ倉庫に格納されています
0001岡部メモリリーク健
2015/07/14(火) 19:27:09.01ID:jJ1YDtNe,.-―:￣｀ー::::::::::､
／::::::::::::.::::::::::::::::::::::::::::｀::､､
/::::::::::::::::::::::::::::::::::::::::::::::::::::::｀､
ｌ::::::::::::::::::::::::::::::::::::::::;':l:::::::::::＼::l
l:::::::::::::::::::::::::::::::::,,::::::::;-,:,::::::::::::::::l
l::::::::::::::::,＿,.::::,';::::::;:::::: :: l ::::::::::::::l
l::::::::::／-/:::/-ニ,.::::／=,.／::::::::::l
ヽ:::: ´､ひ> ;: l .<ひ>' ､::::::::/
ヽ::::: ￣ .)::; l ￣ ｌ::::/ ＜ 毛の壁（岡部健）の話は禁止な
､:::::.. /:::; .,-､ l:::/、
,―:::::::: ゝヽ- ｰ' ､ l::/,､ヽ
l,､,､,,:､:: / ,--､,-.､_ l /::::::,､,､l
ｌ,､,､,､,､,､::､ ｀ー￣-' /:::::::::::,､,､l
ｌ,､,､,､,､,､,､::ヽ ／::::::::､,､,､,､,ﾉ:＼
haskell.org (公式サイト)
http://www.haskell.org/
前スレ
関数型プログラミング言語Haskell Part28
http://peace.2ch.net/test/read.cgi/tech/1428535861/
0446デフォルトの名無しさん
2015/09/08(火) 22:00:09.71ID:KAkZMLHa(IO は別)
0447デフォルトの名無しさん
2015/09/08(火) 22:03:02.01ID:gWCBxnxw箱の喩えでいうなら、その箱から中身を取り出したままでいられる仕組みは
モナドの範疇ではないよ。
Monad 型クラスのインスタンスであるその型に付随された
モナドとは何の関係もない機能だ。
0448デフォルトの名無しさん
2015/09/08(火) 22:04:03.13ID:FdaSRh76>「モナドは値を箱の中に入れるので外からは見えない、だから安全だ」
>っていう話をよく聞くけど、
そんな話を聞いた覚えがないのだが……
0449デフォルトの名無しさん
2015/09/08(火) 22:11:56.24ID:CPV+4Ywq安全だって言ってる文献を教えて欲しい
0450デフォルトの名無しさん
2015/09/08(火) 22:15:43.73ID:1BhJxNoGでも取り出す機能を簡単に付けられるのであれば、箱としての堅牢性は無いに等しいじゃん。
一回入れたらもう出せない！ってのならわかるけど。
>>448-449
IOモナドなんかそんな風に言われるじゃん。
でもIOモナドに入れた値だってfromJustで取り出せる。
0451デフォルトの名無しさん
2015/09/08(火) 22:17:47.80ID:FdaSRh76>IOモナドなんかそんな風に言われるじゃん。
>でもIOモナドに入れた値だってfromJustで取り出せる。
？？？
まず前半、聞いたことがない。そういうこと言ってる実例挙げられる？
後半、意味がわからない。
0452デフォルトの名無しさん
2015/09/08(火) 22:18:26.87ID:CPV+4Ywq「モナドは外からは見えないから安全」という話に思い込んだんじゃ？
0453デフォルトの名無しさん
2015/09/08(火) 22:20:00.08ID:1BhJxNoG0454デフォルトの名無しさん
2015/09/08(火) 22:20:30.14ID:CPV+4Ywq0455デフォルトの名無しさん
2015/09/08(火) 23:38:38.43ID:vkbbpybQパターンマッチでいつでも値取り出せるじゃん。って。
モナドはデストラクタを隠蔽するのが肝なんだよな。
だからparsecとかIOとかをみて、初めてありがたみがわかった。
0456デフォルトの名無しさん
2015/09/08(火) 23:44:27.36ID:FdaSRh76>モナドはデストラクタを隠蔽するのが肝なんだよな。
データ構築子のこと？
runXX の形でモナドの実体を取り出せるモナドは珍しくないし、
IOモナドもそこは変わらないよ？
IO aの実体をWorld -> (a, World)として取り出してもありがたくないだけで
>だからparsecとかIOとかをみて、初めてありがたみがわかった。
うーん、その感覚はさっぱり
隠蔽云々とは関係なくリストモナドだろうがIOモナドだろうがありがたいけどなあ
0457デフォルトの名無しさん
2015/09/08(火) 23:52:35.54ID:FdaSRh76Maybe a の値、つまりNothingによって集合aを拡大していることになるわけで、
この拡大された集合a+上の計算を、元々のaの計算から自然に与えることが
できるようなそういう拡大の仕方とその構造のことをモナドというわけ。
Maybeほどストレートではないけど、他のモナドも基本は一緒。
これはデータ構築子が公開されててパターンマッチできるかどうか、とか
或いはそれと等価な関数が公開されてるかどうか、とかとは関係のない話。
0458デフォルトの名無しさん
2015/09/09(水) 00:06:36.58ID:EJNsNdDh要するに
OOPでクラス関数で主に記述するってことと同じでしょ？
メンバ関数・変数をなるべく使わずに
何がすごいのかさっぱりわからない
0459デフォルトの名無しさん
2015/09/09(水) 00:14:15.49ID:15Wbqaqp誰が関数型言語使えと頼むじゃなし使わないと死ぬわけでもなし
0460デフォルトの名無しさん
2015/09/09(水) 00:50:04.74ID:+WsBDtotバグめっちゃ減るんすよｗｗｗｗ
その代わりコンパイル通りににくくなるんで慣れるまでめっちゃ苛々するんすけど
実行時にヘマするくらいならコンパイル失敗した方がマシだってことを学ぶんすよｗｗｗ
もうC++は体力続かない
三ヶ月前のコードとか読みたくないでしょ
歳取ったらHaskellが良いって解りますよ
Haskellなら三ヶ月前のコード、また読んでみてもいいかなって、それはとっても嬉しいなって
0461デフォルトの名無しさん
2015/09/09(水) 01:57:38.90ID:rpodVdITなんていうか上手く言えないんだけど、例えば、
データ構築子がreturnとbindしか無くて、一方分解子、runの類いがたくさん提供されてるデータを考えてくれ。
どうだいそれって滅茶苦茶役に立たないだろ？
0462デフォルトの名無しさん
2015/09/09(水) 02:07:49.07ID:15Wbqaqp>データ構築子がreturnとbindしか無くて、一方分解子、runの類いがたくさん提供されてるデータを考えてくれ。
なにが言いたいのか理解できないが、いずれにせよreturn とbind があれば
他のはそれから定義できるんだからなにも問題ない
runXXの類がたくさん提供されてる、というのもよくわからんが、
それで有用性が損なわれるとはちっとも思えない
0463デフォルトの名無しさん
2015/09/09(水) 02:09:55.95ID:15Wbqaqpもし、returnでしか当該データ型の値が作れないならrunXX云々以前にそりゃ役には立たない
m a 型の計算が実質的に a 型の計算そのものに崩壊するからな
0464デフォルトの名無しさん
2015/09/09(水) 02:28:58.80ID:rpodVdITだからモナドにするならreturn以外にカスタムコンストラクタをたくさん提供するべき。
逆にコモナドなら、コンストラクタは少なくていい。けど、デストラクタはextractだけじゃだめ。
(俺は_ -> Hoge のヤツをHogeのコンストラクタ、Hoge -> _ をデストラクタって呼んでる。異端かもしれんが)
0465デフォルトの名無しさん
2015/09/09(水) 02:39:48.87ID:15Wbqaqp>だからモナドにするならreturn以外にカスタムコンストラクタをたくさん提供するべき。
いやまったくもって意味不明なんだけど
普通に型定義のデータ構築子がある以上、それを使えばいいんだし、
それらのデータ構築子から構成できないようなものもあり得ない
しかもなんで「べき」なわけ？
Maybe型が役に立たなかったことなんかないだろう
あと、勝手な自分用語振り回されても理解できない（するきになれない）
0466デフォルトの名無しさん
2015/09/09(水) 02:57:08.05ID:rpodVdITところでさ、ライブラリを作っていて、データの内部表現を公開したくない時があるじゃない？
あとでチューニングしたいときとか。そういう時にデータがモナドなら主に ... -> Hoge a を、コモナドなら Hoge a -> ... を提供する。
return / extract に加えて。
理由は、えー… 逆だと使いづらいから。
(たとえばMaybeなら、fromJustってあんまり使わないでしょ？)
0467デフォルトの名無しさん
2015/09/09(水) 02:58:54.11ID:FLIFW6sl荒らしかな
0468デフォルトの名無しさん
2015/09/09(水) 03:07:23.01ID:rpodVdIT理由が弱いので、もう少し考えると、
例えば、doの途中でrunして値を取り出して、その値で分岐して別のモナディックアクションにつなぐのは、計算量が無駄。
それを避けるためにモナド（手続きの抽象）がある、と俺は理解している。
0469デフォルトの名無しさん
2015/09/09(水) 03:13:59.62ID:15Wbqaqpパターンマッチで実体取り出されたくないとき
（実体に依存した利用をされたくないとき）、というのはあるからな
だが、「return に加えて」は意味不明だ
作ろうとするモナドが恒等モナド以上の何かであろうとする限り、
returnでは作れないようなモナド値を構成する方法を提供しなければならない
これは内部表現の隠蔽云々とは何の関係もない
そうしないと使いづらいからではなく、そうしないと恒等モナド以上の
機能を有し得ないから、だ
fromJustを使わない（データ構築子 Just のパターンマッチも使わない）、
というなら、コード全体がモナディックになってしまう
（もちろんnon-monadicなコードは恒等モナドによってまったく等価な
monadicなコードとして書けるが、普通はそんなことはしない）
はっきりいって、何が言いたいのか本当にわからない……
0470デフォルトの名無しさん
2015/09/09(水) 03:14:53.69ID:FLIFW6slこっちもすまん、>>466見る前に書き込んだから
0471デフォルトの名無しさん
2015/09/09(水) 03:20:21.85ID:15Wbqaqp>例えば、doの途中でrunして値を取り出して、その値で分岐して別のモナディックアクションにつなぐのは、計算量が無駄。
>それを避けるためにモナド（手続きの抽象）がある、と俺は理解している。
計算量（？）はほぼ変わらず、コードが見やすくなるだけだ
むしろ、コードの煩雑さを苦にしないならば
最初からモナドの実体を直接操作する方が余計な関数呼び出しと
そこでいう意味の「計算量」は減る
-- オーダー以外の意味で「計算量」を使われるのも違和感があるが
0472デフォルトの名無しさん
2015/09/09(水) 03:21:55.11ID:FLIFW6sl>例えば、doの途中でrunして値を取り出して、その値で分岐して
>別のモナディックアクションにつなぐのは、計算量が無駄。
>それを避けるためにモナド（手続きの抽象）がある、と俺は理解している。
別のモナディックアクションにつなぐのが計算量の無駄というのが、
わからんのだけど
よく言われるように、用途の文脈を明確にしたい場合に使ってる事が多いし
0473デフォルトの名無しさん
2015/09/09(水) 03:27:24.33ID:15WbqaqpReader モナドで、逐一runReaderを使い r->a 型関数に戻すのが手間だ、
くらいの意味だろう。そりゃモナドの中で計算を合成できる方がいいしが、
指摘の通り、手間や関数適用コストの僅かな定数的増大よりは、文脈を切らずに
連続させることの利益が目的でdo 記法を使うはずだ、と私も思う。
0474デフォルトの名無しさん
2015/09/09(水) 04:04:10.81ID:FLIFW6sl少し落ち着いて
>>473
それで意味がわかりましたが、自分も正に>>471と同じ事を思いました
モナド無くていいじゃん、と
0475デフォルトの名無しさん
2015/09/09(水) 05:16:14.00ID:k6Vctrbh「計算は論理の物質化である」
0476デフォルトの名無しさん
2015/09/09(水) 06:53:19.57ID:5v/OlT8AOOPがわかってもC++がさっぱりわからないのと同じ
C++がわかればstaticメンバが何の役に立つのかわかる
0477デフォルトの名無しさん
2015/09/09(水) 07:44:14.88ID:yxoakRA/0478デフォルトの名無しさん
2015/09/09(水) 11:27:05.24ID:Gx2jhnq10479デフォルトの名無しさん
2015/09/09(水) 11:44:28.09ID:15Wbqaqp持ってる有用なデータ型が多いことがHaskellでのプログラミングの進展に
よって後になってから判明したから
後付で用意されたんで、元からあるMonadの定義には手を付けなかった
0480デフォルトの名無しさん
2015/09/09(水) 15:58:18.64ID:Q+d8J0F/藁人形を殴るのやめろ
0481デフォルトの名無しさん
2015/09/09(水) 18:35:43.48ID:wpO/WxMyunboxedが最速かと思ったがもう一つ隠し玉があるのか
0482デフォルトの名無しさん
2015/09/09(水) 20:47:23.14ID:yxoakRA/0483デフォルトの名無しさん
2015/09/09(水) 20:48:31.78ID:15Wbqaqp0484デフォルトの名無しさん
2015/09/11(金) 17:09:38.98ID:yMgx5TOb0485デフォルトの名無しさん
2015/09/11(金) 18:51:03.18ID:KUqdYwfeStateは、状態をあとづけでつける場合に使われるからモナド変換子なのかなぁ。。。？
0486デフォルトの名無しさん
2015/09/11(金) 19:36:27.09ID:v/2h2RVh0487デフォルトの名無しさん
2015/09/11(金) 20:01:00.74ID:2FuYRHxlMaybe a = Either () a
Just x = Right x
Nothing = Left ()
みたいな話？
0488デフォルトの名無しさん
2015/09/11(金) 20:39:04.30ID:v/2h2RVh0489デフォルトの名無しさん
2015/09/12(土) 09:02:59.99ID:8GXyupq5大抵それは「前例のない規模で前例を踏襲する」ことだ
0490デフォルトの名無しさん
2015/09/12(土) 09:43:20.01ID:UPPQquvW「前例のある規模で前例を踏襲することができない」よりはいいんじゃね
0491デフォルトの名無しさん
2015/09/12(土) 20:12:10.06ID:XAqQ9sMD軽トラをCADで拡大して4tトラックになるんだったら仕事なくなる
実際には現実世界の各種係数があって、そっちはスケールしないので無理なわけだが
CAD内でデータを拡大しても、重力やら鉄の剛性やら法律やらetcの
現実世界まで一緒に拡大されるわけではないからな、不整合が起こる
0492デフォルトの名無しさん
2015/09/12(土) 22:59:42.17ID:8GXyupq5拡大できない現実が悪いか、拡大できると言う虚言癖が悪いかを判断できないバカが多い
0493デフォルトの名無しさん
2015/09/13(日) 13:03:42.57ID:kiB/x+KN0494デフォルトの名無しさん
2015/09/13(日) 14:50:26.51ID:mhOIQ8p/だから○○は止めろとグチを言って前へ進まないのはただの甘えです。
ところで、GCがゴミを回収するタイミングを制御する方法はあるでしょうか。
たとえば、ある関数を評価しようとしないとGCが動かないようにできる、みたいな。
ステージクリア型のゲームを作っていると、ステージプレイ中はGCを止めて、
クリアしたりミスしたタイミングで一気にゴミ回収したいことってありませんか？
他にも、3DCGツールを作っていて、レンダリング中ではなく完了後にゴミを回収したい、とか。
0495デフォルトの名無しさん
2015/09/13(日) 15:44:15.42ID:x1dh+v5mGC止めるのはできないはず
System.Mem以下の関数で明示的に起動することはできる
RTSオプションの -I フラグ辺りを見るといいのかもしれない
0496デフォルトの名無しさん
2015/09/13(日) 17:52:56.94ID:m/zohjMNあるある
入力待ちに入る瞬間に軽くGCしといて欲しいとか考える
0497デフォルトの名無しさん
2015/09/13(日) 22:09:38.34ID:mhOIQ8p/ユーザーガイドを見てみました。
なるほど、そのオプションでアイドルになってから
GCが自動起動するまでの時間を指定できるのですね。
この値を非現実的な大きな値にすれば、結果的にperformGC関数で
意図したタイミングでGCを起動できることにならないか、と。
試してみます。
ありがとうございました。
0498デフォルトの名無しさん
2015/09/17(木) 15:51:54.68ID:B1grEVzP0499デフォルトの名無しさん
2015/09/18(金) 01:29:26.35ID:wjuvkHJc0500デフォルトの名無しさん
2015/09/18(金) 13:33:55.01ID:YvxDAq3A0501デフォルトの名無しさん
2015/09/18(金) 15:57:30.16ID:hYbUwCNL0502デフォルトの名無しさん
2015/09/18(金) 17:03:07.30ID:4VBZsKU6騙されたというならもっとこう、嘘を絶対に許さない的な理念があるべきじゃないのか
人を分類して煽り合うだけでは嘘は無くならないだろう
0503デフォルトの名無しさん
2015/09/18(金) 19:10:38.07ID:YvxDAq3Aプログラミングの話をしてくれ
0504デフォルトの名無しさん
2015/09/18(金) 22:09:52.30ID:dOXUeH6Yうまい嘘をつくためにも使えちゃうか
0505デフォルトの名無しさん
2015/09/18(金) 23:39:24.36ID:hYbUwCNL0506デフォルトの名無しさん
2015/09/18(金) 23:58:08.05ID:bAzDgVJCその置換と同等な巡回置換のリストを得る関数 cperms :: ([a], [a]) -> [[a]] を作りたいのですが、泥臭くなってしまいます。
例えば、集合 {x, y, z, w} に対して置換 {x, y, z, w}-->{x, w, y, z} があるとします。
（本来ならば置換は上下に並べて表記したいところですが、これで勘弁してください）。
この置換は2つの巡回置換に分けられ、ひとつは x を x に置換するの巡回置換 [x]、
もうひとつは y を w に、 w を z に、z を y に置換する巡回置換 [y, w, z] です。
なので、cperms ([x, y, z, w], [x, w, y, z]) = [[x], [y, w, z]] となります。
私の考え方は下記のような単純なものです。
引数のタプルの第1要素を置換前リスト、第2要素を置換後リストとします。
置換前リストの先頭要素から次のように順にスキャンします。
0. 置換前リストの先頭要素を a1 とする。
1. 置換前リストの a1 と同じ位置にある置換後リストの要素を a2 とする。
2. 置換前リストの a2 と同じ位置にある置換後リストの要素を a3 とする。
・・・
n. 置換前リストの an と同じ位置にある置換後リストの要素を a[n+1] とする。
a1 == a[n+1] ならば [a1, a2, ..., an] を巡回置換のリストとする。
置換前・置換後の各リストから辿った要素を取り除いた新たな2つのリストを作りタプルにする。
そのタプルに対して再び cperms 関数を適用し、結果を先ほど作った巡回置換のリストと concat する。
泥臭く感じるのは2点。
ひとつは、a1 を覚えておいたり、構築中の巡回置換リストを保存するなどのために
いくつものアキュムレータを付けた再帰関数を作っている事。
もうひとつは、置換前リストや置換後リストから要素を探すときにいちいち先頭から順に探している事。
宣言的とはとても言えないコードになってしまうなですが、良い方法はないでしょうか。
0507デフォルトの名無しさん
2015/09/19(土) 03:37:04.08ID:ygsDvVju憲法守れ！検閲反対！憲法守れ！検閲反対！
検閲する側の人間を支持していてこれか
脳みそ入ってないでしょ
0508デフォルトの名無しさん
2015/09/19(土) 08:31:20.34ID:oTM0A26u0509デフォルトの名無しさん
2015/09/19(土) 09:58:08.46ID:UoEBemSSf :: Eq a => a -> [(a,b)] -> Maybe (b, [(a,b)])
f _ [] = Nothing
f x (y:ys) = if x == fst y then Just (snd y, ys) else fmap(id***(y:))(f x ys)
-- (***) a b (c, d) = (a c, b d)
0510デフォルトの名無しさん
2015/09/19(土) 11:38:35.20ID:9U4PsEMd右から順に書いてしまう (極端には filter even 書いてからその左に length . って書き加える）
んですが、これは慣れてもそういうもの？
それともそのうち「最終的に欲しいのはこれだから」みたいに左から書くようになる？
0511デフォルトの名無しさん
2015/09/19(土) 11:55:02.12ID:uMEyIMVB今はタイプするのが楽だから左から書いてるけど
一度右からの流れを思い浮かべてから逆順をたどるように書くみたいにしかできてない
左から考えられるようになるものなのか？そもそもなるべきなのか？どうなんだろう
0512デフォルトの名無しさん
2015/09/19(土) 12:03:35.61ID:dgpmJE92右から左に思考の順番通り書くので何の問題もない。
カーソルの戻りがイヤで左から右にしたいなら
(>>>) ：関数合成演算子( . )の引数が逆になった演算子（Control.Category）
とか
(&) ：関数適用演算子($)の引数が逆になった演算子（Data.Function）
とかを使えばいいよ。
簡単な短いものはボトムアップで考えて関数合成の連鎖で直接書いてしまうし、
複雑な関数は「欲しいのはこれだから」みたいにトップダウンで定義を考えて
（where節がどんどん入れ子になる感じで）書いていく。
0513デフォルトの名無しさん
2015/09/19(土) 12:36:41.64ID:UoEBemSS0514デフォルトの名無しさん
2015/09/20(日) 00:25:40.61ID:6c+MIwD/0515デフォルトの名無しさん
2015/09/20(日) 09:21:19.17ID:ZXXgaQ/Pレスが遅くなってすいません。
その関数 f の意図が今一分からないのですが、
例えば f 2 [(2, 4), (3, 2), (1, 1), (4, 3)] とやってみると結果は
Just (4, [(3, 2), (1, 1), (4, 4)]) となるのですが、
これは意図通りの結果でしょうか？
0516デフォルトの名無しさん
2015/09/20(日) 09:23:48.87ID:ZXXgaQ/P>>509
間違えました。
> 例えば f 2 [(2, 4), (3, 2), (1, 1), (4, 3)] とやってみると結果は
> Just (4, [(3, 2), (1, 1), (4, 4)]) となるのですが、
結果は Just (4, [(3, 2), (1, 1), (4, 3)]) になります。
0517デフォルトの名無しさん
2015/09/20(日) 10:33:01.14ID:nVyOckkY[(2, 4), (3, 2), (1, 1), (4, 3)]の先頭の(2, 4)はfを使わなくても処理できるので
そこでfを使う意図はありません
次の段階でf 4 [(3, 2), (1, 1), (4, 3)]のような使い方を意図しています
0518デフォルトの名無しさん
2015/09/20(日) 11:37:14.05ID:629ydc810519デフォルトの名無しさん
2015/09/20(日) 12:05:14.46ID:OSUmrGRkググればしっくりくる解き方があるんじゃないかな
0520デフォルトの名無しさん
2015/09/20(日) 12:24:31.09ID:oJTeEA6y0521デフォルトの名無しさん
2015/09/20(日) 12:40:33.83ID:629ydc810522デフォルトの名無しさん
2015/09/20(日) 13:13:36.11ID:ZXXgaQ/Pすいません、やはり意味がよく分かりません。
関数 f の各引数と戻り値の意味を教えていただけないでしょうか。
0523デフォルトの名無しさん
2015/09/20(日) 13:40:26.01ID:ZXXgaQ/P恥ずかしながら初めて聞いた名称だったので調べてみました。
確かに、置換を有向グラフとみなせば、強連結成分分解で解けますね。
今、そのアルゴリズムの詳細を調べているところです。
ただ、私の問題の方が制限がきついので、実際はもう少し特化した方法がとれると思います。
グラフと見なしたとき、全てのノードについて出る辺と入る辺はちょうど1つずつです。
なので極大もなにも一通りにしか分解できませんし、探索中に戻る必要もありません。
>>521
総当たりというのが具体的にどのような処理を指しているのか分かりませんが、
それは結局 >>506 になるのではありませんか？
0524デフォルトの名無しさん
2015/09/20(日) 16:52:06.13ID:KBlLbBcH多少は手続き的っぽくない感じで定義してみた
計算量のことなんも考えてないので泥臭さでは全く負けてないけどｗ
置換は[0..(n-1)]に対する任意の置換を[Int]で与えるものとする
import Data.List (nub, nubBy, sort, transpose)
cperms :: [Int] -> [[Int]]
cperms ns = nubBy unique . (map nub) . transpose . (take n)
$ iterate (map (ns!!)) [0..(n-1)]
where n = length ns
unique xs ys = (sort xs) == (sort ys)
-- cperms [0,3,1,2] => [[0], [1,3,2]]
長さnの一般の置換に対して、[0..(n-1)]の各要素をn回、順に置換していって、
軌道に分けて(transpose)、無駄な重複を削除して結果を得る
unique関数では「2つの巡回置換が本質的に等しい」を判定したいんだけど
毎回ソート2回やるより速い方法が絶対あると思う(メモ化するとか)
0525デフォルトの名無しさん
2015/09/20(日) 17:24:46.74ID:9hEz0Smr文芸誌「新潮」４千部増刷 筒井康隆さんの長編小説掲載
http://www.asahi.com/articles/ASH9K61F1H9KUCVL01X.html
新潮社は１７日、文芸誌「新潮」１０月号（初版８９００部）の４千部の増刷を決めた。
同号には筒井康隆さんの長編小説「モナドの領域」が掲載され、本人がツイッターで「わが最高傑作にして、おそらくは最後の長篇（ちょうへん）」とつぶやくなど話題となっていた。
0526デフォルトの名無しさん
2015/09/21(月) 00:14:56.43ID:bf3bKAE/import Data.Tree (flatten)
cperms (a,b) = map flatten $ scc $ buildG (minimum a,maximum a) $ zip a b
cperms ([1,2,3,4],[1,4,2,3]) -> [[2,4,3],[1]]
0527デフォルトの名無しさん
2015/09/21(月) 00:49:50.78ID:jrn4ktsfg (x, ys) = maybe ([], ys) (((x:) *** id) . g) (f x ys)
h [] = []
h ((x,x'):ys) = uncurry (:) . ((x:) *** h) . g $ (x', ys)
cperms (xs, xs') = h (zip xs xs')
0528デフォルトの名無しさん
2015/09/21(月) 12:16:42.04ID:/2p4upNwグラフで言えば、n個の各ノードから1歩ずつ辿ってスタート地点に戻りn個の輪っかを作る。
最後に本質的に同じ輪っかを1つとみなして輪っかを集める感じですか。
分かりやすいですし、発想が面白いですね。
2つの巡回置換が本質的に等しいことを判定する部分（unique）は、
ys ++ ys の中に xs にマッチする部分があるかどうかを、
xs を先頭から1要素ずつずらしながら調べれば O(n) の計算量でいけますね。
しかしそれ以前に、O(n^2) の nub を n+1 回行っているので、
要素数が増えてくると焼け石に水かもしれませんが・・・
>>526
調べてみたのですが、強連結成分分解の計算量は O(|V| + |E|) なんですね。
（実際にこのライブラリの実装がそうなっているかは未調査のため分かりませんが）
巡回置換への分解が強連結成分分解の特殊バージョンだと分かっていれば、
このコードはとてもシンプルで、何をやっているかも一目で分かるので良いと思います。
ただ、>>524 も >>526 も、集合が整数の連続した列と一対一に対応できること前提なのですね。
まぁ、集合をリストで表現できる時点で要素に番号付けは可能なので、
テーブルか何かでも作っておけば、理論上は整数の巡回置換のリストから元の要素へ戻せますが、
手間と処理時間は少しだけ増えそうです。
0529デフォルトの名無しさん
2015/09/21(月) 12:18:24.09ID:/2p4upNwh (zip xs xs') の簡約をノートに書いていって、処理がやっと理解できました。
結果的に、ひとつの巡回置換の先頭 2 要素のうちの最初のひとつを h で、
次の要素を g で取り出しているのがやや気になります。
あと、1 要素から成る巡回置換を作ることになる場合、
(x, x) :: [...] というパターンから処理を始めますが、
最初の x を h で取り出して、次の x を g で取り出してから、
残りのリスト [...] から g で取り出した x があるかを調べますよね。
そこも少し気になるところです（そこには無いと分かっているから）。
以上の部分をもう少しシンプルにできそうな気がするので考えてみます。
みなさん、いろいろな方法でアドバイスくださり、ありがとうございました。
参考にします。
0530デフォルトの名無しさん
2015/09/21(月) 13:35:14.19ID:/2p4upNw冷静に考えてみれば、いろいろ最適化できそうですね。
たとえば、unique は >>528 よりもっとシンプルになります。
巡回置換リストは、元の集合（を表したリスト）を類別します。
つまり、巡回置換リストのある要素リスト内の任意の要素は、
巡回置換リストの他の要素リスト内には存在しません。
よって、unique xs ys は elem (head xs) ys と同値です。
map nub では、nub は要らないです。
この部分の nub で要素が消えるのは、要素が繰り返し循環している部分です。
たとえば、nub [2, 3, 2, 3] = [2, 3] という感じに。
これ以外にここの nub で要素が消えるパターンはありません。
なので nub xs は、ここに限れば takeWhile (/= head xs) xs と同値です。
これで、O(n^3) から O(n^2) になりました。
せっかくなので、ひとつ残った nub をどうにかしたいところですね・・・
0531デフォルトの名無しさん
2015/09/21(月) 13:40:59.32ID:/2p4upNwと思ったのですが、iterate (map (ns !!)) [0 .. n-1] の部分で O(n^3) でしたね。
連投失礼しました。
0532デフォルトの名無しさん
2015/09/21(月) 18:54:41.45ID:gEmyCLgu(´･_･`)自分が思ったことを素直に表明してるだけで、特段ネトウヨに加担してるつもりはないと思うよ
0533デフォルトの名無しさん
2015/09/22(火) 01:49:24.05ID:xlNSF2Nbレッテル張り
相手を馬鹿にした言動
完全に田中はネトウヨでしょ
0534デフォルトの名無しさん
2015/09/22(火) 06:06:26.79ID:3/1FxAoT同じことを何回も言うのはそれがレッテルであろうがなかろうが問題がある
レッテルを貼ることが問題だというのは多分嘘だろう
本当の問題は連呼すること
0535デフォルトの名無しさん
2015/09/22(火) 07:17:58.47ID:rRTVDkU90536デフォルトの名無しさん
2015/09/22(火) 15:24:02.83ID:cGE1lXHQ0537デフォルトの名無しさん
2015/09/22(火) 18:49:33.73ID:cCHjzu4f>他人の意見を鵜呑みにするより自分で考えてるだけでネトウヨ
いや、まさに他人の意見を鵜呑みにしてるだろw
0538デフォルトの名無しさん
2015/09/22(火) 20:56:50.42ID:ADm2wL+10539デフォルトの名無しさん
2015/09/22(火) 20:59:08.65ID:ADm2wL+10540デフォルトの名無しさん
2015/09/22(火) 21:29:48.50ID:cCHjzu4f0541デフォルトの名無しさん
2015/09/23(水) 13:39:43.66ID:18dgrDRGfmapとかnewtypeコンストラクタとかは最終的に欲しいものというよりむしろ
欲しくないものを検出するために書いてるだけだから
慣れないと感じるのは順序とは別の問題かもしれない
欲しいものの記述のみに集中できる言語があればいいんじゃないか
0542デフォルトの名無しさん
2015/09/23(水) 13:44:57.16ID:OAr0MdsU>欲しくないものを検出するために書いてるだけだから
0543デフォルトの名無しさん
2015/09/23(水) 23:08:22.19ID:mLvEhcU80544デフォルトの名無しさん
2015/09/24(木) 00:22:27.55ID:NkCijieZ反復関数系でフラクタル図形等に応用される
サンプルがあったので研究してみたのですが
値構築子の関数に固有の法則を持たせて
値構築子のタプルの値を使って演算する様ですが
構築子の値に関数をCONSで繋げるという手法が理解できず
何か参考になる文献を知っていましたら教えて下さい。
data Decision = (Int, Double) :-> DecFun
type DecFun = Int -> [Int]
d1 :: Decision
d1 = (1, 0.25) :-> \f -> []
dList = [d1,d2.....]（このリストを処理する関数内でDecFunを匿名関数にして処理）
0545デフォルトの名無しさん
2015/09/24(木) 04:46:59.67ID:ZG5YRh3S■ このスレッドは過去ログ倉庫に格納されています