haskell-jp / beginners #23 at 2023-04-10 00:50:36 +0900

こんばんは。学習のために色々な処理をfunctionalなアプローチで書いてみる中で浮かんだ疑問です。

手続き的な書き方は難しくないのに、functionalに書こうと思うと急に難度があがる処理があるように感じ始めています。
当たり前のことなのですが、これは慣れるしかないのですよね……？
自分には到底書けないよと思う処理も、関数型言語に慣れ親しむうちに処理が書けるようになっていくのでしょうか？:smiling_face_with_tear:

例えば`List.GroupBy`をあえて自分で実装するとなると、
手続き型では「forループを回して、毎要素ペアを条件判定し、適宜新しい配列を作成したり既存の配列に追加したり」で済むところが、
関数型では下記のように(*私にとっては*)難しい書き方になってしまいます。

myGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
myGroupBy p xs = foldl step [] xs
    where step ys x | null ys = (x:[]):ys
                    | p (head (last ys)) x = (init ys) ++ (((last ys) ++ (x:[])):[])
                    | otherwise = ys ++ ((x:[]):[])

自力では書けなかったので、 を引用しています(正直、このコードにバグがあるかどうかも私には自信を持っては分かりません)。
このような処理を書けるようになるためには、他言語の習得と同様に練習するしかないのですよね……！

すみません、とても当たり前のことしか言っていないのですが、難しさに圧倒されて思わず何かご意見を伺いたくなってしまい……:eyes:

canalun さんの直面している大変さすごく分かります
自分も最初はループを回して書き換えていく発想しかできなかったのですが、今は foldr や何やらを使って書くのがしっくりくるようになりました
誰もがそうなるかどうかは分からないですが、今 Haskell を書いてる多くの人はそういう経緯をたどったのではないかなと想像します
再現性のある学習かは分かりませんが、自分の場合でいうと、『Scheme 手習い』はリスト操作を再帰的に行うやり方を理解するのにとても助けになりました
Scheme 言語を使った書物ですが学べることは言語に依存しません
canalun さんが勉強していく中で見るコードで「これどういう発想して書いてるんだろう」みたいなことをこのチャンネルとかで聞いてみるのもいいかもしれません
例に挙げた groupBy を書くとしたらまず何から考えるのかとかはコードから読みとるのが難しいですからね
https://www.ohmsha.co.jp/book/9784274068263/

総論はさておき、実際 Data.List の groupBy はもうちょっとシンプルな実装になっているようです。

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

問題を分割して、 span という、「リストにおける指定した条件にマッチする要素まで含んだリストとそれ以降のリスト」を分割する補助関数を使うのがポイントです。
groupBy はその span を繰り返しをグループを一つ作るごとに繰り返し適用することに他なりませんから。

参考:
• https://hackage.haskell.org/package/base-4.17.0.0/docs/src/Data.OldList.html#groupBy
• https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-List.html#v:span

ちなみに不運なことに、挙げていただいた myGroupBy はお手本としては好ましくないです。
現代のHaskellの世界であまり使わない方がいいとされている foldl や head, last を使っている上に、実際の Data.List の groupBy と比べるに、必要上以上に複雑なようなので...

総論について、できれば具体的に書き換える例を用意したいものですが、時間がないので手短にお話ししますと、よくある for ループから純粋な関数に書き換えるコツは、
• とりあえず再帰で考える（`foldr` や map などについては慣れないうちは後でリファクタリングするときに使う。）
• for文などでは、変数を書き換えることでループを進めていたところ、「純粋な関数」の再帰呼び出しでは、*引数の値を変えることでループを進める*、という点を意識する
の2点です。ちょっと具体例がないと分かりづらいかもですが取り急ぎ

意図的なのか分かりませんが、不必要な括弧や冗長な記述があります。（例えば`x:[]`は`[x]`と書ける）これがなくなるだけでも見た目はスッキリするのではないでしょうか。
分かりやすくなるかは分かりませんが、以下のように書き換えてみました。foldrではなく、foldlを使っていますが、リストは前から処理するのが普通なので、計算効率を無視するならfoldlの方がわかりやすいと思います

myGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
myGroupBy p xs = reverse (foldl step [] xs)
    where
        step [] x = [[x]]
        step ((y : ys) : acc) x
                | p y x = (y : ys ++ [x]) : acc
                | otherwise = [x] : (y : ys) : acc

リストは前から処理するのが普通なので、計算効率を無視するならfoldlの方がわかりやすいと思います

よく誤解されるんですが、 foldr も前からの処理ですよ

すみません。誤解を生む書き方でした。
step関数の引数は「現在見ているリストの要素」と「返り値のリスト」ですが、`foldl`の場合は前から計算した「返り値のリスト」を受け取る一方で、`foldr`は後ろから計算した「返り値のリスト」を受け取るため、上のような書き方をしました。

groupBy は foldr より unfoldr のほうがすっきりしますね。
https://scrapbox.io/Haskell-Misc/span%E3%81%AE%E5%B0%8F%E3%83%8D%E3%82%BF%EF%BC%88%E4%BD%BF%E3%81%84%E6%96%B9%E7%B7%A8%EF%BC%89

みなさんありがとうございます……！！

具体的なコツから、コードが読みやすくなる書き方、foldl/foldrの具体的な使い方まで大変勉強になりました:sob:ご紹介いただいた本も読んでみようと思います！

分からないことたくさんあり、今後もここでご質問させて頂くかと思います。その際もまたよろしくお願いいたします:man-bowing::man-bowing: