関数型プログラミング言語Haskell Part31©2ch.net

■ このスレッドは過去ログ倉庫に格納されています
2017/09/27(水) 02:33:08.70ID:2XAqPuH2
関数型プログラミング言語 Haskell について語るスレです。

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

前スレ
関数型プログラミング言語Haskell Part30
http://mevius.2ch.net/test/read.cgi/tech/1484491434/
2017/10/21(土) 00:23:56.54ID:4Fwr4eN0
https://ideone.com/880zvK
2017/10/21(土) 00:58:52.37ID:Sgt31MqE
>>132
いや、131は揶揄・皮肉だと思う。何スレか前にあった俗説「Haskellでは3ヶ月前に書いた自分のコードが読めなくなる」に対しての。
理由は確か、Haskellでは習熟するにつれてコードが全然違ってくるから、だったかな。
未熟だった頃の考え方とかをスッカリ忘れてしまうので、読んでも頭に入ってこない。

133のコードから漂う、Java上がり臭… 真面目に書いたのも見て取れるんだけど、標準の関数や表記法とズレているのでどうにも読みにくい。

いまstackのコードを読んでるんだけど、意図してコードのレベルを抑えてるフシがある。const を使わずに \_->... と書いてたり。
練度の高低でコードが違ってくることはある意味で良いことといえるのかもしれないけど、多人数で使う際には難しさがあるようだ。
2017/10/21(土) 01:24:40.12ID:E5Mq7+kB
https://ideone.com/q2RCBe

これは >>133 のほぼ 1/10 の行数で書かれている

solve = build “” “”

という行を見て
「ああアキュムレータが2つあるのね」
とわかるのであとはそのまま読むだけ
2017/10/21(土) 01:35:46.03ID:E5Mq7+kB
というか、>>133 のコードはこれはネタでわざとやってるな
2017/10/21(土) 04:25:54.74ID:Sgt31MqE
うひょーッ iOS & Android の ghc バイナリが来た!
http://hackage.mobilehaskell.org/
解説ページ
https://medium.com/@zw3rk/ghc-cross-compiler-binary-distributions-490bb2c0c411
2017/10/21(土) 06:39:56.81ID:M5O/aj/a
何が始まるんです?
2017/10/21(土) 12:52:45.37ID:JKqQJ+2p
自分で書いたコードが、他人が書いたコードと同じに見える

これは普通
同じ書き方をしない方が異常
3ヵ月前の時点ですでに他人が書いたコードと同じに見えていい
2017/10/21(土) 17:28:30.51ID:lv/AbapF
>>135
Data.Mapでもっと単純に書けそうな気がしたけど気のせいだった
https://ideone.com/R4dQIW
2017/10/21(土) 21:05:29.77ID:sahtjmhq
>>124
稟議のロジックをHaskellで書いてくれ。
2017/10/22(日) 09:33:44.39ID:IsEvYiKq
アキュムレータのように引数で変数束縛するのはprologっぽい書き方

haskellならアキュムレータの代わりにwhereを使う手がある
makeMaximumSizeAndMinimumOrderPalindrome wordlist = xs ++ [y] ++ zs where ...
2017/10/22(日) 14:42:07.09ID:b60KFBOe
Intellij IDEAのIntellij-Haskellプラグインが上手く実行できなくて諦めかけてたけど改めて挑戦したらやっとできた
これで俺もIDEデビューだ
開発効率上がるといいな
2017/10/22(日) 15:26:27.37ID:mN+j7loz
アキュムレータの意味がわかってないキチガイがいるのか……
2017/10/26(木) 22:30:22.73ID:/i1iouMm
ByteStringについて、↓の記事に
「使い方の結論を述べると、入力には正格 ByteString、出力は遅延 ByteString を用います」
と書いてあるのですがそうなんですか?
だとしたらなぜそうなるのか教えていただけますでしょうか

http://d.hatena.ne.jp/kazu-yamamoto/touch/20110525/1306298046
2017/10/27(金) 19:45:49.01ID:is9IZ5oJ
CodinGameをHaskellで攻略した方の感想ください

https://www.codingame.com/
2017/10/28(土) 17:22:18.77ID:sV/HPdac
Prelude> let a = 0.3 - 0.2
Prelude> let b = 0.2 - 0.1
Prelude> let c = a == b
Prelude> print c
False

