没专门语法支持的语言里用monad好难看

上周在JavaEye问答看到求一个逻辑运算结果，其中De Morgan定律的应用如night_stalker老兄所说，并不困难。不过就这么应用定律来推算或许不直观，所以当时我就想换个角度，写段C#代码来穷举验证问题中的表达式在应用De Morgan定律前后的真假值是否总是相同。

通过LINQ，代码很简洁：

using System;
using System.Linq;

static class Program {
  static void Main(string[] args) {
    var booleanValues = new [] { true, false };
    var equal = !(from a1 in booleanValues
                  from a2 in booleanValues
                  from a3 in booleanValues
                  from b1 in booleanValues
                  from b2 in booleanValues
                  from b3 in booleanValues
                  select (!((a1 && b1) || (a2 && b2) || (a3 && b3))) ==
                         (!(a1 && b1) && !(a2 && b2) && !(a3 && b3)))
                  .Contains(false);
    Console.WriteLine(equal); // true
  }
}

这段代码看起来应该算是比较直观的。不过……似乎又不太直观？

对许多人来说，或许显式用循环会直观得多：

using System;

static class Program {
  static void Main(string[] args) {
    var booleanValues = new [] { true, false };
    var equal = true;
    foreach (var a1 in booleanValues) {
      foreach (var a2 in booleanValues) {
        foreach (var a3 in booleanValues) {
          foreach (var b1 in booleanValues) {
            foreach (var b2 in booleanValues) {
              foreach (var b3 in booleanValues) {
                if ((!((a1 && b1) || (a2 && b2) || (a3 && b3))) !=
                    (!(a1 && b1) && !(a2 && b2) && !(a3 && b3))) {
                  equal = false;
                  break;
                }
              }
              if (!equal) break;
            }
            if (!equal) break;
          }
          if (!equal) break;
        }
        if (!equal) break;
      }
      if (!equal) break;
    }
    Console.WriteLine(equal); // true
  }
}

但这代码好丑啊 =v=
好吧我作 弊了。就以上两个版本的代码来比较，它们实际的执行过程是不同的；LINQ的版本是会把所有可能性都算出来之后再看是否Contains()，因为Contains是一个eager operator，不像Select、Where那些是lazy的；循环版是遇到不相等的状况就直接退出循环了。不过反正两个版本算出来的结果都一样，用来对比也不算过分。

其实C#的foreach循环已经掩盖了许多细节，不需要显式用下标或者IEnumerator来遍历容器。不过我还是不喜欢在这种场景用显式的循环，主要是因为循环嵌套起来非常难看，搞不好就要超过屏幕的右边了。

之前说LINQ的版本看起来简洁，但未必很直观，是因为：多个from子句连在一起对应的函数是SelectMany，对IEnumerable<T>/IQueryable<T>而言这个LINQ运算符背后的概念则是list monad中的bind函数；其中的机理还是需要读些资料才能理解的。一看到monad这词很多人就要开始晕了吧？ =w=

本来是想list monad在C#通过LINQ来使用可以这么简洁，那要是能在Ruby里也这样用就好了。但如标题所说，语言没有提供monad语法的时候，这玩儿写起来也不优雅。其实更关键的问题或许是没有typeclass的条件下monad无法提供统一的接口来提高抽象层次？不过我只想关心语法，也就是“看起来如何”的问题。

例如说，用Ruby来实现一个maybe monad：

class Maybe
  def initialize(val, has_val = true)
    @value, @has_value = val, has_val
  end
  
  def value
    raise 'Maybe::None has no value' unless @has_value
    @value
  end
  
  class << self
    def unit(val)
      new(val).freeze
    end
  end
  
  def bind
    @has_value ? (yield @value) : Maybe::None
  end
  
  def none?
    self == Maybe::None
  end
  
  def clone
    raise TypeError, "can't clone instance of Maybe"
  end
  
  def dup
    raise TypeError, "can't dup instance of Maybe"
  end
  
  None = Maybe.new(nil, false).freeze
  
  private_class_method :new, :allocate
