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

**デフォルトの名無しさん転載ダメ©2ch.net** · 2017/09/27(水) 02:33:08.70

関数型プログラミング言語 Haskell について語るスレです。

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

前スレ
関数型プログラミング言語Haskell Part30
http://mevius.2ch.net/test/read.cgi/tech/1484491434/

**デフォルトの名無しさん** · 2017/10/30(月) 00:12:43.74

今はコンパイラに解決させるようにしているようだね
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.68

中身としてはこれかな
foldlを直す - 純粋関数空間 http://tanakh.jp/posts/2014-04-07-foldl-is-broken.html

>>158のように素直に定義したらどっちでも変わらないのはその通りで、
foldlの方は末尾再帰の形になってるからseqすることでいい感じに動いてくれる

**デフォルトの名無しさん** · 2017/10/30(月) 08:02:56.80

>>162
> >>158のように素直に定義したらどっちでも変わらないのはその通りで、

やっぱり。
これを聞いて安心した。
みんな、ありがと。

**デフォルトの名無しさん** · 2017/10/30(月) 08:39:48.03

foldlを使うことってほぼない気がする
だいたいfoldl'を使ってる

**デフォルトの名無しさん** · 2017/10/30(月) 08:42:25.25

>>160
その問題は、要するにグラフが準オイラー路になっているかどうかを判定するものだよ。

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

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

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

Haskell で素直に拙くプログラムしても特に問題ないだろうね。
たとえば、N個の要素を持つInt型配列にaccumArrayで次数を集計して、
filterで奇数だけ濾し取り、要素数を調べる。

**デフォルトの名無しさん** · 2017/10/30(月) 08:46:34.46

>>164
最適化で正格になるはずだけど明示的に正格版使う必要ある？

**デフォルトの名無しさん** · 2017/10/30(月) 08:49:38.37

>>160
すまん、準オイラー路を判定する前に、
連結グラフかどうかを調べる必要があった。

**デフォルトの名無しさん** · 2017/10/30(月) 09:33:39.10

haskellで連結判定って面倒そう

**デフォルトの名無しさん** · 2017/10/30(月) 11:24:36.92

>>160
>>168
準オイラー路かどうかを判定する前にと言ったけど、
後の方がいいな。

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

これなら、そう面倒でもないような気がする。

**デフォルトの名無しさん** · 2017/10/30(月) 11:28:25.84

>>169
ごめん、ダメだな。

素直にシードフィルみたいに辿っていくしかないか。

**デフォルトの名無しさん** · 2017/10/30(月) 11:57:14.99

最適化O2からなの忘れてたすまん

**デフォルトの名無しさん** · 2017/10/30(月) 12:01:00.21

>>160
Haskell が得意なアルゴリズムは分割統治なので、
できるだけ分割統治で解けないか考える、
というのが一般的なアプローチ。

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

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

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

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

これしかないね。
Haskellにはとことん向かない問題だと思う。

**デフォルトの名無しさん** · 2017/10/30(月) 12:13:21.53

Haskellわからんからわからんのだがこれとか簡単にかけてそうなんだがそうでもないのか？
https://yukicoder.me/submissions/213035

**デフォルトの名無しさん** · 2017/10/30(月) 12:24:13.36

>>173
連結性の判定を忘れてた

**デフォルトの名無しさん** · 2017/10/30(月) 12:25:22.45

>>174
よく見たらWrong Answerだったわ...orz

**160** · 2017/10/30(月) 20:27:20.42

>>165-175
助言ありがとうございました
Haskellは分割統治が得意、連結判定苦手で覚えます

**デフォルトの名無しさん** · 2017/10/30(月) 22:41:45.81

連結判定だけじゃなくてグラフがらみは総じて苦手じゃないかな

**デフォルトの名無しさん** · 2017/10/31(火) 01:03:17.65

コンパイラはグラフ簡約するのに言語はグラフ苦手なのかよお

**デフォルトの名無しさん** · 2017/10/31(火) 01:46:52.15

つうか制約のない連結性の判定を深さ優先探索でするのは別にHaskellのせいじゃないだろ

