Just $ A sandbox

プログラミングと計算機科学とかわいさ

トップ > Haskell

foldって難しくないですか

Haskell

foldって難しい、というか書きづらくて読みづらくないですか、と思った話を書きます(そういう感じの話題でTLが盛り上がってたので)

以下、foldをrecursion schemeの観点から理解していることは前提とします

foldをかく

foldを書きたい

foldを書こうと思う場合は自分の場合は明白で、可換monoid積で畳むときは必ずfoldで書きます

sum = foldl (+) 0

これは入力と出力の型が一致していて細かいことを考えなくて良いし、何しているのか見れば分かるし、畳み込み感があっていい感じだし文句はない

ただこういうのは得てしてすでに欲しい関数が定義されてたりする

foldを書きたい？？

これがアキュムレータ付き再帰をしたい場合になると若干微妙で、

f xs = go xs 0 where
  go [] acc = acc
  go (x:xs) acc = go xs (x @@ acc)

-- ↑これが
-- ↓こうなる

f = foldl (@@) 0

上が下になるわけですが、下の方が見やすくていいやんけ、と思うじゃないですか？ しかし下をパッと書くためには困ったことにfoldlの第一引数の型を暗記している必要があるので私はググるかコンパイラがある場面でしか自信を持って下は書けません。

もちろん上より下の方が「良い」コードであることは明白ですが、悪いコードの方が圧倒的に自信を持って書けるのなんかおかしくないかって思いますね。

foldを書きたくない

畳み込み関数がより複雑になる可能性のあるケースでは自分はもうfoldは使いません。それが永久に修正されない、あるいは計算量を保証したいとかでなければもう再帰でいいと思っています。

そもそもこれ以上複雑なケースの場合は自分は一旦再帰の形を経由してしかfoldの処理を理解できないので、わざわざそれを頭の中でやるくらいならおとなしくコードに書けばよいのではないかという気持ちになるからです。

f = go where
  go [] = a0
  go (x:xs) = (なんかめっちゃ複雑な式) $ go xs

-- ↑元の形
-- ↓アキュムレータで書き直す

f xs = go xs b0 where
  go [] acc = acc
  go (x:xs) acc = go xs (さらに複雑な式 x acc)

-- ↓foldで書き直す

f = foldl (さらに複雑な式) b0

例えば一般に何も考えていない時は一番上の書き方をしていて、それをfoldに変えようとすると一旦アキュムレータを使う形に変える必要があります

というわけで真ん中の再帰の形を経由してから一番下に変えるわけですが、一番上から一番下には自分は脳内だけでは変換できません。(脳内ワーキングメモリー足りない人類なので)

そもそも一番下のコードを読むときにも脳内で真ん中の形に展開しないと自分は読めないので、常に真ん中経由なら真ん中でよくないか？ってなるし、計算量とか気にしないならむしろ一番上でいいでしょって思うわけです

この辺は好みや脳内ワーキングメモリーとの相談になりますがプログラムを書く際に極限まで脳みそを使いたくない自分のような人間はこういうケースではまずfoldを使いません。

また、一番上から真ん中は比較的簡単に修正可能ですが、再帰部を色々いじる可能性がある場合も一番下の式で再帰部の形をごりっと書き換えたりするのはかなり大変なので、あとで修正が入りそうな関数も敢えてfoldつかわなかったりします

foldは何がしんどいか

個人的にはこういうことだと思ってる。

foldのつらみを緩和

さて上の3つの問題は例えばこんなふうに書けると割と楽だと思います。

fold {nil: g0} {cons(x): \acc -> gn x acc} xs

まぁ当然タイプ数が増えるわけですが、しかしfoldの引数とnil,consのデータコンストラクタとの対応が見えやすいのでわかりやすいよね？ しかもこれなら一般の代数的データ型に対していい感じのsyntaxが提供できるし！(その場合foldという名前はいかがなものかと思うけれど)

しかし当然Haskellではこんなsyntaxはないのでどうしようもないけれど…じゃあ妥協してこういうのでどうかな

instance TaglessList b where
  nil = acc0
  cons = \x acc -> gn x acc

おっ…これならまだ…ってお前tagless finalやんけ！！！

こんな面倒なことするくらいなら素直にfoldでよくないか

ここまで読んだ上でなお「こんな面倒なことするくらいなら素直にfoldでよくないか」と言えるのは多分脳内ワーキングメモリーが有り余ってる人なのでメモリー分けて欲しい

まとめ

  • fold難しい
  • 避けたいし再帰で書きたいけどパフォーマンス上の問題やらを引き起こす可能性が高まるかもしれないことは常に意識しておくべき
  • Haskell(に限らず大体どの言語もだけど)のsyntaxが悪い説もまぁある
  • tagless finalは便利(ただしこれだけだとリストリテラルで表現されたデータは手に入らないので使うときは注意)
  • 頑張って慣れていきましょう

