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

Question

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)

Answer 1

解答の補足です。下記のような定義ですが、

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のソースコード

Answer 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できるということです。