**デフォルトの名無しさん** · 2017/10/31(火) 03:22:06.20

グラフ苦手って競技プログラミングで使う場合のみやろ？普段使う分にはグラフライブラリに突っ込めばいいだけやし気にする必要無いやで！

**デフォルトの名無しさん** · 2017/10/31(火) 08:27:49.90

ライブラリでも、計算量は多くなるよね？

**デフォルトの名無しさん** · 2017/10/31(火) 08:33:52.06

わざわざ車輪の再発明させる競プロってなんなん

**デフォルトの名無しさん** · 2017/10/31(火) 08:44:38.36

Data.Array.(!) や Data.Vector.(!) って O(1) でアクセスできるんですか？
純粋な関数型言語でそんなこと可能なのですか？

**デフォルトの名無しさん** · 2017/10/31(火) 08:50:21.95

>>182
その方が面白いからだと思いますよ。
コードゴルフとかと同じですよ。
制約があった方が燃えます。

**デフォルトの名無しさん** · 2017/10/31(火) 10:02:54.23

>>183
>Data.Array.(!) や Data.Vector.(!) って O(1) でアクセスできるんですか？
>純粋な関数型言語でそんなこと可能なのですか？

読む分にはO(1)に決まってる
そもそもData.Vectorのドキュメントに様々な関数の計算量が書いてあるだろ

**デフォルトの名無しさん** · 2017/10/31(火) 10:40:05.74

>>185
要素数に依存しない計算量で構造から読み取るなんて、
純粋な関数だけでどうやって実現するの？
不思議すぎない？

**デフォルトの名無しさん** · 2017/10/31(火) 11:15:03.94

はあ？
インデクスからメモリ上の位置（たとえばポインタ）へのO(1)な関数があればいいだけだろ
通常の配列もハッシュも変わらん

**デフォルトの名無しさん** · 2017/10/31(火) 11:25:52.68

ライブラリとして提供されてるからそうであって、
Haskellの構文としては書けないって話では？

**デフォルトの名無しさん** · 2017/10/31(火) 11:28:55.70

>>187
キッシヨ

**デフォルトの名無しさん** · 2017/10/31(火) 11:31:18.73

ミスった
キスしよ、な

**デフォルトの名無しさん** · 2017/10/31(火) 11:33:38.62

>>187
そのO(1)な関数は純粋関数型でどうやって実現してるの？
俺はすげー不思議、という話だよ。

**デフォルトの名無しさん** · 2017/10/31(火) 11:36:03.56

純粋データ型のオブジェクトはすべて構築物
（つまり既存のオブジェクトから構築されたもの）
という視点を持たないとこの手の話は一生理解できんと思う

**デフォルトの名無しさん** · 2017/10/31(火) 11:46:17.59

>>192
このあたり、「純粋関数型データ構造」って本で勉強できる？
それともあの本は関係ない？

**デフォルトの名無しさん** · 2017/10/31(火) 13:07:49.38

1 = \x _ _ ... -> x
2 = \_ x _ ... -> x
3 = \_ _ x ... -> x
~
という自然数を定義すれば
\i -> i a b c ...
で参照O(1)な配列の出来上がり

**デフォルトの名無しさん** · 2017/10/31(火) 13:20:29.54

>>194
それじゃあ、Data.Vector みたいに動的に生成できないでしょ。

ワザととぼけてるの？
それとも話の流れ分かってない？

**デフォルトの名無しさん** · 2017/10/31(火) 13:30:02.62

>>195
\x y z ... -> \i -> i x y z ...

**デフォルトの名無しさん** · 2017/10/31(火) 13:43:09.29

C言語で実装してラップしてんじゃないの（知らんけど）

**デフォルトの名無しさん** · 2017/10/31(火) 13:47:50.97

>>196
すげーおまえ頭いいなって思ったが、すまん、
こっちの頭が悪すぎた、まだ何となくしか理解できん。

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

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

fromList :: [a] -> 配列型 a
fromList xs = ムニャムニャ

**デフォルトの名無しさん** · 2017/10/31(火) 15:36:16.62