は?

Prelude> default (Rational)
Prelude> let a = 0.3 - 0.2
Prelude> let b = 0.2 - 0.1
Prelude> let c = a == b
Prelude> print c
True

満足〜♪ 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)
2017/10/28(土) 17:23:34.06ID:sV/HPdac
> 入力には正格 ByteString、出力は遅延 ByteString
これ俺も疑問に思ってた
2017/10/28(土) 17:37:14.16ID:vt4jCtcJ
実装上の都合です
理論的には何の根拠もございません
2017/10/28(土) 17:45:11.92ID:zE41SC6F
メモリ的には入力遅延のほうがよさそうだけどハンドルをすぐ解放するために正格ということかな
2017/10/28(土) 19:05:35.06ID:nHlzoa71
512MB of zeroes with different implementations of echo

https://i.imgur.com/i5SkntG.jpg
2017/10/28(土) 20:19:14.51ID:zE41SC6F
どの本だっけ、Real World?
2017/10/28(土) 20:46:38.08ID:DenCC8QE
出典はHaskell High Performance Programmingです
2017/10/28(土) 21:00:26.16ID:zE41SC6F
それか
読みたいと思ってたんだよなそれ
邦訳はよ
2017/10/29(日) 00:46:23.62ID:UfAXS2oV
>>151
正格ByteStringが遅延に買ってる部分ないのか
2017/10/29(日) 07:47:46.53ID:U58o7DSK
普通に配列とリストの違い
ただしリストの要素は32kの配列
2017/10/29(日) 09:00:08.15ID:vzk3gwxY
WAI の実装とかそういう凄え特殊な場面での話だろうな
リソース管理が死活の場面では Lazy IO がワリと死ねるので