Haskellでつまずいた所まとめ への回答その2

Haskell

lugendre.hatenablog.com

こちらの記事への回答です。

前回の続き

ただ割と前回と被ってるのでそこはスルーしますねGOMENNNASAI

  • 適切な入門記事がない: 日本語は話者が英語に比べて少なすぎるので敢えて日本語で記事を書くことのうま味がね、はい(英語なら割と情報あります)
  • ライブラリの使い方、Hackageの読み方: そういえばhackageの使い方とかどこにも書いてないし自分もどこで習ったのか忘れてしまったなァ この辺はstackを教える場面でフォローしてあげるべきなのだろうか
  • $ と . : 意外とここで詰まる人多いのかな 型見れば違いは割と明らかな気がするけどそもそも型を頼りにプログラムを書くという言語に慣れてなければ厳しいか
  • 型コンストラクタとkind: これ確かに難しいと思う -> が乱用されてたり不親切な割にはリストやらモナドやらで割と遭遇率も高いし 一応すごいH 8章に解説もあるし、そのへんを見ながらGHCiで遊んで身に付けるとか
  • 型クラスの使い方: 私も苦労したなぁというぼんやりした記憶が(どうやって克服したのか忘れました)
  • Monadへの理解: computationです
  • StateとST: ST使ったことなし
  • パフォーマンスを考えた評価戦略: GHCのユーザーガイドに割とこの辺の話も載っていた記憶が ちなみに日本語版もあります古いけど
  • 適切なライブラリの選択: ちゃんとメンテされてていい感じのインターフェイスを提供しているものがあれば採用し、なければ自作します
  • Category, Arrowの使い所: firstとsecondは便利だけどそれ以外は要らないと思う(暴言)
  • 3つのforall: 普通のforall？とRankNTypesとExistentialQuantificationかな？ 同じforallだけど全部別物と認識したほうが
  • DataKindとは？？？: 初心者でこれいる？？？ konnさんの記事とか昔読んでたけどもう古いと思う
  • Optics関連: 初心者でこれ(ry ただまぁLensは普通に使えたほうがいいので、getterとしてもsetterとしても働く型、ってところを早めに飲み込んでもらうしかないのではないかなぁ(どっちにもなれるようにforallつけとくんやぐらいのノリでいいと思う)
  • ByteString: 今すぐ窓から投げ捨ててTextを使おう！
  • 遅延入出力: ！！！突然の死！！！
  • 関数型設計: Haskellでの設計、人類が未だ到達し得ない地点なので、誰かHaskell設計理論完成させて欲しい
  • NFA: HaskellでNFAとかやったことないし分かりません(大嘘)
  • CPS: これは結構鬼門なので、私としても色々悩んでいるところではある(ひとまずContモナド理解してもらうところが第一歩かな？)(昔記事書きました)
  • 不動点コンビネータ: 初心者がfix使うとこある？？？は置いといてmaoeさんのループと比較した解説とか
  • Rank N types: type system勉強するのが早そう あるいはGHCユーザーガイドが割と詳しい(基本的に言語拡張関連はユーザーガイドに色々乗ってるので)
  • GHCの気持ちがわからない: GHCはお馬鹿なのか賢いのかよくわからない(一応年々成長して賢くなってるという噂がある)のでだんだん付き合って親密度を高めていきましょう
  • 型レベルプログラミング: コンパイル時にできる&&やりたいことか？は常に意識しておくべきな気がしますね
  • 型レや型族まわりの情報収集: 論文読むしかなさそう
  • ekmett神の神託(ライブラリ)の解読: (私は出てませんが)昔ekmett勉強会なるものがあり
  • ストリーム: この辺のライブラリ戦国時代ってどうなったんだろう…(よく知らない) 概観ならHaskellでなぜストリーム処理ライブラリが必要なのか - fujimuradaisuke's blogこの記事なんかがいいかも
  • パフォーマンスチューニング: 出来ませんので分かりません Haskellスペースリークアドベンドカレンダーとかに色々まとまってそう
  • やはり圏論は必要: せやろか
  • 最適化レベル: 個人的に思うこととして最適化とか細かいことは基本的に放っておいてもOKというか、それで大きく結果が変わることはあんまり多くはないという気持ちですね(パフォーマンスチューニングはボトルネックだけにしよう、みたいな)
  • 演算子のinfix: 演算子の優先順位未だにふわふわしてるし適当に決めてるけど 適当なライブラリのやつ見てそれに合わせるとか
  • GHCのGCの動き: よく知りません
  • Profunctorの使い所: 初心者でこれいる？？？(2回目) (->) の一般化ぐらいでどうかひとつ
  • >> の存在意義: >>= \_ -> って書きたくない本当にただそれだけ
  • アルゴリズム: やっぱりPFADとかで地道に勉強するしかなさそう
  • GUI: まともなライブラリが存在しないので作るなら今！っていう宣伝をしていきたい
  • ghc-ios(番外): ｴｯ
  • 関数従属: class Hoge a b | a -> b はaに対してbが一意に決まるという制約、っていう説明でどうかひとつ
  • 理論とコードの結びつけ: categorical semanticsとかやってると論文でよく出会うやつ(お前圏論は要らないとか言っておきながらそういうこと言うのか！わかる)
  • ライブラリを読む: ライブラリを読むのはHaskell力付けるのにはものすごく有用だと思うので、著名なやつはどんどん内部実装読んでいくと力ついていいと思います
  • 練習用の題材: この辺は自分で考えて好きなもの作るしかないんじゃないかなぁ
  • TwitterのHaskeller強すぎ問題: 強くない人は目立たないだけ
  • 初心者がそもそもいない: 入門して挫折した人とかならいっぱいいますね
  • 中級者になるために必要なことがわからない: Effective Haskellっていう、中級者になるために必要なことを網羅した素晴らしい本が出るってききましたよ！
  • 深い記事の必要性: これは自分も思うんですが、やっぱりHaskellぐらい発展途上な言語だと「自分は途中だ」って感覚が少なからずあるのでは、と思います。で、途中だからまとめたくてもまとめられないし細かい記事を書いてる暇があったら先へ進まないと、みたいな感じでやっていってるんじゃないでしょうか。これは成長過程にある言語のいいところでもあり悪いところでもあると思います。
  • テストの話: ライブラリは割とあると思うので、自分でライブラリ探してきて使う気力のある人ならなんとかなると思う(本末転倒感)(個人的にはtastyが好きです)
  • 数学の知識: 自分はこれが不足したことがあんまりないと思うのであんまり分からない
  • 型パズル: パズルってみんないうけど、普通に使いこなしている人は明確な直観と具体例を伴ってプログラム書いてるはずなので、ちゃんと理解して納得していればパズル感は次第に薄れていくのではなかろうかと思います。

終わりに

雑でごめんなさい(ふわっとしてる、と言って欲しい)

もっと細かく教えてください、って言うのがもしあれば、つまづきどころを添えてリクエストをいただけると記事を書いたりするかもしれません

Haskellで躓いた(躓いてる)ポイントまとめ への自分なりの回答

Haskell

qiita.com

こんなふうに各位を焚き付けてしまったのでせっかく色々まとめていただいた記事に対して自分なりに回答をしてみようと思ったので記事をかくことにした

ただしあくまでこれは 私個人的な意見でありコミュニティの総意でも唯一の正解でもない ことを重々ご承知くださいとだけ

色んな意見があっていいと思います(マサカリ回避の構え)

  • 高階関数が分からない: 慣れかなぁ 逆に慣れたら高階関数とそうでない関数を分ける意味がわからなくなる気がする(世の中には高階関数が扱えない言語があるって聞いた)
  • 本は1冊終わったけど次やることが分からん: コマンドラインで動く簡単なツールやらゲームやらスクリプトやらを書いてみるのがいいんではなかろうか
  • 何から始めればいいかが分からない: 本を読む→簡単なものを作ってみる→使えそうなライブラリを勉強する→プロダクトに反映する→またライブラリの勉強するをループする感じ
  • 部分関数こわい: せやろか
  • モナドって何: コンピュテーションを解釈するための型クラス
  • 変数に再代入出来ないとか正気か？: (模範解答)そもそも変数あるいは可変な状態から脱却したプログラミングスタイルに慣れてほしい (だめな解答) D a t a . I O R e f
  • fold系が分からない: わかる 未だに自分もfoldより再帰書いたりしちゃうので少しずつ慣れていけばいいと思う
  • unfoldがもっと分からない: DPしたいときくらいしか使わなくない？
  • 型にIOが付いてしまうと泣きたくなる: モナドを理解しましょう
  • Stateが分からない: モナドを(ry
  • doが怖い: モナ(ry do-notation慣れたら(>>=)とかよりずっと楽に感じられるはず
  • 関数型プログラミングって何: 知らない知らない私は何も知らない
  • ポイントフリースタイルこわい: 可読性の上でも後で書き換える手間の上でも最低限にしたほうがいいと思う
  • パーサーが理解し辛い: Persecモナドは内部実装よりそれが表すcomputationを理解しちゃう方が楽だと思う
  • GHCが分からない: 内部実装よくわからないわかるぅ〜
  • stackがもっと分からない: stackは日々進化してるし進化しすぎて情報が古くなりがちなので細かいところはなるべく公式ドキュメントを参照するようにしたほうがいいかも https://docs.haskellstack.org/en/stable/README/
  • cabalが更にもっと分からない: cabalファイルもhpackで生成する時代だしcabalとか投げ捨てていいのでは？
  • モナドが分かったか分かってないかが分からない: State, IO, Persecあたりで普通にプログラムかけたら多分分かってる方なんじゃなかろうか
  • モナド変換子が分からない: 1. モナドをより大きなモナドに変えられる 2. ベースのモナドのアクションをliftできる みたいなノリでこう(説明になってねぇ)
  • 「理解は出来てないけど使えるようにはなった」をいつまで放置して良いのか: 全てを理解出来てる人いなさそう
  • 関数をどれぐらい分割すれば良いか分からない: 限りなく細かく
  • typeとnewtypeが分からない: typeはただのエイリアス newtypeは別の型
  • UI関連の情報が少ない: UIﾂﾗｲ そもそもHaskellでこういうのに果敢にチャレンジする人あんまりいない感じある
  • 特にTUI: brick好きだけど使ってる人ほぼ見たことない
  • 文字列型が多い: 基本StringでムカついてきたらText
  • 結局圏論は必須なのかどうなのか: いらない派(使ってるお前が言うんじゃねーよ！わかる)
  • インデントスタイルが「これかこれかこれが多いよ」的なのが無い(あったとして、情報が纏まってない): インデント、みんなノリなのでは…お使いのエディタにそれっぽいプラグイン入れてそれに合わせるとか
  • 関数の名前付けがネタ切れする: 名前が思いつかない→分割が足りてない 名前が被る→わかる(わかるじゃなくて)
  • .と$の違いは分かるけど, いつのタイミングでどっちかの判断がし辛い: なるべく . 使いましょう (でも私は a $ b $ c を a . b $ c にするのあんまり好きじゃないのでやらないけど)
  • 関数型プログラミングは分かるけど関数型プログラミングが出来てるかが分からん: 自然に小さな関数を組み合わせてプログラムを組むってことができていればいいんじゃないかな
  • 言語拡張怖い: わかり〜〜〜
  • 逆引き的なの欲しい: こういうのはやはりコミュニティのちからを使ってみんなでちまちま作っていくしかなさそう
  • キモいコードが出てきた時にお手上げ: キモいコードは書く奴が悪い
  • 見たことない演算子がいっぱい: stackでhoogleできるらしいしそれ使うか、stackageの検索もhoogleなのでそれでも出来ますよ
  • その時は理解できても, 次回必要になった時結局使えない: 一般に理解することと使いこなせることはまた別なので
  • 結局letは使わないべきなのか: 使うべき 早く使ってあげてください
  • というか禁じ手一覧が欲しい: そういうのも逆引きと同じくみんなで作っていって欲しい
  • 自分が書いているコードが関数型プログラミングをちゃんと出来ているかが分からない: 上に同じ
  • 自分のコードが汚くて嫌い: 綺麗になるまでがんばりましょう
  • 他人のコードが難しすぎて理解できず, 結局写経しても理解できない: 他人のHaskellコード読む気にならないわかる
  • どのライブラリが良いのか分からん: 色々使ってみて判断しましょう
  • 写経ですら動かないサンプルコードが多い: これは文句言うべき案件では
  • cabalで書かれても入れ方分からん: 今時大体stack installで入りそう
  • Lazy IO怖い: わかるぅ〜〜〜

補足

逆引き的なの

http://dev.stephendiehl.com/hask/

https://github.com/haskell-jp/recipe-collection

この辺かしら

検索したい

https://www.stackage.org/

stackageに入っている奴は全部検索できるはず

関数の命名について

関数の名前が被りそうな時に以下の命名をよくやる気がする

  1. 類義語を使う(call→invokeとか、get→obtainとか): ボキャブラリー誰かくれ〜〜〜
  2. 2単語以上くっつけてみる(callWhenHogeとか makeSomethingとか): かっこわるいけど致し方ない
  3. 似た発音の別の文字にする(class→klassとか、func→fankとか): おしゃれ感あるけど後から見てナニコレってなりそうなので私は避けてます
  4. そもそも関数にしない: 似たような名前の関数を複数定義する前に、それは実は1つのgeneralな関数に抽象化出来ませんか？とか 関数じゃなくて専用のデータ型を作ってデータコンストラクタとして与えられませんか？とか ちょっと上級者向きかも

ポイントフリースタイルについて

関数型プログラミングしてて、関数を組み合わせてプログラムを書くスタイルでは自然と f . g . h みたいな感じになるはずなので関数型プログラミングにおいて自然と発生する書き方がポイントフリースタイルというものなのだと思えばよいのではなかろうか。

少なくともそれは無理に頑張ってそうしたりするようなものではなくてあくまでたまたまそういうのがよく出てくるよねぐらいの気持ちでいいと思います