C言語で実装してラップしてんじゃないの（知らんけど）

**デフォルトの名無しさん** · 2017/10/31(火) 15:50:28.40

>>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.45

>>200
ありがと

あかん、頭の中で考えてても理解できん、
と言うかスッキリしない。
家に帰ったらじっくり勉強してみるよ。

**デフォルトの名無しさん** · 2017/10/31(火) 18:15:23.97

競プロで使えるグラフライブラリにData.Graphってのあるのな

Data.Graph
https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Graph.html

**デフォルトの名無しさん** · 2017/10/31(火) 19:08:38.44

>>202
上の問題でverticesとreachableの長さを比較すればと思ったら
verticesは辺の無い頂点も列挙する仕様だったわ
まあGraphの中身はリストの配列だから自分で数えればいいんだけど

**デフォルトの名無しさん** · 2017/10/31(火) 21:49:16.80

関数合成ってhoge.piyoよかhoge . piyoの方が可読性高い？

**デフォルトの名無しさん** · 2017/11/01(水) 00:06:04.05

>>204
スペース無しドットはモジュールの名前空間の表現に使うから
関数合成は後者で書く方がいいよ
モジュール名は大文字で関数名は小文字だからコンパイラは間違えないけど

**デフォルトの名無しさん** · 2017/11/01(水) 00:26:27.90

hackageのソースコード見ても合成のドットは離して書いてるの多いね

**デフォルトの名無しさん** · 2017/11/01(水) 00:27:10.19

>>205
やっぱりそうですか
ありがとうございます

**デフォルトの名無しさん** · 2017/11/01(水) 01:06:06.52

人間も間違えねえよってつっかかってくる人昔みかけた
そういう人が出たら、宗教戦争やめろっていうつもりだったのに

**デフォルトの名無しさん** · 2017/11/01(水) 07:53:11.67

「大文字と小文字を間違えない」の主語は何かの戦争か
そもそも主語を書く必要があるのか

**デフォルトの名無しさん** · 2017/11/01(水) 09:43:47.82

データコンストラクタも大文字なので（ry

**デフォルトの名無しさん** · 2017/11/01(水) 11:37:03.55

最初の文字が大文字やドットなら特別な意味がありそう
最初ってどこなのかは正規表現で定義すれば間違いなさそう

**デフォルトの名無しさん** · 2017/11/04(土) 23:17:33.32

リスト内包表記がdo表記に一対一に対応するのは知っていますが、
言語拡張 TransformListComp によって拡張されたリスト内包表記も、
一対一に対応するdo表記があるのでしょうか。

then group by e using f の働きがどのような仕組みなのかよく分からないので、
対応するdo表記を調べて理解を深めたいです。

**デフォルトの名無しさん** · 2017/11/05(日) 08:59:13.86

>>212
>対応するdo表記を調べて理解を深めたいです。

どうぞそうなさって結果をスレにてご報告ください。

**デフォルトの名無しさん** · 2017/11/05(日) 11:02:14.73

>>213
いろいろ実験したり、GHCのユーザーガイドを読んだりしたところ、
then group by p using f の働きが理解できました。

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

代わりに、then group by p using f がどのような働きになっているのか、
私の知見だけでも述べた方が良いでしょうか。

**デフォルトの名無しさん** · 2017/11/05(日) 13:47:42.35

知見は歓迎です

**デフォルトの名無しさん** · 2017/11/05(日) 14:29:15.46

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.19

Haskellの表記を楽にする6つのghc拡張 - Qiita
https://qiita.com/philopon/items/b812e43128654245e42d

**デフォルトの名無しさん** · 2017/11/05(日) 23:15:17.53

>>217
MultiWayIfとBinaryLiterals以外は可読性落ちとるやないかーい

**デフォルトの名無しさん** · 2017/11/05(日) 23:28:42.70

>>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.83

haskell始めてみたいんだけどまだプログラミング能力があまりないので不安
他の言語をどれくらい書けるようにしておくべき？

**デフォルトの名無しさん** · 2017/11/13(月) 23:15:58.10

