3

こんにちは、私は現在試験のために勉強していて、回答のトピックに問題がありました。タイトルの状態として、目標は、concat理解リストを使用して非再帰関数を作成し、解決策を検討することです:

concat3 :: [[a]] -> [a]
concat3 xss = [x | xs <- xss, x <-xs]

それでも、なぜそれが機能するのか理解できません。助けていただければ幸いです。

4

2 に答える 2

10

リスト内包矢印は、「xss の xs と xs の x に対して x を読む」(<-)のように「in」と読むことができます[x | xs <- xss, x <- xs]。これは、list-of-lists の各リストをその構成要素にアンパックしていることを示します。concat.

ただし、これを表示する方法はたくさんあります。

機械的に、リスト内包表記はdo表記法に変換されます

do xs <- xss
   x  <- xs
   return x

anddo表記は and に変換され(>>=)ます(>>)

xss >>= \xs -> xs >>= \x -> return x

リスト上でそれらをインスタンス化すると、それ自体がandに(>>=)変わります。concatMapreturn(\x -> [x])

concatMap (\xs -> concatMap (\x -> [x]) xs) xxs

考えてみればconcatMap (\x -> [x])、リストを渡し、各要素をシングルトンリストに取り、それらを連結しているように見えるかもしれません...これは、何もしない複雑な方法です。

concatMap id xss

の定義からconcatMap、

concat (map id xss)

そして最後に（Functorの法則から！または常識から）

concat xss

したがって、関数が動作するのと同じように機能することは驚くべきことではありませんconcat。

do「リストモナド」にいるときに意味的に考える傾向があるため、表記法を解釈するのはどうですか?

do xs <- xss
   x  <- xs
   return x

本質的に、これは「リストのリストから構成リストの1つを非決定論的に選択し、そのリストから要素の1つを非決定論的に選択し、この手順からすべての可能性を収集する」と読むことができます。 、連結しているだけだという考えにつながります。

Control.Monad関数から幸運な通信を取得することもできますjoin

join              :: (Monad m) => m (m a) -> m a  -- this looks `concat`-like!
join x            =  x >>= id

内部を考慮してから、「正しい同一性」モナド法であるイータ変換をxs >>= \x -> return x使用すると、それを確認するのに役立ちますxs >>= return

xss >>= \xs -> xs >>= \x -> return x
===
xss >>= \xs -> xs >>= return
===
xss >>= \xs -> xs
===
xss >>= id
===
join xss

そしてjoin、リストモナドでインスタンス化する方法を調べて見ることができますjoin = concat。

concatしたがって、リスト内包表記をどのように考えたいかによって、リスト内包表記を介して実装されていると見なす多くの方法があります。重要な部分は、これらはすべて同等であり、リストとそのモナドインスタンスが実際に意味するものの基礎を形成するために互いに構築できることです。

于 2013-07-08T06:15:00.403 に答える
7

リスト内包表記は、ネストされたループとして描くことができます。そう、

[ z | x <- list1, y <- list2 ]

は「 for each xin list1、 for each yin list2、yield z」を意味し、結果のリストは、すべての生成された値を順番に集めたものです。ここでは、生成される値がz表記の最初に来ることに注意してください。したがって、次の場合：

[ (x,y) | x <- [1,2], y <- [3,4,5] ]

これは、「 for each xin [1,2]、 for each yin [3,4,5]、yield (x,y)」を示しているため、次のようになります。

[ (1,3), (1,4), (1,5),   -- when x = 1
  (2,3), (2,4), (2,5) ]  -- when x = 2

リスト内包表記のニーモニックを備えているため、定義を読み取ることができますconcat3。

concat3 xss = [ x | xs <- xss, x <- xs ]

読みやすくするために、変数の名前を変更します。

concat3 listOfLists = [ x | list <- listOfLists, x <- list ]

listこれを「 for each in listOfLists、 for each xin list、yield 」と読むことができますx。つまり、最初のリストからすべての要素を生成し、次に 2 番目のリストからすべての要素を生成するというようになります。これは、すべてのリストを連結することに相当します。

私が使用した名前は、実際に見られる可能性はほとんどありません。sリストを表すことを意図した変数には、で終わる「複数の」名前を使用するのが一般的です。xs「エグゼ」と発音します。おそらく言語学的なアナロジーをとりすぎると（しかし、それはまだ一般的な慣例です）、リストのリストを「二重複数化」しますxss。「exeses」はばかげているように聞こえるので、通常は発音しません。xssしたがって、リストのリストであり、リストである名前で見ることができますxs。これは、これらのような密な式を読むのに役立ちます。

于 2013-07-08T06:50:50.933 に答える