トップページ⇒tech
1002コメント312KB

関数型プログラミング言語Haskell Part28 [転載禁止]©5ch.io

レス数が1000を超えています。これ以上書き込みはできません。
0001デフォルトの名無しさん2015/04/10(金) 01:30:32.61ID:KZNYLMbm
関数型プログラミング言語 Haskell について語るスレです。

haskell.org (公式サイト)
http://www.haskell.org/

前スレ
関数型プログラミング言語Haskell Part27
http://peace.2ch.net/test/read.cgi/tech/1420718555/
0952デフォルトの名無しさん2017/01/05(木) 15:57:44.99ID:qnGCBE0G
cost centreではなく?
0953デフォルトの名無しさん2017/01/05(木) 16:40:24.11ID:MABferfQ
>>952
ごめん、単に書き間違えただけ。

cost ね
0954デフォルトの名無しさん2017/01/05(木) 22:58:18.77ID:XwpChIXW
Haskell界隈だとコスト集約点という訳語がよく用いられている模様
意味はGHCのマニュアルなどを参照

第5章 プロファイルを取る
http://www.kotha.net/ghcguide_ja/latest/profiling.html
0955デフォルトの名無しさん2017/01/06(金) 05:48:29.36ID:x6C/Cft1
>>954
これ日本haskell界では有名なサイトなの？

http://www.kotha.net/
0956デフォルトの名無しさん2017/01/06(金) 15:16:05.67ID:5l30YHWE
>>951
同じ意味で使われているのではない？
時間や計算機資源はコストという考えを前提に
0957デフォルトの名無しさん2017/01/07(土) 05:10:29.38ID:JXrYQtFJ
>>951
テクニカルタームというより、会計で使う原価部門の概念を流用しているのでは？
Haskellでのテクニカルタームとしての定義は>>954に書いてあるが、もとの意味はコストがどこで発生したかを管理把握するための会計上の区分。
0958デフォルトの名無しさん2017/01/07(土) 12:31:58.32ID:S46XE+Ca
なぜ語源と定義は同じではないのか

モナドの語源はライプニッツと関係ありそう
だがモナドの定義はライプニッツと全く関係ない
0959デフォルトの名無しさん2017/01/07(土) 14:43:46.03ID:QuS23fJI
Data.Sequence 食べず嫌いしてたけど、これ慣れたら便利そうだな
0960デフォルトの名無しさん2017/01/07(土) 15:38:35.59ID:7iPw9gWV
リストは初めからData.Sequenceっぽい挙動にしてくれれば良いのにな。
細かいチューニングが利用者任せなのも普及しない原因だと思うわ。
0961デフォルトの名無しさん2017/01/07(土) 21:53:37.71ID:S46XE+Ca
これ有限の長さしか扱えないから
無限の長さを遅延評価で処理するリストと同じではない
0962デフォルトの名無しさん2017/01/08(日) 09:07:59.66ID:HXGQkJ06
951 だけど、>>954 のリンク先で理解できた。
みんなの言うとおり、ぴったり合うということで用語を流用してるんだね。
シャノンがエントロピーを流用したのと似た感じか。


ありがと。
0963デフォルトの名無しさん2017/01/08(日) 13:41:38.81ID:s45iu22l
<$>、>>、>>= 等より強い$が欲しいから

infixr 5 $+
($+) = ($)

を使ってるんだけど、邪道かな？
0964デフォルトの名無しさん2017/01/09(月) 21:52:35.01ID:Gy5eZLLr
>>963
個人的にはなんでそんなのが欲しいのか知りたい
0965デフォルトの名無しさん2017/01/10(火) 19:00:40.72ID:f/pmyPVx
それらの演算子の右辺に使いたいって話なら (.) で関数合成すりゃ済むような
0966デフォルトの名無しさん2017/01/11(水) 00:32:30.85ID:4yaLCJvM
ごちゃごちゃ右に続けるより、let か where で一行加えた方が良いマナーでなかろうか
命名に英語の知識が若干必要だけど
0967デフォルトの名無しさん2017/01/11(水) 01:56:24.44ID:4yaLCJvM
＞去年知ったけど、いつの間にか普通の再帰が自動で末尾再帰最適化(ループへ変換)されて

これマジ！？
0968デフォルトの名無しさん2017/01/11(水) 04:35:07.03ID:qB6hV9pT
マジ。
久しぶりに触ったらなってた。
理屈で言えば単純な再帰は末尾再帰に変換するパターンは決まってるから、変形してコンパイルしてくれてるんじゃないかな。
0969デフォルトの名無しさん2017/01/12(木) 21:38:21.22ID:i0JKcY5G
retainerとは何でしょうか
0970デフォルトの名無しさん2017/01/12(木) 21:44:41.00ID:i0JKcY5G
すいません、>>969 は解決しました。
0971デフォルトの名無しさん2017/01/13(金) 16:27:32.91ID:spW6LWtW
"AAABCC" `combi` 3
（ﾀｰﾝ!
["AAA","AAB","AAC","ABC","ACC"]

