クエリ式で総当たり

.NET

発端

  1. 『C# の yield return の使い道 - u_1rohのカタチ』にコメントを書く．
  2. 久しぶりに yhara くんの『Ruby勉強会＠関西-16「30分でわかるcallccの使い方」- Greenbear Diar』を読み直す．
  3. oxy くんの『Non Determinism - Rubyのある風景』を思い出す．
  4. そういや C# 3.0 なら書けるなぁ．

とまあそんな感じで．

リストモナドで非決定性計算

以上のリストモナドの性質を使うと、総当たりのプログラム、格好よくいうと非決定性の計算を行うことができます。 SICPから次のような問題を借りることにします。

Baker, Cooper, Fletcher, MillerとSmithは五階建てアパートの異なる階に住んでいる。Bakerは最上階に住むのではない。Cooperは最下階に住むのではない。Fletcherは最上階にも最下階にも住むのではない。MillerはCooperより上の階に住んでいる。SmithはFletcherの隣の階に住むのではない。FletcherはCooperの隣の階に住むのではない。それぞれはどの階に住んでいるか。

さて、この問題を解くことにしましょう。次に示すコードを見ると、まるで問題の条件を並べているだけのように見えるかもしれませんが、実はこれで可能な解をちゃんと求めることができます。

import Control.Monad.List

solve = do baker <- [1, 2, 3, 4, 5]
           cooper <- [1, 2, 3, 4, 5]
           fletcher <- [1, 2, 3, 4, 5]
           miller <- [1, 2, 3, 4, 5]
           smith <- [1, 2, 3, 4, 5]
           guard $ distinct [baker, cooper, fletcher, miller, smith]
           guard $ baker /= 5
           guard $ cooper /= 1
           guard $ fletcher /= 1 && fletcher /= 5
           guard $ miller > cooper
           guard $ abs (smith - fletcher) /= 1
           guard $ abs (fletcher - cooper) /= 1
           [baker, cooper, fletcher, miller, smith]

distinct :: Eq a => [a] -> Bool
distinct [] = True
distinct (x:xs) = all (/=x) xs && distinct xs

main :: IO()
main = print solve

実行結果: [3,2,4,5,1]
Non Determinism - Rubyのある風景

これの C# 版を書いてみました．ほとんど直訳で行けますな．

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var answers =
            from baker in Enumerable.Range(1, 5)
            from cooper in Enumerable.Range(1, 5)
            from fletcher in Enumerable.Range(1, 5)
            from miller in Enumerable.Range(1, 5)
            from smith in Enumerable.Range(1, 5)
            where new []{ baker, cooper, fletcher, miller, smith }.Distinct().Count() == 5
            where baker != 5
            where cooper != 1
            where fletcher != 1 && fletcher != 5
            where miller > cooper
            where Math.Abs(checked(smith - fletcher)) != 1
            where Math.Abs(checked(fletcher - cooper)) != 1
            select new { baker, cooper, fletcher, miller, smith };

        foreach (var answer in answers)
            Console.WriteLine(answer);
    }
}

{ baker = 3, cooper = 2, fletcher = 4, miller = 5, smith = 1 }

STL の std::next_permutation みたいなのを先に作るのもありかもしれません．

余談

昨年だったか一昨年だったか，MVP Summit でレドモンドに遊びに行ったとき，波村さんの鞄の中に入っていたのが SICP と Hibernate 本でした．なんというか，この 2 冊を悪魔合体させたら LINQ ができることもあるかもなぁと妙に納得した憶えがあります．