リストにおけるdo式

コメント欄で教えて頂きました(ありがとうございました)。

コメント頂いた内容の繰り返しになりますが、理解した内容をなぞっておさらいしたいと思います。

まず、つまずいたのがこの部分。

k m m' = do { x <- m; xs <- m'; return (x:xs) }

do式の理解が不十分だったことが原因。
手持ちの本を紐解いてみると。

一般に、(>>=)を使った式とdo式を使った式とは次のような規則に従って書き換えられます。

式1 >>= 式2
↓↑書き換え可能
do x <- 式1
   式2 x

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門 278ページ

つまり、

do { x <- m; xs <- m'; return (x:xs) }

は、

m >>= (\ x -> (m' >>= (\ xs -> return (x:xs))))

と書き換えることができる(冗長な括弧も書いてます)。

で、ここまでくれば、リストの(>>=)の定義に従って書き換えれば、

concatMap (\ x -> concatMap (\ xs -> [x:xs]) m') m

が得られる。

うまく理解できなかったのは、do { x <- m; ... のところで、xに入るものが何か、と考えてしまったことが原因のようです。正しいかわかりませんが、xには「リストの要素、各々が入っている」ということなのだと思います(リスト内包表記のときのx <- mと同じと思えばいいのではないだろうか)。