質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.35%

concatのソースコードの意味が分からない

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 3,016

moeii

score 12

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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

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では、途中に作られるリストをなくすことができます。それにより、効率が最適化されます。

参考: モジュールGHC.Baseのソースコード

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る