むしろ手続き型言語に慣れ親しんだ脳みそだと関数型は取っ付きにくいから
いきなりHaskellでいいと思うよ

**デフォルトの名無しさん** · 2017/11/13(月) 23:27:39.67

>>221
Masterminds of Programming という本で Haskell 委員会のひとりが、
他言語をちゃんとできるヤツはHaskellも上手く使える、という趣旨のことを言ってた。

**デフォルトの名無しさん** · 2017/11/13(月) 23:30:10.81

>>221
それどころか、いきなりHaskellをやるのはお勧めしない感じだった。

**デフォルトの名無しさん** · 2017/11/13(月) 23:30:57.19

>>222
「ちゃんと出来る」の意味が、常人と違う予感。

**デフォルトの名無しさん** · 2017/11/13(月) 23:42:04.93

いきなりHaskellの難点はどのHaskell入門書籍やサイトも基本的なプログラミング知識を前提としちゃってるとこかな
変数とか関数とかリストとかマップとか
でもHaskellというか関数型パラダイムにできるだけ早い時期から触れとくのは良いことだと思う

**デフォルトの名無しさん** · 2017/11/14(火) 00:36:12.17

>>220

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

でOCamlやってからHaskellに逝くのが一番簡単な導入

**デフォルトの名無しさん** · 2017/11/14(火) 00:42:09.25

SICP読んでからhaskellやるのは大丈夫？

**デフォルトの名無しさん** · 2017/11/14(火) 02:30:14.88

Haskellは日本語どころか
英語でググっても答えが見つからない問題にぶち当たる率が
他のメジャーな言語と比べると高すぎるから初学者向きじゃないよ

もくもく会に参加したり、Stack Overflowで質問したりと
双方向的な方法を挟まないと一定以上に到達するのは難しい

**デフォルトの名無しさん** · 2017/11/14(火) 11:28:30.93

問題自体が難しい
だから答えが見つからない
と解釈するのが自然

問題自体をよく見ようとせず、SEOや脳味噌のことを考えるのは的外れだと思う

**デフォルトの名無しさん** · 2017/11/14(火) 19:55:37.30

ocamlの元のmlで挫折しそうになった。
f#がたのしい

**デフォルトの名無しさん** · 2017/11/14(火) 20:17:46.83

例えばC言語の楽しさを1とすると
haskell,ocaml,f#の楽しさはどれぐらい？

**デフォルトの名無しさん** · 2017/11/14(火) 21:11:59.47

F#はC#の知識を前提とすることを許可されている感がある
箸の上げ下ろしどころか知識を得るのにも許可を必要とする異常な環境に適応したのがF#

**デフォルトの名無しさん** · 2017/11/14(火) 22:22:03.84

f#はなんかこう昔懐かしbasicの関数型言語版のよう
な気がする。

**デフォルトの名無しさん** · 2017/11/14(火) 22:22:45.27

haskell構文がやだ。

**デフォルトの名無しさん** · 2017/11/14(火) 22:58:23.51

>>234
たとえば、どんな構文が？

遅延評価とか参照透過性とか厳密な型付けとか、そういうのを嫌う人はいっぱいいたけど、
構文が嫌って人には初めて出会った。

**デフォルトの名無しさん** · 2017/11/14(火) 22:59:13.88

F#固有のライブラリ使ったことないな
構文的にC#よりF#楽
あとはHaskell並みの肩推論あれば文句ないんだけど
Haskellは遅延評価使いどころを見つけづらい

**デフォルトの名無しさん** · 2017/11/14(火) 23:31:10.95

結構凝ってるみたいっすねえ

**デフォルトの名無しさん** · 2017/11/15(水) 01:49:26.34

むしろ構文が好きだわ
限りなく不要な物は省く的な

**デフォルトの名無しさん** · 2017/11/15(水) 07:22:37.14

インデントルールにたまにハマるくらいかな
一応ブレース＆セミコロン方式でも書けるようだが

**デフォルトの名無しさん** · 2017/11/15(水) 12:36:08.57

