ITコンサルの日常

ITコンサル会社に勤務する普通のITエンジニアの日常です。

perm関数を理解する

前掲の

perm [] = [[]]
perm xs = concat [map (x:) $ perm (delete x xs) | x <- xs]

を理解する。


まず、リスト内包表記(ふつうのHaskellプログラミング p147)で書かれているので、これを普通の書き方に直してみる。

map (x:) $ perm (delete x xs)

の処理を、xsの各要素ごとに行うっていうことなので、この処理を別関数にくくりだして、こうなりました。

import List

main = print $ perm [1,2,3,4]

perm :: [Int] -> [[Int]]
perm [] = [[]]
perm xs = concat $ map perm2 xs
  where perm2 x = map (x:) $ perm $ delete x xs

whereを使ったのは、xsの各要素xも使いたいが、xs自体も参照したいからです。
これで動かしてみると、こうなりました。

[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3]
,[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1]
,[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]
]

ちゃんと出来てるっぽい。