concatのソースコードの意味が分からない
解決済
回答 2
投稿
- 評価
- クリップ 0
- VIEW 3,016
Hoogleでconcatのソースコードを読んでいたのですがソースコードの内容がよくわからなかったので質問しました。
ここで言っている分からないは「concatの使い方が分からない」ではなく「一体このソースコードが何をしているのか分からない」と言う意味です
以下がそのソースコードです。
concat :: Foldable t => t [a] -> [a]
concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
以下が入出力です。
Prelude > concat [[1,2],[3,4]]
[1,2,3,4]では、具体的にどの部分が分からないかですが
「\c n ->」とありますがこの「c」と「n」は一体どこから引数を取っているのでしょうか？
考えたこと
--仮にconcatに[[1,2],[3,4]]を渡した場合
cancat [[1,2],[3,4]] = build (\c n -> foldr (\x y -> foldr c y x) n [[1,2],[3,4]])
--buildはg:[]なので恐らく最終的にこうなるのだろうか？
concat [[1,2],[3,4]] = build(1:2:3:4)
concat [[1,2],[3,4]] = 1:2:3:4:[]
--そうなるとこのラムダ式は「1:2:3:4」を返す
--じゃあ一体cとnは何なんだろうか？
(\c n -> foldr (\x y -> foldr c y x) n xs)-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+2
まず、buildのソース
build g = g (:) []
は、いいですね？ということでconcatのソースからbuildをなくせば
concat xs = (\c n -> foldr (\x y -> foldr c y x) n xs) (:) []
となります。つまり、buildの引数であるラムダ式に、:と[]の引数を与えるのがbuildです。ということで、cとnに入るのは:と[]です。
concat xs = foldr (\x y -> foldr (:) y x) [] xs
fordrが二重になっていてわかりにくいですが、次のように計算していきます。(実際は遅延評価のため、求められるまではそれぞれ計算されませんが)
foldr (\x y -> foldr (:) y x) [] [[1,2][3,4]]
(\x y -> foldr (:) y x) [1,2] $ (\x y -> foldr (:) y x) [3,4] []
(\x y -> foldr (:) y x) [1,2] $ foldr (:) [] [3,4]
(\x y -> foldr (:) y x) [1,2] $ 3:(4:[])
(\x y -> foldr (:) y x) [1,2] $ 3:[4]
(\x y -> foldr (:) y x) [1,2] [3,4]
foldr (:) [3,4] [1,2]
1:(2:[3,4])
1:[2,3,4]
[1,2,3,4]といった感じでconcatできるということです。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
+2
解答の補足です。下記のような定義ですが、
concat :: Foldable t => t [a] -> [a]
concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)本来つぎのような定義でも良いはずです。
concat :: Foldable t => t [a] -> [a]
concat xs = foldr (\x y -> foldr (:) y x) [] xs上のような定義になっている理由としては、このような書きかただと、コンパイラによる最適化がされるからです(RULESプラグマによる書き換えが行われる)。つぎのように最適化されます。
foldr c n (build g) ===> g c n関数concatの例よりも、関数mapのほうが説明しやすいので、関数mapの例を挙げます。たとえば、関数mapが、つぎのように定義されているとします。
map f xs = build $ \c n -> foldr (c . f) n xsこのとき、つぎのようなリストを定義するとします。
nums = map (* 3) $ map (+ 5) [2, 8, 3]これを展開します。
-> build $ \c1 n1 -> foldr (c1 . (* 3)) n1
$ build $ \c2 n2 -> foldr (c2 . (+ 5)) n2 [2, 8, 3]ここで、foldr c n (build g)の形ができていることを確認してください。この形は、g c nのように最適化されるので、
-> build $ \c1 n1 -> (\c2 n2 -> foldr (c2 . (+ 5)) n2 [2, 8, 3]) (c1 . (* 3)) n1
-> build $ \c1 n1 -> foldr (c1 . (* 3) . (+ 5)) n1 [2, 8, 3]のようになります。これを関数mapの形にもどします。上記の関数mapの定義について右の形を左のかたちにするということです。
-> map ((* 3) . (+ 5)) [2, 8, 3]これは結局は、つぎのような最適化をしたことになります。
map (* 3) $ map (+ 5) [2, 8, 3]
-> map ((* 3) . (+ 5)) [2, 8, 3]最適化のまえの形では、リスト[7, 13, 8]が作られますが、最適化後の形では、そのような途中のリストは作られません。これは、関数mapによる変換が、いくつ連続していても、おなじです。
このように、関数buildを利用することで、GHCでは、途中に作られるリストをなくすことができます。それにより、効率が最適化されます。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.35%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる