Rubyでリストモナドぽい何か

http://mono.kmc.gr.jp/~oxy/w/hiki.cgi?Non%20Determinismにあるリストモナドで非決定性計算をRubyでHaskellぽく解いてみようと思います。問題はこれです。元はSICPらしいです。

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

Haskellの回答はこちら。リストモナドがおしゃれです。

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

普通にRubyで解くとこんな感じ。

#!/usr/bin/env ruby

module Enumerable
  def distinct?
    table = {}
    each do |e|
      return false if table[e]
      table[e] = true
    end
    return true
  end
end

solve = []
[1, 2, 3, 4, 5].each do |baker|
  [1, 2, 3, 4, 5].each do |cooper|
    [1, 2, 3, 4, 5].each do |fletcher|
      [1, 2, 3, 4, 5].each do |miller|
        [1, 2, 3, 4, 5].each do |smith|
          next unless [baker, cooper, fletcher, miller, smith].distinct?
          next unless baker != 5
          next unless cooper != 1
          next unless fletcher != 1 and fletcher != 5
          next unless miller > cooper
          next unless (smith - fletcher).abs != 1
          next unless (fletcher - cooper).abs != 1
          solve << [baker, cooper, fletcher, miller, smith]
        end
      end
    end
  end  
end
p solve

Haskellみたいにモナドのアイデアを取り入れるとこうなります。ArrayMonadモジュールで、Arrayの足し込みを隠蔽しています。

#!/usr/bin/env ruby

module Enumerable
  def distinct?
    table = {}
    each do |e|
      return false if table[e]
      table[e] = true
    end
    return true
  end
end

module ArrayMonad
  def mbind(a, &f)
    a.inject([]) {|r, e| r += f.call(e) }
  end

  def mzero
    []
  end

  def mreturn(v)
    [v]
  end
end

include ArrayMonad

solve = mbind([1, 2, 3, 4, 5]) do |baker|
  mbind([1, 2, 3, 4, 5]) do |cooper|
    mbind([1, 2, 3, 4, 5]) do |fletcher|
      mbind([1, 2, 3, 4, 5]) do |miller|
        mbind([1, 2, 3, 4, 5]) do |smith|
          next mzero unless [baker, cooper, fletcher, miller, smith].distinct?
          next mzero unless baker != 5
          next mzero unless cooper != 1
          next mzero unless fletcher != 1 and fletcher != 5
          next mzero unless miller > cooper
          next mzero unless (smith - fletcher).abs != 1
          next mzero unless (fletcher - cooper).abs != 1
          mreturn [baker, cooper, fletcher, miller, smith]
        end
      end
    end
  end  
end
p solve

んー、いまひとつRubyだとうれしさが半減しますね。<-とかguardとかのシンタックスシュガーが用意されていないのがその原因かなー。