ってやりたいんですがどうやりますか？ 但し一杯生成してから余計なの省くのはナシで
0972デフォルトの名無しさん2017/01/13(金) 16:43:30.15ID:sdnCdlet
combi "AAABCC" 3 = ["AAA","AAB","AAC","ABC","ACC"]
0973デフォルトの名無しさん2017/01/13(金) 17:11:30.27ID:Y/PhWwOJ
>>971
例だけじゃなくて、関数の仕様もできるだけ詳しく教えて
0974デフォルトの名無しさん2017/01/13(金) 17:13:03.00ID:spW6LWtW
けちんぼ！
0975デフォルトの名無しさん2017/01/13(金) 17:20:14.39ID:spW6LWtW
>>973
組合せです。
入力は重複を含む要素のリストで
出力はそのリストからn個選んだリストのリストです
しかし出力に重複は許されません

例えば "AAAAAAA" `combi` 3 == ["AAA"] です

実装に関して、一杯生成してからnubはダメです

例えば "AAAABBB" `combi` 3 == ["AAA","AAB","ABB","BBB"] です
0976デフォルトの名無しさん2017/01/13(金) 17:26:32.27ID:Y/PhWwOJ
>>975
後から重複を取り除く方法全般がダメなの？

それとも、たとえばソートしてからグルーピングして
先頭要素だけ取る方法はOK？
0977デフォルトの名無しさん2017/01/13(金) 17:37:44.30ID:spW6LWtW
出力される各リストは、例えば "AAB" と "ABA" は同じとみなされます（Aが２つ、Bが1つ選ばれているという意味で同じとみなすのです）
0978デフォルトの名無しさん2017/01/13(金) 17:39:24.14ID:spW6LWtW
>>976
それはいいです
0979デフォルトの名無しさん2017/01/13(金) 18:09:13.37ID:KeMBxxc7
できた？

runlen [] = []
runlen (x:xs) = rl x 1 xs
rl x k [] = [(x,k)]
rl x k (y:ys) = if x == y then rl x (k+1) ys else (x,k) : rl y 1 ys
combi' [] _ = []
combi' [x] y = if x >= y then [[y]] else []
combi' (x:xs) y = [ h : t | h <- reverse [0..min x y], t <- combi' xs (y-h) ]