end

定义了Maybe类之后，可以这样用：

res1 = Maybe.unit(1).
             bind { |x| Maybe.unit(x + x) }.
             bind { |x| Maybe.unit(x * x) }
#=> #<Maybe:0x34bc3e8 @has_value=true, @value=4>

看起来还不错，方法调用没有嵌套，都是串在一起的。
但这只不过是因为这一连串计算是从单一的来源得到数据的：那个“1”。假如要把一个“1”和一个“2”都用Maybe包装起来，然后要得到它们的和，那就变成：

one, two = [1, 2].map { |i| Maybe.unit i }
res2 = one.bind { |x|
         two.bind { |y|
           Maybe.unit(x + y)
         }
       }
#=> #<Maybe:0x35ece5c @has_value=true, @value=3>

于是bind的调用就嵌套起来了，郁闷 T T

我一时觉得纳闷，明明记得在Haskell里写的时候即使不用do也没这么麻烦的啊，像这样：

Just 1 >>= \x -> Just 2 >>= \y -> return (x + y)

然后才想起来其实这个表达式就是嵌套的 OTL

(Just 1) >>= (\x -> ((Just 2) >>= (\y -> (return (x + y)))))

还是没有括号看起来顺眼些……但是由于优先级不同，Haskell里能省略的这些括号在Ruby里就省略不了。只好乖乖的写吧。

嘛，无论如何，有了Maybe类的定义后，我们就得到了传播Maybe::None的能力。像是把前面的1+2换成1+None，得到的就会是None：

res3 = one.bind { |x|
         Maybe::None.bind { |y|
           Maybe.unit(x + y)
         }
       }
#=> #<Maybe:0x316384 @has_value=false, @value=nil>
res3.none?
#=> true

或者写在一行上？

res3 = one.bind { |x| Maybe::None.bind { |y| Maybe.unit(x + y) } }

用Haskell写的话，不用do记法是

Just 1 >>= \x -> Nothing >>= \y -> return (x + y)

用do记法的话

do x <- Just 1
   y <- Nothing
   return (x + y)

嗯，看过maybe monad，那么list monad呢？
Ruby里的Enumerable模块其实就可以看成一个抽象的表，里面的select、inject、map/collect等方法都有函数式编程的对应物：filter、fold_left、map等。那干脆就把list monad的bind函数写在Enumerable里好了，像这样：

module Enumerable
  def bind
    self.inject([]) { |acc, e| acc + (yield e) }
  end
end

然后，例如说要求[1, 2]的每个元素分别与[3, 4, 5]的每个元素的乘积的列表：

[1, 2].bind { |x|
  [3, 4, 5].bind { |y|
    [x * y]
  }
}
#=> [3, 4, 5, 6, 8, 10]

呜，没想像中的好看 T T
即使不用list monad，直接用each来写看起来也差不多：

res = []
[1, 2].each { |x|
  [3, 4, 5].each { |y|
    res << (x * y)
  }
}
#=> res == [3, 4, 5, 6, 8, 10]

而在有专门的语法支持的语言里，这逻辑写起来就很优雅：

do x <- [1, 2]
   y <- [3, 4, 5]
   return (x * y)
-- [3,4,5,6,8,10]

from x in new [] { 1, 2 }
from y in new [] { 3, 4, 5 }
select x * y
//=> { 3, 4, 5, 6, 8, 10 }

在Haskell里即使不用do记法也不难看：

[1, 2] >>= \x -> [3, 4, 5] >>= \y -> return (x * y)

回到开头C#的那个例子，用上面Ruby里的list monad来写的话，

boolVals.bind { |a1|
  boolVals.bind { |a2|
    boolVals.bind { |a3|
      boolVals.bind { |b1|
        boolVals.bind { |b2|
          boolVals.bind { |b3|
            [(!((a1 && b1) || (a2 && b2) || (a3 && b3))) ==
            (!(a1 && b1) && !(a2 && b2) && !(a3 && b3))]
          }
        }
      }
    }
  }
}.all? { |b| b }
#=> true