でもそういうのはいまなら各種の streaming ライブラリでOK
2017/10/29(日) 22:14:12.00ID:HYvWAe4Y
foldr と foldl ってこんな風に作れるよね。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ i [] = i
foldr f i (x:xs) = f x (foldr f i xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ i [] = i
foldl f i (x:xs) = foldl f (f i x) xs

なんで foldl より foldr の方がメモリ効率がいいのか分からん。
どっちも結果の値が評価されるまで式が数珠繋ぎになったままじゃね?
2017/10/29(日) 22:32:56.88ID:SX8DMS20
これ?

Haskell の畳み込み関数 - foldl, foldr | すぐに忘れる脳みそのためのメモ
http://jutememo.blogspot.jp/2008/06/haskell-foldl-foldr.html
2017/10/30(月) 00:11:55.76ID:kEApsxXD
競プロでhaskell使う場合の何かアドバイスください

この問題解けませんでした
https://yukicoder.me/problems/no/583
https://yukicoder.me/submissions/212458
161デフォルトの名無しさん
垢版 |
2017/10/30(月) 00:12:43.74ID:XzbjUl3p
今はコンパイラに解決させるようにしているようだね
haskell - Foldl memory performance in GHC 8.0.x - Stack Overflow
https://stackoverflow.com/questions/42747159/foldl-memory-performance-in-ghc-8-0-x
2017/10/30(月) 00:31:06.68ID:VIeJ5TeT
中身としてはこれかな
foldlを直す - 純粋関数空間 http://tanakh.jp/posts/2014-04-07-foldl-is-broken.html

>>158のように素直に定義したらどっちでも変わらないのはその通りで、
foldlの方は末尾再帰の形になってるからseqすることでいい感じに動いてくれる
2017/10/30(月) 08:02:56.80ID:WTE/ZW3E
>>162
> >>158のように素直に定義したらどっちでも変わらないのはその通りで、

やっぱり。
これを聞いて安心した。
みんな、ありがと。
2017/10/30(月) 08:39:48.03ID:rELgjW3C
foldlを使うことってほぼない気がする
だいたいfoldl'を使ってる
2017/10/30(月) 08:42:25.25ID:WTE/ZW3E
>>160
その問題は、要するにグラフが準オイラー路になっているかどうかを判定するものだよ。

各駅を頂点、各路線を辺とするグラフが、
準オイラー路であれば彼らは計画達成できるし、
そうなっていなければ計画は達成できない。

グラフが準オイラー路であることと、
次数が奇数の頂点がちょうど2つ存在することとは同値。

要するに、一筆書きができるかどうかだよ。

Haskell で素直に拙くプログラムしても特に問題ないだろうね。
たとえば、N個の要素を持つInt型配列にaccumArrayで次数を集計して、
filterで奇数だけ濾し取り、要素数を調べる。
2017/10/30(月) 08:46:34.46ID:I1PPVtSx
>>164
最適化で正格になるはずだけど明示的に正格版使う必要ある?
2017/10/30(月) 08:49:38.37ID:WTE/ZW3E
>>160
すまん、準オイラー路を判定する前に、
連結グラフかどうかを調べる必要があった。
2017/10/30(月) 09:33:39.10ID:032bj4sa
haskellで連結判定って面倒そう
2017/10/30(月) 11:24:36.92ID:WTE/ZW3E
>>160
>>168
準オイラー路かどうかを判定する前にと言ったけど、
後の方がいいな。

正確には、次数が奇数の頂点がちょうど2つあることを確認した後で、
その2つの頂点間に道があればOKとする。

これなら、そう面倒でもないような気がする。
2017/10/30(月) 11:28:25.84ID:WTE/ZW3E
>>169
ごめん、ダメだな。

素直にシードフィルみたいに辿っていくしかないか。
2017/10/30(月) 11:57:14.99ID:I1PPVtSx
最適化O2からなの忘れてたすまん
2017/10/30(月) 12:01:00.21ID:WTE/ZW3E
>>160
Haskell が得意なアルゴリズムは分割統治なので、
できるだけ分割統治で解けないか考える、
というのが一般的なアプローチ。

だけど、この問題はそれでは解けそうもないので、
他の命令型言語と同じアルゴリズムを使うしかないと思う。

で、これは一筆書き問題なので、
「連結グラフがオイラー路かまたは準オイラー路なら一筆書き可能」
という定理を利用することになる。

オイラー路や準オイラー路の判定は簡単。

肝は連結グラフの判定だけど、これはもう素直に調べるしかない。
普通ならグラフ用ライブラリを使うところだけど、
競技ならまず使えないだろうから、2次元配列を使ってグラフを表現する。
そして頂点をひとつ決めて、そこから全頂点を辿れるか調べる。

これしかないね。
Haskellにはとことん向かない問題だと思う。
173デフォルトの名無しさん
垢版 |
2017/10/30(月) 12:13:21.53ID:/4xzRH5O
Haskellわからんからわからんのだがこれとか簡単にかけてそうなんだがそうでもないのか?
https://yukicoder.me/submissions/213035
2017/10/30(月) 12:24:13.36ID:oL0091Lz
>>173
連結性の判定を忘れてた
175デフォルトの名無しさん
垢版 |
2017/10/30(月) 12:25:22.45ID:/4xzRH5O
>>174
よく見たらWrong Answerだったわ...orz
176160
垢版 |
2017/10/30(月) 20:27:20.42ID:kEApsxXD
>>165-175
助言ありがとうございました
Haskellは分割統治が得意、連結判定苦手で覚えます
2017/10/30(月) 22:41:45.81ID:bEDc9q0a
連結判定だけじゃなくてグラフがらみは総じて苦手じゃないかな
2017/10/31(火) 01:03:17.65ID:hkKKSLGp
コンパイラはグラフ簡約するのに言語はグラフ苦手なのかよお
2017/10/31(火) 01:46:52.15ID:HrVASABH
つうか制約のない連結性の判定を深さ優先探索でするのは別にHaskellのせいじゃないだろ
2017/10/31(火) 03:22:06.20ID:mBYeMGb0
グラフ苦手って競技プログラミングで使う場合のみやろ?普段使う分にはグラフライブラリに突っ込めばいいだけやし気にする必要無いやで!
2017/10/31(火) 08:27:49.90ID:v6NvB8KL
ライブラリでも、計算量は多くなるよね?
2017/10/31(火) 08:33:52.06ID:ipWwIy6g
わざわざ車輪の再発明させる競プロってなんなん
2017/10/31(火) 08:44:38.36ID:DbaXyY3l
Data.Array.(!) や Data.Vector.(!) って O(1) でアクセスできるんですか?
純粋な関数型言語でそんなこと可能なのですか?
2017/10/31(火) 08:50:21.95ID:DbaXyY3l
>>182
その方が面白いからだと思いますよ。
コードゴルフとかと同じですよ。
制約があった方が燃えます。
2017/10/31(火) 10:02:54.23ID:HrVASABH
>>183
>Data.Array.(!) や Data.Vector.(!) って O(1) でアクセスできるんですか?
>純粋な関数型言語でそんなこと可能なのですか?

読む分にはO(1)に決まってる
そもそもData.Vectorのドキュメントに様々な関数の計算量が書いてあるだろ
2017/10/31(火) 10:40:05.74ID:DbaXyY3l
>>185
要素数に依存しない計算量で構造から読み取るなんて、
純粋な関数だけでどうやって実現するの?
不思議すぎない?
2017/10/31(火) 11:15:03.94ID:HrVASABH
はあ?
インデクスからメモリ上の位置(たとえばポインタ)へのO(1)な関数があればいいだけだろ
通常の配列もハッシュも変わらん
2017/10/31(火) 11:25:52.68ID:u1zcRbeB
ライブラリとして提供されてるからそうであって、
Haskellの構文としては書けないって話では?
189デフォルトの名無しさん
垢版 |
2017/10/31(火) 11:28:55.70ID:0GSWnPMN
>>187
キッシヨ
190デフォルトの名無しさん
垢版 |
2017/10/31(火) 11:31:18.73ID:0GSWnPMN
ミスった
キスしよ、な
2017/10/31(火) 11:33:38.62ID:DbaXyY3l
>>187
そのO(1)な関数は純粋関数型でどうやって実現してるの?
俺はすげー不思議、という話だよ。
2017/10/31(火) 11:36:03.56ID:K+wdnCfv
純粋データ型のオブジェクトはすべて構築物
(つまり既存のオブジェクトから構築されたもの)
という視点を持たないとこの手の話は一生理解できんと思う
2017/10/31(火) 11:46:17.59ID:DbaXyY3l
>>192
このあたり、「純粋関数型データ構造」って本で勉強できる?
それともあの本は関係ない?
2017/10/31(火) 13:07:49.38ID:xZzZlui7
1 = \x _ _ ... -> x
2 = \_ x _ ... -> x
3 = \_ _ x ... -> x
~
という自然数を定義すれば
\i -> i a b c ...
で参照O(1)な配列の出来上がり
2017/10/31(火) 13:20:29.54ID:DbaXyY3l
>>194
それじゃあ、Data.Vector みたいに動的に生成できないでしょ。

ワザととぼけてるの?
それとも話の流れ分かってない?
2017/10/31(火) 13:30:02.62ID:xZzZlui7
>>195
\x y z ... -> \i -> i x y z ...
2017/10/31(火) 13:43:09.29ID:xihCdoaS
C言語で実装してラップしてんじゃないの(知らんけど)
2017/10/31(火) 13:47:50.97ID:DbaXyY3l
>>196
すげーおまえ頭いいなって思ったが、すまん、
こっちの頭が悪すぎた、まだ何となくしか理解できん。

たとえば、リストから一次元配列を作る関数をつくってくれないか?

ずうずうしいと思ったら、ヒントだけでも。

fromList :: [a] -> 配列型 a
fromList xs = ムニャムニャ
2017/10/31(火) 15:36:16.62ID:xihCdoaS
C言語で実装してラップしてんじゃないの(知らんけど)
2017/10/31(火) 15:50:28.40ID:xZzZlui7
>>198
いやチャーチエンコーディングのパクリだよ
fromList xs = foldl ($) (\x y z ... -> \i -> x y z ...) xs
実際は型チェックが通らないからアキュームレーターの関数を
data Func a b = Res b | Func (a -> Func a b)
みたいな型で作って結果をパターンマッチすればいい
2017/10/31(火) 16:16:10.45ID:DbaXyY3l
>>200
ありがと

あかん、頭の中で考えてても理解できん、
と言うかスッキリしない。
家に帰ったらじっくり勉強してみるよ。
2017/10/31(火) 18:15:23.97ID:gU/sNGWK
競プロで使えるグラフライブラリにData.Graphってのあるのな

Data.Graph
https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Graph.html
2017/10/31(火) 19:08:38.44ID:1toVIYFj
>>202
上の問題でverticesとreachableの長さを比較すればと思ったら
verticesは辺の無い頂点も列挙する仕様だったわ
まあGraphの中身はリストの配列だから自分で数えればいいんだけど
2017/10/31(火) 21:49:16.80ID:uNFhbghr
関数合成ってhoge.piyoよかhoge . piyoの方が可読性高い?
2017/11/01(水) 00:06:04.05ID:viv8LMSD
>>204
スペース無しドットはモジュールの名前空間の表現に使うから
関数合成は後者で書く方がいいよ
モジュール名は大文字で関数名は小文字だからコンパイラは間違えないけど
2017/11/01(水) 00:26:27.90ID:llNAjsKg
hackageのソースコード見ても合成のドットは離して書いてるの多いね
2017/11/01(水) 00:27:10.19ID:WlWR964+
>>205
やっぱりそうですか
ありがとうございます
2017/11/01(水) 01:06:06.52ID:Fgn1cTLB
人間も間違えねえよってつっかかってくる人昔みかけた
そういう人が出たら、宗教戦争やめろっていうつもりだったのに
2017/11/01(水) 07:53:11.67ID:DzcCU70V
「大文字と小文字を間違えない」の主語は何かの戦争か
そもそも主語を書く必要があるのか
2017/11/01(水) 09:43:47.82ID:55me074h
データコンストラクタも大文字なので(ry
2017/11/01(水) 11:37:03.55ID:DzcCU70V
最初の文字が大文字やドットなら特別な意味がありそう
最初ってどこなのかは正規表現で定義すれば間違いなさそう
2017/11/04(土) 23:17:33.32ID:GxslH7p8
リスト内包表記がdo表記に一対一に対応するのは知っていますが、
言語拡張 TransformListComp によって拡張されたリスト内包表記も、
一対一に対応するdo表記があるのでしょうか。

then group by e using f の働きがどのような仕組みなのかよく分からないので、
対応するdo表記を調べて理解を深めたいです。
2017/11/05(日) 08:59:13.86ID:BXN9Zljm
>>212
>対応するdo表記を調べて理解を深めたいです。

どうぞそうなさって結果をスレにてご報告ください。
2017/11/05(日) 11:02:14.73ID:33a+kqna
>>213
いろいろ実験したり、GHCのユーザーガイドを読んだりしたところ、
then group by p using f の働きが理解できました。

しかし、結局のところ対応するdo表記は分かりませんでした。
そんなものはもともと無いのかもしれません。
もしかしたらCoreを出力してみると何か分かるかもしれませんが、
自分の中ではもう問題が解決しているので、そこまで調べるモチベーションがありません。
なので、ここでその結果を報告することはできません。

代わりに、then group by p using f がどのような働きになっているのか、
私の知見だけでも述べた方が良いでしょうか。
2017/11/05(日) 13:47:42.35ID:iHS/FHvi
知見は歓迎です
2017/11/05(日) 14:29:15.46ID:g7Wivisu
https://downloads.haskell.org/~ghc/7.8.3/docs/html/users_guide/syntax-extns.html#monad-comprehensions
> D[ e | Q then group by b using f, R ] = f (\Qv -> b) D[ Qv | Q ] >>= \ys ->
> case (fmap selQv1 ys, ..., fmap selQvn ys) of
> Qv -> D[ e | R ]
> where Qv is the tuple of variables bound by Q (and used subsequently)
> selQvi is a selector mapping Qv to the ith component of Qv
別にモナドで定義されてるからdoで定義してもいいけど
Qvから要素を取り出す方法がアドホックにしか書けないから
doを使わないにしろ一対一で対応するようには書けない
2017/11/05(日) 18:08:38.19ID:Rt4/SB7E
Haskellの表記を楽にする6つのghc拡張 - Qiita
https://qiita.com/philopon/items/b812e43128654245e42d
2017/11/05(日) 23:15:17.53ID:s0bBqtdw
>>217
MultiWayIfとBinaryLiterals以外は可読性落ちとるやないかーい
2017/11/05(日) 23:28:42.70ID:33a+kqna
>>212 です。

then group by p using f の働きはいろいろ不思議な部分があるのですが、
すべての疑問は、then group by p using f で使う関数 f :: (a -> t) -> [a] -> [[a]] の第1引数は
どのような関数が渡されるのか、ということに集約されました。
(それが分かって初めて、これは then f by p の f でも同じだと気づきましたが、
こちらでは理解につまづかない程度の簡単な例しか扱っていなかったので)

この関数 f は、then group by p using f が現れるより左にある全てのバインダを要素に持つ組から p への関数
と考えれば納得がいきました。

たとえば、
[ (x, y) | x <- [1,2,1], y <- "ok", then group by x using groupWith]
ですと、then より左のバインダを要素に持つ組というのは、つまり
<1, o>, <1, k>, <2, o>, <2, k>, <1, o>, <1, k> といった組です。
(実際に内部で使われている実際のデータ型は分かりません)

このような組から x への関数なので、
g <1, o> = 1
g <1, k> = 1
g <2, o> = 2
g <2, k> = 2
という関数です。
このような関数 g が groupWith 関数の第1引数に渡されると考えると辻褄が合いました。
2017/11/13(月) 22:38:59.83ID:GpiHsSLN
haskell始めてみたいんだけどまだプログラミング能力があまりないので不安
他の言語をどれくらい書けるようにしておくべき?
2017/11/13(月) 23:15:58.10ID:IehbHsjb
むしろ手続き型言語に慣れ親しんだ脳みそだと関数型は取っ付きにくいから
いきなりHaskellでいいと思うよ
2017/11/13(月) 23:27:39.67ID:ZUv/XWe7
>>221
Masterminds of Programming という本で Haskell 委員会のひとりが、
他言語をちゃんとできるヤツはHaskellも上手く使える、という趣旨のことを言ってた。
2017/11/13(月) 23:30:10.81ID:ZUv/XWe7
>>221
それどころか、いきなりHaskellをやるのはお勧めしない感じだった。
224デフォルトの名無しさん
垢版 |
2017/11/13(月) 23:30:57.19ID:PxhTPMZi
>>222
「ちゃんと出来る」の意味が、常人と違う予感。
2017/11/13(月) 23:42:04.93ID:dMdke9KA
いきなりHaskellの難点はどのHaskell入門書籍やサイトも基本的なプログラミング知識を前提としちゃってるとこかな
変数とか関数とかリストとかマップとか
でもHaskellというか関数型パラダイムにできるだけ早い時期から触れとくのは良いことだと思う
2017/11/14(火) 00:36:12.17ID:XSI09cgL
>>220

『プログラミングの基礎』浅井健一

でOCamlやってからHaskellに逝くのが一番簡単な導入
2017/11/14(火) 00:42:09.25ID:Meoq/IF/
SICP読んでからhaskellやるのは大丈夫?
2017/11/14(火) 02:30:14.88ID:RezF4qhu
Haskellは日本語どころか
英語でググっても答えが見つからない問題にぶち当たる率が
他のメジャーな言語と比べると高すぎるから初学者向きじゃないよ

もくもく会に参加したり、Stack Overflowで質問したりと
双方向的な方法を挟まないと一定以上に到達するのは難しい
2017/11/14(火) 11:28:30.93ID:eZNGHHYs
問題自体が難しい
だから答えが見つからない
と解釈するのが自然

問題自体をよく見ようとせず、SEOや脳味噌のことを考えるのは的外れだと思う
2017/11/14(火) 19:55:37.30ID:0CBPSjnu
ocamlの元のmlで挫折しそうになった。
f#がたのしい
2017/11/14(火) 20:17:46.83ID:WUG8DCiI
例えばC言語の楽しさを1とすると
haskell,ocaml,f#の楽しさはどれぐらい?
2017/11/14(火) 21:11:59.47ID:eZNGHHYs
F#はC#の知識を前提とすることを許可されている感がある
箸の上げ下ろしどころか知識を得るのにも許可を必要とする異常な環境に適応したのがF#
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。

ニューススポーツなんでも実況