🔙 Back to Top

Thu Jul 10 03:46:05 JST 2014

リスト内包表記

schemeでリスト内包表記は srfi-42. 一時期よく使ってたので 42 という番号は覚えてる．

Haskellのリスト内包表記をスタンダートと思うなら， リスト内包表記とは次のような言語である．

ListComprehension ::= [ Expression | Patterns ]
Patterns ::= Pattern | Pattern, Patterns
Pattern ::= Var <- List | let Var = Expression | Predicate

例えば

[(x,y,z) | x <- [0, 1, 2], y <- "abc", odd x, let z = (x,y)]
[(1,'a',(1,'a')),(1,'b',(1,'b')),(1,'c',(1,'c'))]

と評価される．

<- は map で表現される．letはletだろう．

リストもなど

私は昔読んだ これ | Combining Monads を思い出してた．

メモ と重複になるが <- については次のように定義できて，

[u] = [u]
[u | x <- ls] = map (\x -> u) ls
[u | p1, p2, .. pn, q] = concat [[u | q] | p1, p2 .. pn]

三番目は再帰部分に相当するのだけど，順序に註意． この順でないと， [x | xs <- xss, x <- xs] を正しく展開できないから， これで正しい．

letもそんなに難しくないだろう.

[u | let x = z] = [let x = z in u]
[u | q1 .. qn, let x = z] = [let x = z in u | q1 .. qn]

Predicate はちょっと困ることになった. filterで簡単にできると思ったけど,

[ y | x <- ls, test]
(filter (lambda (???) (test))
  (map (lambda (x) y) ls))

つまり test は何についての述語なのか分からない． というか，filter より外に x という項は出てこないからわかりようがない．

解決法

モナドもなにもない，コードを書いた 先ほどの

[ y | x <- ls, test]

を

(let ((ret '()))
  (for-each (lambda (x)
    (when test
      (push! ret x)))
  ls))

と書き換える． 展開の順は先ほどと同じではある．

[x | xss <- xsss, xs <- xss, x <- xs]

は

(let ((rec '()))
  (for-each (lambda (xss)
    (for-each (lambda (xs)
      (for-each (lambda (x)
        (push! ret x))
        xs))
      xss))
    xsss))

破壊的代入 push! のおかげで Predicate は単にループをスルー (continue) すればいいだけになった．

コード