Haskellでlist monadを使って完全順列を生成してみました

完全順列（撹乱順列とも）とは順列を置換と見た場合、不動点をもたない置換のことをいいます。順列の要素数を無限大にした極限をとったとき、完全順列の個数(モンモール数)とすべての順列の個数(n!)の比が1:e(eは自然対数の底)になり、世の中の物好きを惹きつけています。
前回のN-Queens問題につづいてlist monadを利用して関数型言語のHaskellで完全順列を生成するコードを書いてみましょう。

*Main> derangement ['c','o','n','s']
>>["ocsn","onsc","oscn","ncso","nsco","nsoc","scon","snco","snoc"]

こんな感じになって欲しいのです。順列を生成した後にfilterを掛けるのは非効率的なのでやめておきます。
書いてみると以下のようになりました。

import Data.List

derangement xs = drg xs xs

drg [] ys = return []
drg xs (y:ys) =
  delete y xs >>=
  \x -> map (x:) (drg (delete x xs) ys)

Monadを利用することを考えると、こんなに簡単に書けるんですね。
素晴らしきかな、Haskell、Monad！