感觉微妙……

有没有什么办法能让这monad在Ruby里更好看些？还是说我要求的过多了？
即使像LINQ的SelectMany那样把Bind写成多接受一个参数的版本，调用也还是会嵌套啊（虽然lambda表达式不必嵌套了）。我就是想少写点括号少写些缩进而已……
周末再读读《The Ruby Programming Language》来找找灵感好了。

对了，记个链接：MenTaLguY: Monads in Ruby
还没来得及读……

评论

7 楼 RednaxelaFX 2009-03-31  

ychael 写道

传入一个闭包嫌太少

很好奇你所提到的yield1、yield2是什么语境下的？因为没见过，所以想多了解一些～

至于在Ruby里传入多于一个闭包，其实不是大问题吧？原本用yield的地方也可以用显式的block参数+.call来调用，要多个闭包的话就多收几个参数好了。像是Ruby里的Y组合子，可以简单实现为：

irb(main):001:0> Y = lambda { |y| lambda { |f| lambda { |x| f[y[y][f]][x] } } }
=> #<Proc:0x02e9a154@(irb):1>
irb(main):002:0> Fix = Y[Y]
=> #<Proc:0x02e9a190@(irb):1>
irb(main):003:0> F = lambda { |fac| lambda { |x| 0 == x ? 1 : x * fac[x-1] } }
=> #<Proc:0x02e915a4@(irb):3>
irb(main):004:0> factorial = Fix[F]
=> #<Proc:0x02e9a1cc@(irb):1>
irb(main):005:0> factorial[4]
=> 24

这段代码里一个&都没用到（当然我们知道lambda这个函数里是有&的……不过不管了），也一个yield都没用到，直接收了参数拿来调用，仅此而已。好吧这段代码里的lambda都是收一个参数的，不过多收几个也没啥差别？

至于说我这帖原本想写的东西，应该跟传入多个闭包没关系，而是跟嵌套定义的闭包有关系……但我傻了，用monad也不会解决闭包的嵌套的，除非弄个monadic syntax来掩盖这实现细节，像Haskell的do记法。

6 楼 ychael 2009-03-30  

传入一个闭包嫌太少

5 楼 RednaxelaFX 2009-03-30  

ychael 写道

不太理解，是不是yield1，yield2这种？

Umm...我没理解，请问yield1、yield2指的是什么？

4 楼 ychael 2009-03-30  

不太理解，是不是yield1，yield2这种？

3 楼 night_stalker 2009-03-13  

幂集一般都可以用二进制数来对应，其他语言里也一样
写在Fixnum里只是为了方便一点而已

2 楼 RednaxelaFX 2009-03-13  

太强了！拜一下～～～
Fixnum可以这样用……太强了 XDD

night_stalker 写道

Ruby是不能省掉块结束符号地！真想弄掉只能自己加工下再eval……

不过我的原意是想尽量不用块结构，或者即便用也尽量不嵌套而是串连在一起。实际把代码写出来才发觉自己错了，原本想的办法的lambda表达式就是嵌套的。如果像LINQ的SelectMany那样多给一个参数或许能不嵌套，回头得试试。

1 楼 night_stalker 2009-03-13  

我（逃避抽象的实用主义者）觉得：怎样写比较短，在于如何穷举a1 a2 a3 b1 b2 b3

class Fixnum
  %w[a1 a2 a3 b1 b2 b3].each_with_index do |name, idx|
    define_method name, do
      self & (1<<idx) == 0 ? false : true
    end
  end
end
0b1000000.times do |n|
  n.instance_eval %q[
    if !((a1&&b1) || (a2&&b2) || (a3&&b3)) != !(a1&&b1) && !(a2&&b2) && !(a3&&b3)
      puts 'blah'
    end
  ]
end

Ruby是不能省掉块结束符号地！真想弄掉只能自己加工下再eval……