combi str n =
let xs = runlen str in
let str' = map fst xs in
[ concat (zipWith replicate y str') | y <- combi' (map snd xs) n ]
0980デフォルトの名無しさん2017/01/13(金) 19:00:59.49ID:spW6LWtW
>>979
ありがとうございます
0981デフォルトの名無しさん2017/01/13(金) 19:14:20.11ID:Y/PhWwOJ
>>978
それなら、組み合わせを計算してから、ソート・グルーピング・map head すればいいだけなのでは？
0982デフォルトの名無しさん2017/01/14(土) 01:09:18.39ID:qkQ2nYQV
Elmって面白いね。初めて関数型言語が実戦で使えた感じ。
0983デフォルトの名無しさん2017/01/14(土) 01:50:04.25ID:qj8F+4RU
>>981
ああ、やっぱそれだとソートしてグルーピングの計算オーダーがnubするのと変わらない事態を招く気がしますのでダメになっちゃいますね


要は愚直実装より速いものが欲しかったのです。重複を含む巨大なリストから数個取り出す組合せをリストアップしようとすれば、愚直実装ではフリーズしてしまいまして
0984デフォルトの名無しさん2017/01/14(土) 07:24:46.87ID:mdG3n9u6
>>983
ソート済みリストに対する重複削除はちゃんと定義すればO(n)で動くから
ソートがO(n log n) で動けば全体もO(n log n) になるので
Haskellの一般のリストに対するnub のO( n^2) より速いはず
0985デフォルトの名無しさん2017/01/14(土) 08:37:41.01ID:z+PGQfym
import Data.List

comb :: String -> Int -> [String]
comb xs = comb' ((group . sort) xs)
where
comb' ys n
| n == 0 = [[]]
| (null . head) ys = comb' (tail ys) n
| (length . concat . tail) ys < n = map ((head . head) ys :) (comb' ((tail . head) ys : tail ys) (n - 1))
| otherwise = map ((head . head) ys :) (comb' ((tail . head) ys : tail ys) (n - 1)) ++ comb' (tail ys) n

こんな感じで組み合わせを求めることはできると思うんだけど速度的には難ありってことなんでしょうか
そのあたりのことを知りたい
0986デフォルトの名無しさん2017/01/14(土) 09:46:02.22ID:z+PGQfym
import Data.List

comb :: String -> Int -> [String]
comb xs = comb' ((group . sort) xs)
where
comb' ys n
| n == 0 = [[]]
| (null . head) ys = rs
| (length . concat . tail) ys < n = ls
| otherwise = ls ++ rs
where
ls = ((head . head) ys :) <$> comb' ((tail . head) ys : tail ys) (n - 1)
rs = comb' (tail ys) n

汚かったので整えた
0987デフォルトの名無しさん2017/01/14(土) 13:45:42.41ID:BE8dMuIV
comb :: String -> Int -> [String]
comb xs n
| n == 0 || null xs = [[]]
| otherwise = do
l <- [0..m]
zs <- comb ys (n - l)
if length ys >= n - l then
return $ replicate l x ++ zs
else
[]
where
x = head xs
ys = filter (x /=) xs
m = min n $ (length xs - length ys)


>>985だけど多分こういうやり方のほうがいいのかな
0988デフォルトの名無しさん2017/01/14(土) 14:38:17.99ID:eAnfzjs/
みんな両極端だよな
平気で嘘、誤答を書く時もあるし、速度的に？最も正しい答えを書きたがる時もある
0989デフォルトの名無しさん2017/01/14(土) 23:05:47.30ID:ARUXoNoj
最強のアルゴリズマーさんに聞くしかないな
0990デフォルトの名無しさん2017/01/15(日) 10:11:21.74ID:wEixuQp0
書いてる方もよくわかってないんだよ
0991デフォルトの名無しさん2017/01/15(日) 10:47:54.19ID:Lz2CPGKK
プログラミング自体趣味でやってるだけで教養のようなものがなく
具体的な指摘はとても勉強になるのでお願いしたいです

Haskellって日曜プログラマには最適な言語なんじゃないかな。アイデアを形にする過程がすごく楽しい
0992デフォルトの名無しさん2017/01/15(日) 13:07:09.67ID:SnguMZvf
教養ってそんな綺麗なものではなく非科学的なものが一杯入ってる
かといって科学をただ否定すりゃいいってものでもない
0993デフォルトの名無しさん2017/01/15(日) 13:30:05.19ID:Lz2CPGKK
>>992
科学と実用性の駆け引きというのか協力というのか、そういう絶妙な連携は魅力的ですね


ところで組み合わせの問題グルーピングよりも[("A",3),("C",2),...]みたくはじめに個数を数えたほうが少し速くなりました
0994デフォルトの名無しさん2017/01/15(日) 16:16:50.57ID:40h2fwNv
Haskellは数学で科学はPythonでは
0995デフォルトの名無しさん2017/01/15(日) 16:26:11.57ID:nEHh2xZn
数学を名乗るには線形代数が弱い
0996デフォルトの名無しさん2017/01/15(日) 18:02:21.49ID:Vh4eztBk
15万文字のソート済み文字列で >>979で48秒で終わる処理が、>>985から最初のソートを抜いた版だと2000秒かかりました
0997デフォルトの名無しさん2017/01/15(日) 21:36:53.35ID:VKnf+7zn
>>991
スマホ対応が終わってるのがなぁ・・・
今時自分のスマホでも自作アプリ動かしたいですやん
0998デフォルトの名無しさん2017/01/15(日) 21:52:48.96ID:KJfp/lQK
>>996
文字をそのまま足すんじゃなくて個数として抽象化した方が良いってことですね。言われてみれば当然ですが勉強になりました
0999デフォルトの名無しさん2017/01/15(日) 22:08:25.90ID:SnguMZvf
スマホの良いところは一人一台
発電所みたいに一箇所で大規模にやった方が安いという考えは古いのかも
1000デフォルトの名無しさん2017/01/15(日) 22:08:43.69ID:zF8FuE9b
aojの問題でわからないところがあるので質問します．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
二股にわかれた容器に1から10まで番号のついたボールを番号の大小関係の制約を守って並べていけるかを判定する問題なんですが，自分のコードを提出するとruntime errorになってしまいます．
理由も考えたんですがよくわからないので，何がダメなのかアドバイスをお願いしたいです．


main :: IO ()
main = getContents >>= mapM_ (putStrLn . (\arr -> solve (tail arr) 0 (head arr, 0)) . map (read :: String -> Int) . words) . tail . lines

solve :: [Int] -> Int -> (Int, Int) -> String
solve arr index (box1, box2)
| index == length arr =
10011001Over 1000Thread
このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。
life time: 646日 20時間 38分 11秒
10021002Over 1000Thread
２ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。


───────────────────
《プレミアム会員の主な特典》
★ ２ちゃんねる専用ブラウザからの広告除去
★ ２ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────

会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。

▼ プレミアム会員登録はこちら ▼
http://premium.2ch.net/

▼ 浪人ログインはこちら ▼
https://login.2ch.net/login.php
レス数が1000を超えています。これ以上書き込みはできません。