合成関数を左から右に書きたい
何か数学でそんな書き方もあったと思うんだけど忘れた

**デフォルトの名無しさん** · 2017/11/15(水) 17:52:48.58

Control.Arrow の (>>>) 演算子使えばいい
($) の引数入れ替えたヴァージョンなら Data.Function の (&) 演算子

**デフォルトの名無しさん** · 2017/11/15(水) 17:55:11.80

>>239
>一応ブレース＆セミコロン方式でも書けるようだが

標準的なコーディングスタイルだと使わないからなあ……
コード生成のときなんかには便利だけど

**デフォルトの名無しさん** · 2017/11/15(水) 21:31:38.92

Preludeに引数を入れ替えるというだけの関数なかったっけ？
マニアック過ぎて忘れてしまった

**デフォルトの名無しさん** · 2017/11/15(水) 22:05:39.40

つ　flip

全然マニアックじゃないよ……

**デフォルトの名無しさん** · 2017/11/16(木) 19:05:18.93

Haskellが競プロで得意なグラフ問題がatcoderでマラソン形式で出題されているらしい

**デフォルトの名無しさん** · 2017/11/16(木) 20:02:11.38

誰もhaskell使ってないでしょ

**デフォルトの名無しさん** · 2017/11/16(木) 20:10:09.25

使うものじゃないからな。

**デフォルトの名無しさん** · 2017/11/16(木) 20:21:11.26

競プロでHaskell使ってた人は皆Rustに移ったイメージ

**デフォルトの名無しさん** · 2017/11/16(木) 20:28:57.17

競プロは普通に手続き型かつ破壊的の方がいいもんな
入力範囲も固定だし、Haskellで挑む理由がない

**デフォルトの名無しさん** · 2017/11/16(木) 21:32:29.59

関数型っぽく書くと実装が一瞬で完了する簡単な問題が結構あったりはする

**デフォルトの名無しさん** · 2017/11/16(木) 21:43:12.74

競プロより Project Euler で付けた力の方が将来の糧になりそう

**デフォルトの名無しさん** · 2017/11/16(木) 22:35:40.89

Haskellはアルゴリズムをうまくfold系で書ければ
融合則とかで綺麗さと速度を両立できる感じになるけど
うまく書けないとSTRefとか使うことになって
なぜHaskellやってるんだって気分になる

**デフォルトの名無しさん** · 2017/11/17(金) 00:37:00.18

ストリーム処理的にしか使ってない

**デフォルトの名無しさん** · 2017/11/17(金) 00:38:56.41

ストリーム処理的にしか使ってない
https://ideone.com/kYgQxV

**デフォルトの名無しさん** · 2017/11/17(金) 11:21:31.36

>>252
fold系には合わない計算があるのは分かる。

でも、なぜそれでSTRefを使うことになるのかが分からない。

**デフォルトの名無しさん** · 2017/11/17(金) 12:39:19.61

別にIORefやSTRefを使ったっていいじゃない
FFIだってポインターだってあるじゃない
ただしStateモナド、テメーはダメだ

**デフォルトの名無しさん** · 2017/11/17(金) 16:36:27.24

よく知らないけど
カーソル的なクラスと同じように使えるんじゃない？Stateって
Stateモナドに入るのがインスタンス生成で>>=がメソッドコール

**デフォルトの名無しさん** · 2017/11/17(金) 17:56:56.51

1 s -> (a, s)
2 s -> (a -> s -> s) -> s
3 (a -> s -> s) -> s -> s
4 (a -> s -> s) -> s -> [a] -> s

1がStateで4がfoldr

**デフォルトの名無しさん** · 2017/11/17(金) 20:49:15.19

Haskellって他人のコード読むと

▲ a b ＝ □ . ○ $ map ■ $ (△ a) $ ▼ $ ◎ b []
　where
　　◎ b xs =　～長い処理～

こんなんばかりで脳がパンクするんだが

**デフォルトの名無しさん** · 2017/11/17(金) 20:52:24.67

むしろ他人のコードでも割とサクサク読めるのがHaskellのメリットじゃね？