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

1 名前：デフォルトの名無しさん mailto:sage [2017/01/15(日) 23:43:54.28 ID:Vh4eztBk.net] 関数型プログラミング言語 Haskell について語るスレです。 haskell.org (公式サイト) www.haskell.org/ 前スレ 関数型プログラミング言語Haskell Part28 echo.2ch.net/test/read.cgi/tech/1428597032/ 852 名前：デフォルトの名無しさん [2017/08/13(日) 01:44:46.49 ID:Pg7jRQiA.net] Let vs. Where - HaskellWiki https://wiki.haskell.org/Let_vs._Where#Lambda_Lifting これってwhereは引数に変換されるってこと？(英語うまく訳せなくて分からない) 853 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 06:26:42.63 ID:BxbLY5/X.net] 競技プログラミングではデフォルトライブラリしか使えないので 高度なアルゴリズムは自分で勉強して実装しておいたものをコピペするしかないのだ 854 名前：デフォルトの名無しさん [2017/08/13(日) 10:34:38.57 ID:fRo9GRp1.net] モナドってなんなの？ 855 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 12:11:08.44 ID:ndxDWak1.net] 文脈 856 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 13:12:26.05 ID:mWeUlEpW.net] 山本ﾀｿは「裏面配線」って言ってたかな 857 名前：デフォルトの名無しさん [2017/08/13(日) 17:47:54.48 ID:fRo9GRp1.net] 関数プログラミングって文字列型って上手くあつかえるの？ オブジェクト指向の最大の欠点って「文字列を上手く扱えない」ところに あると思うんだよね。 858 名前：デフォルトの名無しさん [2017/08/13(日) 17:51:31.77 ID:fRo9GRp1.net] >>846 何か「表面」があっての裏面配線なんだろ？ ではその表面って何？ 859 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 19:22:11.54 ID:zbgzOget.net] >>842 違うよ。 ある関数の定義に使う補助的な関数の定義は、独立してトップレベルに置く事もできるし、 let や where を使って関数定義の中に置く事もできるよ、って言ってる。 関数内部で定義されていた関数を外に出して独立させることを lambda lifting と言って、 逆に外にあった関数を別の関数の内部で定義することを lambda dropping と言うんだ。 Haskell を使うだけならこんな理解で十分なんだけど、 もともとは関数型言語の処理系の研究で出てきた用語なんで、 その辺りまで深く学びたいのなら、やつぱり英語を読めないと難しいかも。 ちなみに、そのリンク先の [3 Lambda Lifting] と比べれば、 その直後の [4 Problems with where] の方が衝撃的な内容だね。 Haskell を実用的に使っている人にとってはこっちの方が大事な内容だよ。 860 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 20:15:07.01 ID:DrQ+cSjE.net] Haskellという土台の上に、オレオレ言語を構築する。それがモナドだ Haskell上で動作する『ぼくのかんがえたさいきょうのげんご』 DSLプラットフォーム 861 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 20:19:51.10 ID:qvBBF+tW.net] >>849 衝撃だけど実際どれくらいパフォーマンス上のインパクトがあるの？ 862 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 21:59:10.19 ID:zbgzOget.net] >>851 試せばすぐに分かるが、あのフィボナッチ数のサンプルでは全く大した事なかったりする。 確かに後者の方が遅い代わりにメモリ効率いいけど、ほとんど差が出ない事に驚くほどだよ。 差がはっきり出る例を作る方が難しいと思う。 衝撃なのはパフォーマンスの差じゃなくて、単に引数を省略しただけで コンパイルの結果に差が出ることがある、という事実。 GHCにはこういうことがあると、頭の片隅にでも入れておいた方がいいね。 他にも「単に***を変えただけで何で意図したように動かないの？」 ってなるようなコンパイラの仕様があるだろうから、 それに出くわした時に、もしかしてと気づければ無駄に悩む時間が省ける。 863 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 22:05:27.98 ID:IBmKuvX6.net] STモナドとSTArrayの理解を深めるのに向いてる書籍やサイトなどがあれば英語でもいいので教えていただきたいです 競技プログラミングで少し行き詰まってて 864 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 22:12:47.72 ID:qvBBF+tW.net] >>852 なるほど 関数プログラミング入門か実践入門あたりの和書でもポイントフリーか否かで 動作が変わるという内容を見たことはある 865 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 22:35:47.24 ID:3dVRXwBQ.net] >>851 fib1 40は1秒かからなかったけど fib2 40だと37秒かかった fib1 = (map fib1' [0 ..] !!) where fib1' 0 = 0 fib1' 1 = 1 fib1' n = fib1 (n - 1) + fib1 (n - 2) fib2 x = map fib2' [0 ..] !! x where fib2' 0 = 0 fib2' 1 = 1 fib2' n = fib2 (n - 1) + fib2 (n - 2) 866 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 22:42:29.03 ID:3dVRXwBQ.net] >>855 fib1 43は1秒かからなかったけど fib2 43は2分40秒かかった 867 名前：デフォルトの名無しさん [2017/08/13(日) 22:56:30.39 ID:Pg7jRQiA.net] >>849 教えてくれてありがとう 868 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 23:03:01.35 ID:Kt+T0SXe.net] 毎回 let 束縛し直すから遅い、って凄えなこれ 手動 eta-reduction 必須、みたいなんか 869 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 23:18:59.79 ID:AxVfgjdD.net] >>855 fib3 40、fib4 40は fib2 40と同じくらい fib3 = let fib3' 0 = 0 fib3' 1 = 1 fib3' n = fib3 (n - 1) + fib3 (n - 2) in (map fib3' [0 ..] !!) fib4 x = let fib4' 0 = 0 fib4' 1 = 1 fib4' n = fib4 (n - 1) + fib4 (n - 2) in map fib4' [0 ..] !! x 870 名前：デフォルトの名無しさん mailto:sage [2017/08/13(日) 23:39:51.65 ID:DrQ+cSjE.net] >>842 なにこれこわい 871 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 00:09:46.90 ID:CgEdc2Wx.net] >>855 最適化オプションを付けてコンパイルしてみ。 ほとんど差が無くなるから。 872 名前：デフォルトの名無しさん [2017/08/14(月) 00:40:48.93 ID:qlMtZwAF.net] >>840 traceはメモ化には使えないってことですか >>851-852 試してみた 使用メモリがだいぶ違う、低スペックPCなので20でも実行時間に差が出た i.imgur.com/lJUUCAs.png i.imgur.com/zXHSwNH.png 873 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 01:18:11.31 ID:BK9BhUbr.net] モナドを取り入れると明らかに型が違うのが分かる Identityモナドでもいいんだが 問題なのは引数の省略ではなくコンストラクタの省略ではないか fib1 = return (map fib [0 ..] !!) fib2 x = return (map fib [0 ..] !! x) 874 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 01:40:22.76 ID:tyQzDLaM.net] 呼び出し毎の関数束縛が遅いってことかね 値の束縛やトップレベルの関数呼び出しだとどの程度だろう 875 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 03:27:39.46 ID:YjoaiCYq.net] >>861 たしかに最適化で差異がなくなった 最適化なし -O0 fib1 (sec: 0.00 mem: 3456) https://paiza.io/projects/0LYONUr9fsU2GCX0AE8A_g fib2 (sec: 0.87 mem: 4608) https://paiza.io/projects/iNAIEVZM5IY5uLxzJ_QJ7w 最適化あり -O1 fib1 (sec: 0.00 mem: 3280) https://paiza.io/projects/XCnm40B0C1HcbuAIBGyUFw fib2 (sec: 0.00 mem: 3312) https://paiza.io/projects/Et1N4r-vdxXjrid_7hn6PA 計測手段 /usr/bin/time -f "sec: %e\tmem: %M" 876 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 05:10:48.34 ID:8PjQyPOp.net] 最適化かくにん！ 　　　よかった。 877 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 12:00:31.24 ID:vFMuIdhl.net] やはり、最適化かかってんのね。 安心したけど書いてるのがもう少し速くなるかなと思ってたので、残念なような、、 linuxでgtk2hsでつくってたのをwin10に移植しようとしたら、うまくいかなかった。 gtk2hsの公式も落ちてたし、HaskellのGUIは今は何が主流 or ポテンシャル高い、なんですかね？ 878 名前：デフォルトの名無しさん [2017/08/14(月) 14:52:12.07 ID:yxoqAlkZ.net] すまん、いろんなモナドをJavaとかPythonとかのコードで 表してくれ・・・ なんとなく言いたいことは分かったとしても、はっきりとモナドが なんなのかが分からない。 クラスとは何が違うのか。 879 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 15:06:44.92 ID:Au3l8RWH.net] ひところ GUI の為の FRP に熱を上げていた連中は今、何に熱を上げてるの？ 880 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 17:17:03.93 ID:emaMcYYJ.net] >>868 >すまん、いろんなモナドをJavaとかPythonとかのコードで >表してくれ・・・ JavaかPythonのスレ逝くべきだと思うの >なんとなく言いたいことは分かったとしても、はっきりとモナドが >なんなのかが分からない。 >クラスとは何が違うのか。 「なんとなく」もわかってないと思うよ あと「モナドは自己関手の圏におけるモノイド対象以上でも以下でもない」が本質的な回答 881 名前：デフォルトの名無しさん [2017/08/14(月) 17:29:31.74 ID:yxoqAlkZ.net] >>870 お、イキリオタクか？ 平たい言葉で説明できないやつは無能なんだよなぁ・・・ 自分は頭いいとおもってる？？かっこいいね？？本質的な解答とかいっちゃってさ 882 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 17:52:42.99 ID:emaMcYYJ.net] CSにコンプレックスでもあんの？ テクニカルな概念をバカにわかるように説明しようとしてもムダってだけ 883 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 18:03:28.37 ID:HwAT4qGf.net] 春先Haskell熱心にやってたが いまはCとかアセンブラとかそんなんばっかw 884 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 18:05:00.48 ID:HwAT4qGf.net] 圏論分からんのがここで いくら吠えても無駄だとという… 885 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 20:12:02.36 ID:IonSoW2j.net] 「左辺 <- 右辺」の右辺をモナドという 左辺と右辺が等しいとは言っていないので制約が少なくて便利 886 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 20:17:22.67 ID:lpoYOEZY.net] 圏論を学ぶ為の知識がない 887 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 20:37:31.10 ID:IonSoW2j.net] letとwhereが炎上したのも 等しいと書いてあるのに時間とメモリの消費が違うのはおかしいって話だよな 888 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 20:53:52.30 ID:FlMJ7oBL.net] 圏論もモノイドもわからなくてもHaskellでコード書くくらいは出来るけどな もっと初学者への門戸を広げないと未来がない気がする 889 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 22:55:23.88 ID:CgEdc2Wx.net] >>867 最適化オプションで差がほぼ無くなるんだから、 俺は、どっちの書き方でも良い ==> 読みやすい方で書けばOK となって嬉しいけどな。 GUI ライブラリの主流は知らんけど、ポテンシャル高いのは Web アプリ系だと思ってる。 Webブラウザを GUI のキャンバスにするタイプのライブラリ。 基本的にはどのプラットフォームでも同じように動く。 既存の Web アプリ用テストフレームワークが使える。 この辺り、ライブラリ開発者にもアプリ開発者にも大きなメリットで、 要するに開発がしやすい。 これからどんどん進化していく可能性が高いんじゃないかな。 そんなライブラリはいくつかあるけど、俺は threepenny-gui がおすすめ。 ヘンに小難しい EDSL が無く、概念が素直でシンプルだからプログラムしやすいよ。 stackage にも入ってるから導入が楽だしね。 890 名前：デフォルトの名無しさん mailto:sage [2017/08/14(月) 23:10:56.01 ID:/MmIRMIQ.net] >>879 情報ありがとう。 良い機会だしThree pennyやってみるよ。 上ででてるFRPとかいうのもやれそうで面白そうだし。 891 名前：デフォルトの名無しさん mailto:sage [2017/08/15(火) 02:45:23.70 ID:NWVlMToc.net] >>842 2014年とかめっちゃ情報古いのでアテにならんだろ Revision history of "Let vs. Where" - HaskellWiki https://wiki.haskell.org/index.php?title=Let_vs._Where&action=history 892 名前：デフォルトの名無しさん mailto:sage [2017/08/15(火) 16:18:56.38 ID:5CT1InAk.net] Chris Okasakiの純粋関数型データ構造 Haskellを志すキッズはマストバイだわ まだ3章だけど、木の値の更新でどうやって効率良く（更新しない部分を）扱ってるのか解ったわ 根元から辿って、毎回関係ない方を共有してけば確かに辿るステップ分のコピーしか発生しないわけだわ 対数オーダーになるわけだわ なるほどなるほど SML記法で書いてあるけどHaskell式としてもすぐに頭に入るわ 893 名前：デフォルトの名無しさん mailto:sage [2017/08/15(火) 17:50:51.72 ID:ukf6/i16.net] ステマステマス 894 名前：デフォルトの名無しさん mailto:sage [2017/08/16(水) 10:19:38.26 ID:WjjZTNlo.net] smlnj入れたけど全然勉強進んでないなそういえば 895 名前：デフォルトの名無しさん mailto:sage [2017/08/16(水) 15:19:53.05 ID:CVOJ5+kj.net] ニュージャージーSMLは大学時代情報科学実験だか演習だかの簡易コンパイラ作製でひどい目にあった Haskellに出逢えなかったら危うく関数型アレルギーになるところだった 896 名前：デフォルトの名無しさん mailto:sage [2017/08/16(水) 17:48:37.53 ID:i974/+KY.net] stackで、stack buildしても上書きされなかったりします？ stack execしても、新しいのにならない、、 897 名前：デフォルトの名無しさん [2017/08/16(水) 20:37:22.91 ID:DL/Olpzx.net] >>885 どんなとこが合わなかったの？ 898 名前：デフォルトの名無しさん mailto:sage [2017/08/16(水) 23:08:21.23 ID:CVOJ5+kj.net] ・怒涛の再帰再帰再帰再帰の思考枠組みに悲鳴を上げる、手続き脳だった当時のボクの頭が ・末尾再帰最適化など実際（パフォーマンス）的なことを教えてくれず、代入なし、変更はコピーでやるとふわふわっと説明され、 （時間・空間）計算量的に現実には使い物にならないんじゃないかという疑念を払拭してくれなかった当時の講師（ボクはC++のように本格的でないものにはやる気が出ない性格）が ・演習に遅刻した奴への嫌がらせかと疑わしい程に沢山埋め込んであるレジュメの誤植を、口頭でちょろちょろっと訂正するだけのおざなり風土（レジュメだけでなくちゃんと教科書で進めろ）が ・できあがる、四則演算しかできない（途中アセンブリ言語に少し触れたのは良かったが）面白くもなんともない（ボクは本格的でないものにはやる気が出ない性格）糞仕様の言語（とそれ用コンパイラ）が …ん？ なんかほとんどニュージャージーのせいじゃないな 899 名前：デフォルトの名無しさん mailto:sage [2017/08/16(水) 23:58:51.50 ID:t3qJKwuj.net] そういうの、よそのスレでやってくれないか 900 名前：デフォルトの名無しさん mailto:sage [2017/08/17(木) 07:36:41.55 ID:+LfjPFPQ.net] すいません許してください。何でもしますから 901 名前：デフォルトの名無しさん [2017/08/18(金) 00:54:02.54 ID:/Ug8Ilbd.net] モナドってインタフェースみたいなもんでいいのか？ つまりなんでもアリにしちゃうと、設計上様々な不整合があるから 「こういうモナド」を最初に規定してしまい、「モナドに合致しない」記述は コンパイルで弾いてくれるの? 902 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 01:40:52.19 ID:DcI2Tm3Y.net] モナドはDSLプラットフォーム 903 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 08:52:35.38 ID:JMfuFDdS.net] 文脈だって言ってんダロ 文脈を保ちながら普通の値と同じように扱うための規則を定めたものがモナド 904 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 09:06:56.52 ID:t41bY7Zb.net] haskellはモナドじゃないものもコンパイル通しちゃうよ モナドであることの保証は自分でするしか 905 名前：デフォルトの名無しさん [2017/08/18(金) 09:22:11.27 ID:xzRfloCT.net] >>891 モナドってより型クラスがインターフェースに近い。 んで、モナドは型クラスの一つでしかない。 等値を司るEq型クラスのインスタンスになれば=が使える。 大小比較を司るOrd型クラスのインスタンスになれば<や<=が使える。 それと同じ。 逐次処理を司るMonad型クラスのインスタンスになれば>>=とreturnが使える。 IOモナドはIO型を受け取るモナドってだけ。 素のモナドを使うのがほぼIO型しかないからIOモナドって一緒くたにされるけど、IOとモナドは分けて考える。 リストやMaybeもモナドのインスタンスなので、モナドでもある。 モナドが他の型クラスと違うのは、メソッド定義(インターフェースになる関数や演算子をインスタンスになる型で定義)の時にモナド則に則って書く必要があるということ。 それとモナド則を正しく定義できたかは型クラスには無関係なので、定義した人が正しさを保証する必要があるということ。 906 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 09:38:38.34 ID:pIYVRSo1.net] 万能で汎用のDSLも作れるけどそれは手続き型言語と同じだから作らないんだよ IOはごく一部で使われるDSLであるべき 他のところではIOとは別のDSLを使うべきという設計 907 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 13:45:01.90 ID:/WLuQhbG.net] Haskellによる手続き型言語の 分かりやすくて面白い実装きぼん (学習用のおもちゃでよろし) 908 名前：デフォルトの名無しさん [2017/08/18(金) 20:36:40.41 ID:2JfViLUf.net] >>891 ぶっちゃけていうとライブラリ実装者専用の グローバル変数置き場って感じじゃね？ ライブラリのユーザはその中身は気にせずに使う。 909 名前：デフォルトの名無しさん mailto:sage [2017/08/18(金) 21:42:29.70 ID:XJnMHx6C.net] ListTの使い方ようわかりまへん do x <- [1..9] なんちゃらかんちゃら x って、リスト感覚で使いたいんですが 910 名前：デフォルトの名無しさん mailto:sage [2017/08/19(土) 23:56:10.44 ID:3LWi1RRc.net] 直受けの50万 客：いつまでもうちにいていいよ 3次受けの50万（客は70万払ってる) 客：短期延長していい？ 5次受けの50万（客は110万払ってる) 客：作り終わったらとっと出てけ　できなかったら即退場だ　 長時間労働　高稼働　高スキル要求が多い 零細フリーランスサイトは5次受けから誰もできない難易度の高い仕事　余り物の仕事を紹介してくる。40万円代でやってくれと これならJIETから3次でいったほうがいいな 446非決定性名無しさん2017/08/02(水) 22:12:48.95 JIETに毎月5千円払えば３次から入場できるだろ？ 高額をうたうフリーランスのサイトはだいたい５次から４５万円 JIETで閲覧応募できる末端価格からさらに搾取するのが高額をみせつけるフリーランスサイトでした 高額案件をみせつけるフリーランスサイトも案件の取得はJIETでした 473非決定性名無しさん2017/08/03(木) 15:21:30.71 JIETに加入すれば誰でも3次60万からスタートだ。フリーランスのサイトをやってる 自称エージェントもそこから案件情報を取得しきてる。サイトで60万で釣って40万から55万の 間でやらしている。 372仕様書無しさん2017/08/11(金) 10:31:43.41 フリーランスで検索すると引っかかる零細ITがやっているフリーランスのサイトはだめだ。 高額に見せているけど実際は50万前後 JIET加入した方がいいよ。案件は毎日千件以上末端価格は60万円　平凡な稼働時間の80万円の案件もある。 ユー子も求人をだしてる。名刺も渡せる。ユー子に名刺が渡せるんだぞ。夢のようだ それらの案件まさぐってHPで転売していたのが零細ITがやるフリーランスサイト 自称エージェントはJIETから流れてくる案件を転売してるだけだった。 JIETに加入すれば誰でも案件に応募することができた。収入が40万50万台にならなくて済む 911 名前：デフォルトの名無しさん mailto:sage [2017/08/20(日) 03:21:02.15 ID:ZIcYkpAE.net] >>899 x <- ListT $ return [1..9] でもListTはモナドの結合則を破るというか 場合によっては幅優先になるから不用意に使わない方がいい 912 名前：デフォルトの名無しさん mailto:sage [2017/08/21(月) 00:38:33.62 ID:JGSk0hSy.net] >>901 ListTには失望しました。もう積むのやめます 913 名前：デフォルトの名無しさん mailto:sage [2017/08/21(月) 01:01:09.86 ID:JGSk0hSy.net] そもそもやろうとしてることに（よくよく考えたら）モナド変換必要なかった 本当に必要だったのは foldl でした 一方ロシアは鉛筆を使った 914 名前：デフォルトの名無しさん mailto:sage [2017/08/24(木) 13:28:03.79 ID:CtBOeO2p.net] 以下のhogeを定義してください foldl' f a xs = foldr1 seq $ hoge $ scanl f a xs hoge xs = ？？？ 915 名前：デフォルトの名無しさん [2017/08/24(木) 19:41:48.97 ID:QM9NdRuY.net] https://wandbox.org/permlink/HLJOHIGKIX8APzrZ 引数４つのfoldrがよくわからない foldr f g [1..9] 707 916 名前：905 [2017/08/24(木) 20:30:17.00 ID:QM9NdRuY.net] >>905は事故解決しました 917 名前：905 [2017/08/24(木) 20:49:44.49 ID:QM9NdRuY.net] 引数の適用順序の理解が足りないだけでした f x = id id id id id id x というのがあったら f x = (((((id id) id) id) id) id) x という感じに左から順番に適用されるんですね foldr f g [1..9] 707 も (foldr f g [1..9]) 707 と括れば理解できました 918 名前：デフォルトの名無しさん mailto:sage [2017/08/24(木) 23:08:48.67 ID:RV3Vojhw.net] Data.Map.findWithDefault について質問です マップに存在しなかったからデフォルト値を返したのか、それともマップに存在したからそれを返したのか 一目判らないとき、デバッグでどうやって判定しますか？ 919 名前：デフォルトの名無しさん mailto:sage [2017/08/24(木) 23:40:45.91 ID:Drr24sOi.net] 判定不可能でありそれが意図するところじゃね？ 変な値をデフォルトに入れておくか a->k->Map k a->Either a a的なのを用意するしかないんじゃ 920 名前：デフォルトの名無しさん mailto:sage [2017/08/25(金) 00:15:34.79 ID:eQ9TUNW0.net] findWithDefault d k m = maybe (trace "default" d) (trace "existed") $ Map.lookup k m 921 名前：デフォルトの名無しさん mailto:sage [2017/08/25(金) 05:39:52.91 ID:Qp5pyEwS.net] >>910 やったぜ。ドバァーっとヒット/ミス/更新がその時の検索キーと共に時系列で出てきた。 もう気が狂う程気持ちええんじゃ。 ログまみれのコンソールを見つめてメモ化再帰の効果を確認したりした。ああ〜〜たまらねえぜ。（ありがとうございました） 922 名前：デフォルトの名無しさん mailto:sage [2017/08/25(金) 06:18:21.22 ID:eQ9TUNW0.net] わろた 923 名前：デフォルトの名無しさん mailto:sage [2017/08/26(土) 04:35:19.01 ID:gyHjYOL6.net] >>910 ポイントフリー化に成功しました findWithDefault = curry.(.uncurry Map.lookup).(`maybe` trace "existed").(trace "default") https://ideone.com/RVpv4o 924 名前：デフォルトの名無しさん mailto:sage [2017/08/29(火) 10:59:59.32 ID:4lrctZxR.net] 新しい言語を勉強してると「Haskellならこう書けるのになんだかな〜」となってしまう 925 名前：デフォルトの名無しさん mailto:sage [2017/08/29(火) 14:36:34.73 ID:Qxc6OkmQ.net] Haskell書いてると「OCamlならこう書けるのになんだかな〜」となってしまう 926 名前：デフォルトの名無しさん mailto:sage [2017/08/29(火) 14:47:58.47 ID:Ca4b6AZL.net] そま？例えば？ 927 名前：デフォルトの名無しさん mailto:sage [2017/08/29(火) 16:59:34.07 ID:weKjOry2.net] 岡村の方が速いらしいっすよ。でも、そうですね…やっぱり僕は、王道を征く、Haskell系ですか 928 名前：デフォルトの名無しさん mailto:sage [2017/08/29(火) 19:06:06.26 ID:Qxc6OkmQ.net] 多相ヴァリアント 929 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 16:54:11.68 ID:osPI36Tt.net] 双方向リンク系のデータ構造って、Haskell で作るのムズいね。 作るだけなら良いけど、更新時の処理で頭こんがり。 任意のノードに外部からアクセス用リンクが張ってあると もう訳分からん。 930 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 17:07:44.85 ID:YH54NEsT.net] そういうことするなっていう設計の言語で強引にしようとしたらわけわからなくなるよ 931 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 17:18:14.50 ID:osPI36Tt.net] >>920 そういうことするなってのは入門書には書いてないじゃん。 じゃあ、ちょっくらやってみようか、ってなるのがプログラマでしょ。 できるかもしれんし、できんかもしれん。 まぁ、かなりムズいなってのは体験して分かった。 932 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 17:24:15.30 ID:YH54NEsT.net] >>921 あー。Haskellでは状態を変更しない為に単方向リストを用いるって書いてなかった？ 933 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 17:35:40.48 ID:osPI36Tt.net] >>922 リストの定義とか使い方とかは載ってたけど、 なんで単方向のなのかの説明は無かったよ。 「Haskell:The Craft of Functional Programming」 「Beginning Haskell: A Project-Based Approach」 934 名前：デフォルトの名無しさん mailto:sage [2017/08/30(水) 17:47:54.21 ID:YH54NEsT.net] マジかぁ…… 935 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 03:30:11.22 ID:lYwDQiZm.net] Purely Functional Data Structuresなら触れられてるかと思って探してみたけど そもそも双方向連結リスト出てこないな(´・ω・`) でも永続データ構造の概念を知ればなぜ扱われていないかが分かるだろう多分 936 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 05:24:22.47 ID:8YNqT7yd.net] 何で双方向リストの必要なんかあるんですか 途中で戻るとか男らしくないっすよ 937 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 07:18:24.63 ID:3UP7YVEo.net] >>926 巨大な双方向グラフを作ることになったんだけど、 使い方は次の通りちょっと特殊。 * あるノードにアクセスしたら、その近隣のノードも集中的にアクセスすることが多い * ノードが持つ値の読み書きアクセスが圧倒的に多く、グラフの形を変えることは少ない * ノードの値の書き込みアクセスよりは読み取りアクセスの方が多い 既存の汎用的なグラフ ライブラリと、双方向リンクで自作したグラフ ライブラリとで、 どっちが効率いいか実験してみようと思ったんだ。 でも双方向リンクは、ひとつのノードの値を変えるためにどうしてもグラフ全体を作り直す羽目になる。 どうにかならんものかと考えてたけど、どうにもならんね・・・ 938 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 09:37:24.20 ID:z8GPJM/w.net] 「doubly linked list haskell」でググって適当な実装拾う 939 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 11:49:25.22 ID:lYwDQiZm.net] すごハスにあるようなZipper構造かな必要なのは 940 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 12:38:50.35 ID:cadjyHiv.net] 書き換えしないんだったら　([a], a, [a]) 　みたいなので充分なんだよな コモナドにしてどうたらとか余計な話も無視して 941 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 12:49:49.13 ID:3UP7YVEo.net] あの、欲しいのはリストじゃなくてグラフなんだ。 だから、zipper 系とは違う。 942 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 14:03:01.85 ID:UJfUdOL2.net] 最低限木じゃないと効率的かつ単純なのは無理なんじゃないかな？ あんま自信ないけど 943 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 14:05:39.83 ID:3UP7YVEo.net] 皆のレスがどうも勘違いしてると思ってたら、 俺が最初に双方向リンクと言ってしまったからか。 ごめん、相互リンクだ。 944 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 14:16:21.20 ID:3UP7YVEo.net] >>932 木構造でも、親ノードへのリンクを入れると相互リンクになって難しくなるよね。 ひとつのノードの値を変えるためには、 ツリー全体を作り直すことになるんじゃないかな。 HaskellのDOMツリーのデータ構造とかどうなってるんだろ・・・ 945 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 14:36:16.80 ID:3UP7YVEo.net] よく考えたら、リストとかツリーでも、 途中のノードの値を変えたかったら、 そのノードまでリンクで繋がってる全ノードは、 新しくリンクを張り直さなくちゃいけないんだね。 946 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 16:07:16.49 ID:ByIgTrbm.net] そうです。途中の値の変更は リストならO(n) ツリーならO(log n) 947 名前：デフォルトの名無しさん mailto:sage [2017/08/31(木) 17:20:58.63 ID:UJfUdOL2.net] >>934 ランダムアクセスしないなら木に入れなくてもその都度親リストを作ればいいんだけどね なおかつそれをカーソル的に使ってやれば平均で更新のコストも減らせる ってこれzipperか 948 名前：デフォルトの名無しさん [2017/09/01(金) 01:21:03.60 ID:5J9AnuIe.net] 何が何でも１つのプログラミング言語で何とかしようとするのって 異国に行っても母国語で通そうとする観光客と同じ 949 名前：デフォルトの名無しさん mailto:sage [2017/09/01(金) 06:41:46.01 ID:YbmVmXZP.net] >>938 ひとつの言語がどこまでできて、何が得意で何が苦手なのか、 ひとつの言語に集中してそういうのを学ぼうとするのも、 おまえの言う「母国語で通そうとする観光客」カテゴリに入るのか？ 950 名前：デフォルトの名無しさん mailto:sage [2017/09/02(土) 01:43:24.06 ID:6rFZUKZZ.net] >何が何でも１つのプログラミング言語で何とかしようとするのって >異国に行っても母国語で通そうとする観光客と同じ こういうやつにかぎってポリグロッタルコストを甘く見てる 951 名前：デフォルトの名無しさん [2017/09/02(土) 02:26:59.07 ID:zv/5K5Jn.net] 私はHaskell以外のプログラミング言語で書く気はありません 952 名前：デフォルトの名無しさん mailto:sage [2017/09/02(土) 03:52:13.44 ID:qGW8qyv/.net] 慣れるまで大変だけど、慣れたら居心地いい気がする 953 名前：デフォルトの名無しさん mailto:sage [2017/09/02(土) 07:28:06.22 ID:pdF7ruXY.net] 困ったらFFIでC呼び出せばいいだけだから助かる 954 名前：デフォルトの名無しさん mailto:sage [2017/09/08(金) 23:35:36.55 ID:r8Qtf4kd.net] ICFP 2017 で発表された資料、成果や知見はどこかで後悔されたりしないんですか？ 動画が公開されてるんなら、有料でも見たいです。 955 名前：デフォルトの名無しさん [2017/09/09(土) 18:15:24.47 ID:lkyt770O.net] 発表者各自が公開してるの地道に探すしかねーんでないの ICFP Conference(@icfp_confere 956 名前：nce)さん | Twitter https://twitter.com/icfp_conference [] [ここ壊れてます] 957 名前：デフォルトの名無しさん mailto:sage [2017/09/09(土) 20:11:43.28 ID:TPWLKlk7.net] >>945 やはりそうですか。 毎年そうやって発表者や参加者の発信を探すのですが、 分散しており、詳しいことは書いてないことも多く、 情報集めに苦労する割には、たいてい徒労に終わります。 有料でいいので公式がまとめて公開してくれるといいのにと ここ数年つたない英語でメールを出しているのですが、 相手にしてもらえませんね。 すいません、愚痴でした。 958 名前：デフォルトの名無しさん [2017/09/09(土) 23:36:02.27 ID:9IxpzJRD.net] icfpが何なのか知らないけど「icfp video」「icfp paper」で検索してみた ICFP Video - YouTube https://www.youtube.com/channel/UCwRL68qZFfub1Ep1EScfmBw gasche - GitHub https://github.com/gasche ICFP 2016- Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming www.sigplan.org/OpenTOC/icfp16.html フェイスブック、レディっと、ラムダザウルチメイトなどの良く知られた媒体でも 事前告知や事後報告があると思う 959 名前：デフォルトの名無しさん mailto:sage [2017/09/10(日) 00:33:58.75 ID:et8drD+r.net] >>947 指摘を受けて、もしかしてと思い、改めて公式サイトの中を探してみましたら、 paper は公開されていることが分かりました。 過去のも見てみましたら、去年のもの paper にはアクセスできるようでした。 (その前のは公式からはリンクは張られていない模様) video も年によってはリンクが張られていたりします。 なかなかぱっと見では分かりにくいところにリンクがあるのですが、 やはり探し方が悪かったみたいでお恥ずかしいです。 ちなみに、ICFP は国際的な関数型言語の会議です。 使う側、処理系側双方の最新情報を発表したり、 ワークショップが開かれていたりします。 960 名前：デフォルトの名無しさん [2017/09/11(月) 00:32:10.78 ID:Xe2WUSa/.net] 問題解決もしくは近づいたのなら何よりです 961 名前：デフォルトの名無しさん mailto:sage [2017/09/11(月) 23:17:06.08 ID:NiRp1zJ5.net] Haskellの正規表現ってどのライブラリを使うのが無難？ Text.Regex.Posixをimportしようとすると、Text.Regex.BaseかText.Regex.PCREの間違いじゃね？って言われて困惑 962 名前：デフォルトの名無しさん [2017/09/13(水) 18:15:30.36 ID:15e8c4wP.net] (´・ω・`)あのー なにかおすすめの参考書ありませんか？ 初心者です むちゃくちゃ簡単でやさしく書いてるのが良いです アマゾンで見つけて最近出たみたいなんだけどこれはどうなの？ Haskellによる関数プログラミングの思考法 https://www.amazon.co.jp/dp/4048930532/ref=cm_sw_r_cp_api_ozpUzbZS57HY2 963 名前：デフォルトの名無しさん mailto:sage [2017/09/13(水) 19:15:57.75 ID:jV0bEQ9+.net] 正直Haskellで「簡単でやさしく」は無理です 諦めてすごいH本やHaskellWikI,Hoogleや各種書籍、サイトを何度も往復して苦しみながら覚えてください 964 名前：デフォルトの名無しさん [2017/09/13(水) 19:18:52.25 ID:15e8c4wP.net] (´・ω・`)はい 965 名前：デフォルトの名無しさん mailto:sage [2017/09/13(水) 19:53:59.78 ID:4h5PMlCQ.net] すごいHaskell楽しくなんとかって奴がいいらしいよ あとリアルワールドHaskell 966 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 00:00:37.91 ID:55xYcYks.net] https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%BC%E3%83%89%E3%82%A6%E3%82%A7%E3%82%A2%E8%A8%98%E8%BF%B0%E8%A8%80%E8%AA%9E HaskellベースのHDLってけっこう　多いのな ビックリした 967 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 01:28:21.76 ID:kgKbKDJJ.net] >>951 他の人も書いてるけどやはり「すごいHaskell」がとっつきやすさは高いと思う それでいて内容もちゃんとしている 「関数プログラミングの思考法」もいい本だとは思うのだが 目的がアルゴリズムデザインとかの方面であんまり初心者向けっぽくない 968 名前：デフォルトの名無しさん [2017/09/14(木) 06:01:32.83 ID:yKCuCAfu.net] >>954 >>956 (´・ω・`)すごいHaskell読んでみます ありがとー 969 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 09:24:06.36 ID:ux4IsQoU.net] 英語が読めればwikibooksのやつもどうですか？ 自分は"プログラミングHaskell"から入ったので初見じゃないですが、良さげに見えます。 内容も定期的に更新かかってますし。 970 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 10:02:22.29 ID:Yrr+4vGX.net] 「しゅごいHaskell」はダブルVサイン出しながら 読まなきゃいかんのでキーボードが打てない 971 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 16:15:03.19 ID:fLwKChPf.net] What does it mean? 972 名前：デフォルトの名無しさん mailto:sage [2017/09/14(木) 23:15:23.23 ID:BKIQZ2N0.net] He probably meant Haskell wikibook page is upto dated. And that is also why I recommend it for beginners too. 973 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 08:29:13.24 ID:K8WAqD4o.net] >>957 あなたがそもそも関数型プログラミングに慣れ親しんでいないのであれば、まずはそこが第一の壁となるでしょう まずはリストをメインに再帰やマッピング、畳み込みといった操作に慣れましょう またHaskellはデフォルトでカリー化されているのでその妙味も十分に味わいましょう 次に壁となるのは、型や型クラスでしょうか？ ここではクラスやインスタンスといった単語が出てきますが、それらはいわゆるオブジェクト指向で使われているものとは意味が全く違うので注意してください 型に慣れ親しみ、常に適切な型を選択できるよう意識してください そうすればコンパイラがあなたの強い味方となってくれます 最後に入門者の壁となるのは、おそらくモナドでしょう モナドは数学の圏論由来の概念ですが、別段圏論に詳しくある必要はありません 基本的な部分では、モナドは単なる文脈であり、文脈を表すためのコンテナです しかし、それ以上に高度で抽象的なことをやろうとすると、その理解では行き詰まるかもしれません そんなときは、圏論に軽く触れてみるのもいいでしょう 少なくともかの有名な 「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも？」 をざっくりとでもいいので理解できれば、新たな視界が開けると思います Haskellは簡単な言語でもやさしい言語でもありませんが、その代わり高度に抽象化された、バグの少ないプログラミングが可能です あなたの成功を心より祈っています 974 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 08:57:14.76 ID:8dqnOzco.net] 歳を取って反射神経鈍ってくると一々詳細を語るのが億劫になって抽象的なまま話を進めたくなるよね Haskellは抽象的にプログラミングするインフラを整備している？ 975 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 18:00:40.28 ID:d/L5NKte.net] Map a (Map b c) Map (a,b) c どっちが速いかみんな一度は悩んだことあると思う 976 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 22:35:43.14 ID:znUIhbu+.net] 悩まんでしょ 977 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 22:47:16.31 ID:eUG8Jdoq.net] コンパイルしたらどうせ一緒になると思って適当に書いてたけど、変わるの？ 978 名前：デフォルトの名無しさん mailto:sage [2017/09/15(金) 23:09:08.09 ID:4fuQ9N5K.net] Mapは平衡二分探索木だから各Map b cのサイズに開きがあると遅くなるね 979 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 13:16:45.55 ID:u+a6R9+A.net] newtype F a b c = F (Map a (Map b c)) newtype G a b c = G (Map (a, b) c) これでFとGはどうせ一緒のクラスになる こういうポリモーフィズムの意味がわかってる人は速さで悩まない 980 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 15:43:07.25 ID:QR311jcD.net] それは実装を隠蔽しただけで速さの悩みを解決したわけではないのでは… もちろん実装を隠蔽しておいて後でより速い実装に 容易に交換できるようにしておくのは大変有用だが 981 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 20:52:50.94 ID:u+a6R9+A.net] pi :: Floating a => a 円周率piの値を隠蔽し精度の悩みを解決 982 名前：デフォルトの名無しさん mailto:sage [2017/09/16(土) 21:24:55.55 ID:MfZyyhcD.net] 今更だけど、いつの間にか cabal のバージョンが 1 から 2 になってる なんか大きく変わったの？ 983 名前：デフォルトの名無しさん [2017/09/17(日) 08:09:36.24 ID:QPoZRnuU.net] >>4にある解説ページをちらっとみた たしかに数式に似た感じでものすごく簡単に書けるみたいだね たしかに直感的だとおもった 984 名前：デフォルトの名無しさん mailto:sage [2017/09/21(木) 22:09:47.22 ID:1QLcw3LX.net] haskellコンパイラはユーザ定義のモナドが モナド則満たすことを チェックしてくれない所がウンコ 985 名前：デフォルトの名無しさん mailto:sage [2017/09/21(木) 23:00:55.55 ID:gD1zcn0E.net] そんな超能力コンパイラがあるですか？ 986 名前：デフォルトの名無しさん mailto:sage [2017/09/21(木) 23:55:50.59 ID:Y0fSMmUh.net] QuickCheck的なのがコンパイル時に走ってチェックしてくれたりするように そのうちならないかなー 987 名前：デフォルトの名無しさん mailto:sage [2017/09/21(木) 23:58:25.67 ID:h/TDh704.net] モナドを自作したことがないから後学のためにどういう状況でどういうモナドを自作すると効率的なのか教えていただけると幸いです 988 名前：デフォルトの名無しさん mailto:sage [2017/09/22(金) 00:28:53.04 ID:kX95feab.net] 適当に型を作ってたら実はモナドだった、みたいな 989 名前：デフォルトの名無しさん mailto:sage [2017/09/22(金) 16:55:50.20 ID:xffnPG6j.net] 原理的にモナド則のチェックの自動化は不可能なの？ 圏論マスターでも無理なの？ 990 名前：デフォルトの名無しさん mailto:sage [2017/09/22(金) 17:04:50.24 ID:uYwUnAnO.net] ゲーデルさんに聞けばわかるかも。 991 名前：デフォルトの名無しさん mailto:sage [2017/09/22(金) 17:56:16.78 ID:4/60bB6Q.net] ユーザが書いたモナドであることの形式的証明を 検証出来る処理系なら有るはず。 Coq辺り。 992 名前：デフォルトの名無しさん mailto:sage [2017/09/22(金) 19:52:40.81 ID:uE400tii.net] Vectorパッケージで、基本Unboxedにして、 Unboxedに出来なければBoxedにする、 途中でUnboxedにできるなら戻す、 でのを手でやってるのですが、スマートなやり方ってありますか？ 993 名前：デフォルトの名無しさん mailto:sage [2017/09/23(土) 02:53:52.53 ID:7lhkarx+.net] QuickSpecならなんとかしてくれる かもしれない 994 名前：デフォルトの名無しさん mailto:sage [2017/09/23(土) 20:42:11.20 ID:WVPJPMdD.net] stack プロジェクト内の cabal ファイルの build-depends の項に sdl2 を書き込んで、stack build コマンドを実行しました。 すると、sdl2 パッケージのビルドでエラーが出て、「-fPCI を付けて再コンパイルしてください」と出力されました。 そこで stack build --ghc-options="-fPIC" コマンドを実行してみました。 しかし、それでも同様のエラーが起き、ビルドできません。 stack による sdl2 パッケージを利用するプログラムをビルドするにはどうすれば良いでしょうか。 995 名前：デフォルトの名無しさん mailto:sage [2017/09/23(土) 21:51:07.20 ID:58d35SiT.net] >>983 stack.yaml に、 ghc-options: sdl2: -fPIC を追記すればOK。たぶん。 https://github.com/commercialhaskell/stack/blob/master/doc/yaml_configuration.md#ghc-options 996 名前：デフォルトの名無しさん mailto:sage [2017/09/23(土) 22:50:55.76 ID:WVPJPMdD.net] >>984 やってみましたが、結果は変わりませんでした。 今使っている lts-9.5 の snapshot が ~/.stack/snapshot/x86_64-linux-tinfo6-nopie/lts-9.5 にあるのですが、nopie とあり、何か問題に関係ありそうなのですが、どうでしょうか。 997 名前：デフォルトの名無しさん mailto:sage [2017/09/23(土) 23:32:36.23 ID:58d35SiT.net] >>985 うーん、なんだかよくわからないけど、リンクフェーズで”recompile with -fPIC”と言われてしまう問題が報告されていて https://github.com/commercialhaskell/stack/issues/2712 https://docs.haskellstack.org/en/stable/faq/#i-get-strange-ld-errors-about-recompiling-with-fpic これによると、Arch Linux では ncurses5-compat-libs をインストールすると直るらしい。 998 名前：デフォルトの名無しさん mailto:sage [2017/09/24(日) 10:57:49.47 ID:G5x2bhDn.net] >>986 とりあえず先に進めるようになりました。 アドバイスありがとうございました。 たしかに私は ArchLinux を使っています。 Haskell の問題にディストリビューションの違いが絡んでくるとは考えていませんでした。 はじめ ncurses5-compat-libs をインストールしただけでは解決されませんでした。 (ログインし直しても) そこで stack を一度綺麗にアンインストールしてから再インストールし、 それでもダメで、更にビルド時に -fPIC オプションを付けたらエラー無く通りました。 何が原因で処置がどう働いてこういう結果になったのか、まだ何となくでしか分かりませんが、 とにかく SDL を用いたプログラムを試すことができるようになり良かったです。 999 名前：デフォルトの名無しさん mailto:sage [2017/09/25(月) 22:51:00.48 ID:xypOJPnn.net] 集合Aと整数mを引数に取り、Aの可能なm分割全体から成る集合Mを返す関数を作りたいです。 (m分割とは集合論的にm個の集合に分割することとする) 例: 集合 A = {a, b, c, d} と m=2 を引数に取ると、下記の集合Mを返す。 M = {{{a}, {b,c,d}}, {{b}, {a,c,d}}, {{c}, {a,b,d}}, {{d}, {a,b,c}} , {{a,b}, {c,d}}, {{a,c}, {b,d}}, {{a,d}, {b,c}} } 集合を表す型は何でも良いです。 Data.List でも Data.Set でも、その他の型でも。 Haskell で効率よく書けるでしょうか。 ここでいう効率とは、空間よりも時間を優先します。 空間も小さければ尚良いですし、ソースが綺麗ならいっそう良いです。 かれこれ一週間ほど考えていますが (と言っても四六時中ではありませんが)、 なかなか良いアイデアが浮かびません。 前もって言っておきますが、実際の集合Aのサイズはせいぜい20程度で、分割数も2に固定です。 質問のきっかけとなった問題は愚直に実装して解決しました。 なので、この質問は純粋に頭の体操、ゲームです。 1000 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 00:11:58.02 ID:lGqC8DP/.net] 集合の任意の要素m個(nCm)に1〜mの番号を重複なく振る(順列m!)、残りの要素に1〜mの番号を適当に振る(m^(n-m)) 1001 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 07:15:14.90 ID:YKUYL+7U.net] >>989 その方法ですと重複が起きます。 極端な話、集合 {a, b} を 2 つに分割する場合、 番号 1 と番号 2 を重複無く振る方法は2通りあります。 1. a=1、b=2 2. a=2、b=1 残りの要素は無いのでそのまま目的の集合を作ると、 どちらの方法で作っても同じ集合 {{{1}, {2}}} になります。 最後に重複をまとめて排除するのでしょうか。 1002 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 07:27:48.34 ID:8PxDtYJG.net] 部分集合作って差集合とのタプルにして最後に重複省くくらいしか思いつけない 1003 名前：デフォルトの名無しさん [2017/09/26(火) 07:50:17.87 ID:gfUhXOzb.net] {a, b, c, d, e}でm=3なら {a, b, c, d}でm=3のときの答えのリストにmap(:)'e' それに加えて、{a, b, c}でm=2のときの答えに(:)'e' 集合の長さとmが同じならそのまま返す みたいな感じじゃダメ？ 1004 名前：デフォルトの名無しさん [2017/09/26(火) 07:51:32.23 ID:gfUhXOzb.net] 訂正 {a, b, c, d}でm=2のときの答えに(:)'e' 1005 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 10:27:56.68 ID:g1C4tf16.net] >>992 >>993 要素数5でm=3なら、結果の集合の要素数は25ですけど、 その方法で25個すべて出ます？ 1006 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 10:46:10.91 ID:cHfS1yYI.net] inter :: a -> [[a]] -> [[[a]]] inter x = go  where    go [] = []    go (y:ys) = ((x:y):ys) : map (y:) (go ys) part :: Int -> [a] ->[[[a]]] part _ [] = [] part 1 xs = [[xs]] part k (x:xs) = map ([x]:) prev_ks ++ concatMap (inter x) ks  where    prev_ks = part (k-1) xs    ks = part k xs main = print $ part 3 [1..4] 1007 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 21:54:38.15 ID:YKUYL+7U.net] >>995 素晴らしいです。 正直 >>992 の時点では意味が分からなかったです。 (答えに (:a)'e' とか) コード見て意味が分かりました。 1008 名前：デフォルトの名無しさん mailto:.sage [2017/09/26(火) 23:41:18.71 ID:pHNMsW6Q.net] n個の異なる要素のリストから[3,3,4,1,8,...]などとサイズ指定リストに従って分割するときの全列挙をするにはどうしますか？ 分割はサイズ以外に見分けはつかないものとします [[a,b,c],[d,e,f]] と [[d,e,f],[a,b,c]]はダブルカウントです 1009 名前：デフォルトの名無しさん mailto:sage [2017/09/26(火) 23:55:56.84 ID:LAGAI/jv.net] 分割の言葉のお前の定義からきかせてもらおうか。英語でok 1010 名前：デフォルトの名無しさん mailto:sage [2017/09/27(水) 00:47:00.32 ID:wiD7jN/4.net] bunkatsu "abcdefghij" [1,2,3,4] なら [["a","bc","def","ghij"],...みたいにです 1011 名前：デフォルトの名無しさん mailto:sage [2017/09/27(水) 01:19:52.15 ID:iTQClNYA.net] >>999 listl take　自然変換 1012 名前：1001 [Over 1000 Thread.net] このスレッドは１０００を超えました。 もう書けないので、新しいスレッドを立ててくださいです。。。 life time: 254日 1時間 35分 58秒 1013 名前：過去ログ ★ [[過去ログ]] ■ このスレッドは過去ログ倉庫に格納されています

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef