Fixing the Many monad, respecting the specs

[Bastes]

Trying to fix this issue: https://github.com/tomstuart/monads/issues/8

The problem was that flat_map didn't actually necessarily return a flat array, just tore down one layer of array returned by the block, leaving a nested array standing.

This version keeps the specs running green, though I haven't yet put a spec to check there's no backsliding.

[Bastes]

Here, I added a test that showcases the problem. You can checking out commit 6e3f0e6f1910c60d98ac20791d9f639fce553f07 and run the spec to see it failing, the next commit is the fix I proposed some times ago.

Hope it helps, have fun ^^

[sclinede]

That's seems like right solution. But I think your tests are not very obvious.

[Bastes]

Agreed, although I don't quite see how I can make the test more obvious ^^° The alternatives I tried were actually less obvious. I'll submit the best I can think of on top of my mind so we can compare.

[Bastes]

Well, here's another approach, with only one root and branch object. WDYT?

[Bastes]

There it is ^^

[sclinede]

cool. :ok_hand: @tomstuart ?

[tomstuart]

I agree that the implementation of Many in this gem is not right, but I don’t think the proposed solution is right either.

The implementation of Many in the original blog post does the right thing, which is to flatten the results once (i.e. concatenate them all) before wrapping them in a new Many:

>> many = Many.new([[:a, [:b, :c]], [:d, [:e, :f]], [:g, [:h, :i]]])
=> …
>> many.slice(0, 1).values
=> [:a, :d, :g]
>> many.slice(0, 2).values 
=> [:a, [:b, :c], :d, [:e, :f], :g, [:h, :i]]
>> many.reverse.values
=> [[:b, :c], :a, [:e, :f], :d, [:h, :i], :g]

Issue #8 correctly identified that this gem, unlike the aforementioned code on which it is based, does the wrong thing:

>> many = Many.new([[:a, [:b, :c]], [:d, [:e, :f]], [:g, [:h, :i]]])
=> …
>> many.slice(0, 1).values
=> [[:a], [:d], [:g]]
>> many.slice(0, 2).values
=> [[:a, [:b, :c]], [:d, [:e, :f]], [:g, [:h, :i]]]
>> many.reverse.values
=> [[[:b, :c], :a], [[:e, :f], :d], [[:h, :i], :g]]

There is not enough flattening here; the result arrays should have been concatenated, but they haven’t been. (I missed this because spec/monads/many_spec.rb doesn’t test the result of method_missing when the method returns an array.)

However, the code in this pull request doesn’t do the right thing either:

>> many = Many.new([[:a, [:b, :c]], [:d, [:e, :f]], [:g, [:h, :i]]])
=> …
>> many.slice(0, 1).values
=> [:a, :d, :g]
>> many.slice(0, 2).values
=> [:a, :b, :c, :d, :e, :f, :g, :h, :i]
>> many.reverse.values
=> [:b, :c, :a, :e, :f, :d, :h, :i, :g]

Now there is too much flattening; the nested arrays have disappeared. This could be easily fixed by replacing .flatten with .flatten(2), but that feels like an incidental hack rather than an elegant and instructive solution.

How do we solve the underlying problem?

[sclinede]

I agree that .flatten(2) is incidential hack. I have some ideas why. Want to test, prove them and then share about success...

[Bastes]

Also agreed on my side... I think I have an idea on how to implement it without the .flatten(2) hack, I'll keep in touch.

[Bastes]

I've tried working around it but I keep on bumping on new problems ; there's something I'm missing, and I think it has something to do with the super-class, perhaps the way every new value is wrapped in an array in from_value.

I'll keep trying after some cooldown period for my neurons ^^°

[tomstuart]

What if we just change the code (on master) to be:

module Monads
  class Many
    # …

    def self.from_value(value)
      Many.new(Array(value))
    end
  end
end

That makes my example above work correctly — is there a downside?

[Bastes]

Ok, I think I've had my epiphany of sorts. I've upped my PR with new code a test. Here's what went wrong if I'm actually right:

# from lib/monads/monad.rb
def within(&block)
  and_then do |value|
    self.class.from_value(block.call(value))
  end
end

# from the new take on lib/monads/many.rb
def self.from_value(value)
  # since and_then can receive either a single value or values in something iterable,
  # we test for :each to avoid re-wrapping the value in a redundant array
  if value.respond_to? :each
    Many.new(value)
  else
    Many.new([value])
  end
end

def and_then(&block)
  block = ensure_monadic_result(&block)

  # now since we *necessarily* get a nested array from values.map(&block).map(&:values),
  # we still need to flatten it, but we need to flatten only one level, the outer wrapping array
  # that is now redundant ^^
  Many.new values.map(&block).map(&:values).flatten(1)
end

[tomstuart]

Okay, great, that’s similar to what I suggested. And your map(&:values).flatten(1) is equivalent to just flat_map(&:values), which is what we started with.

[Bastes]

Glad to be of service ^^

As for the:

module Monads
  class Many
    # …

    def self.from_value(value)
      Many.new(Array(value))
    end
  end
end

I'm not sure how it's supposed to work but it breaks almost everything when I'm trying it (returning to the code as it was or as it is now). Is there something I'm missing there? ^^°

[sclinede]

It's seems like Array(value) is not right solution due to problems with changing input object. Because Array(...) is calling #to_ary method, that could mess up input object.

Array({a: 'b'}) # => [[:a, "b"]]

So solution with #each looks not bad in this case.

[Bastes]

Yep, as far as I can see, Array.new(x) (x being an intege) will create a list of x nils, which is why so many tests were broken when I tried it.

The only thing I see so far against the "each" fix is that you could implement "each" on an object that does not behave like a list of values, but I don't see how that would be a major problem.

WDYT?

[sclinede]

Hmm. I checked it again. With #each we also have problems:

> Monads::Many.from_value({a: 1})
 => #<Monads::Many:0x000000018ffb00 @values={:a=>1}> 
> Monads::Many.from_value({a: 1}).keys
NoMethodError: undefined method `keys' for [:a, 1]:Array

[sclinede]

So lastly, it seems like we should check type. If current value is an Array, then skip wrapping, and wrap otherwise.

[tomstuart]

The underlying problem is that Many is trying to roll two monads into one:

>> words = Many.new(['foo', 'bar'])
=> …
>> words.upcase.values
=> ["FOO", "BAR"] # not flattened, because String#upcase returns a string
>> words.chars.values
=> ["f", "o", "o", "b", "a", "r"] # flattened, because String#chars returns an array (except in Ruby 1.9.3!)

There is no watertight way to have both, and it doesn’t make algebraic sense. I think we should pick one of the two behaviours and stick with it.

[Bastes]

Good points.

Well, at least insuring we don't wrap an Array in another unnecessary Array makes a resonable amount of sense. I'll make a spec with the hash example and improve my PR as soon as I have time.

For the string example, this behaviour is about what I'd expect the "Many" to do so I wasn't surprised, so at least it seems like it wouldn't break the principle of least surprise.