Feature #20625: Object#chain_of

• Status: Open
• Assignee: -
• Target version: -

[matheusrich (Matheus Richard)]

Motivation

It's often common to traverse a tree/list-like structure in order to get a chain
of elements. This proposal is to add a method to Object that allows collecting
a chain of elements by applying a block to each element. It doesn't require the
root element to be an instance of a specific class or respond to a specific
protocol.

I think this method could be useful in many cases, since hierarchies like this
are common in codebases (e.g. file systems, organizations structures, commit
histories, breadcrumbs in web apps, configuration hierarchies, etc.).

Here are some examples extracted from real codebases (simplified for the sake of
the example/privacy):

# Given a file system structure, get the breadcrumbs of a file or directory
def breadcrumbs(root)
  crumbs = []
  current = root
  
  while current
    crumbs << current
    current = current.parent_dir
  end

  crumbs
end

# Given an employee, get the hierarchy of managers
def hierarchy(employee)
  hierarchy = []
  current = employee

  while current
    hierarchy << current
    current = current.manager
  end

  hierarchy
end

Implementation

The implementation in Ruby could look like this:

class Object
  def chain_of(&block)
    chain = []
    current = self

    while current
      chain << current
      current = block.call(current)
    end

    chain
  end
end

Here's an example use:

class ListNode
  attr_accessor :value, :parent

  def initialize(value, parent = nil)
    @value = value
    @parent = parent
  end

  def ancestors
    chain_of(&:parent).shift
  end
end

root = ListNode.new("root")
child1 = ListNode.new("child1", root)
child2 = ListNode.new("child2", child1)

puts child2.ancestors.map(&:value)
# => ["child1", "root"]

The examples from the motivation section could be rewritten as:

breadcrumbs = root.chain_of(&:parent_directory)
hierarchy = employee.chain_of(&:manager)

Considerations

• While I'm including the object by default in the chain, it could be more
  intuitive to exclude it. In any case, it's easy to remove or add it with
  shift/unshift.

• On a different note, the method could be named differently (I do like
  chain_of, though). Some alternatives I've considered are map_chain,
  traverse, and trace_path.

• The method assumes that the traversal will finish at some point. If the user
  has a cyclic structure, it will loop indefinitely. We could stop looping if we
  find the same element twice. I don't think it's worth the extra complexity.

• I'm not sure Object is the best place for this method. While it's very
  general, I think it gives power to the user to decide how to traverse a chain
  like this without having to rely on a specific class. Maybe a mixin
  (Traversable/Chainable) would be more appropriate? Could this fit in
  Enumerable, somehow?

Of course, I'm open to suggestions and feedback. Thanks for reading!

[zverok (Victor Shepelev)]

breadcrumbs = Enumerator.produce(parent, &:parent_directory).take_while { !_1.nil? }
hierarchy = Enumerator.produce(employee, &:member).take_while { !_1.nil? }

My initial proposal for what became Enumerator.produce (it is the opposite of Enumerable#reduce, hence the name) was to make it an Object’s method.

But it was decided that increasing Object’s API is too breaking change, so it became a separate Enumerator method... Which, to the best of my estimation, not a lot of people are aware about (because even when somebody looks for “method like this”, it is not obvious where to look for it).

[matheusrich (Matheus Richard)]

@zverok (Victor Shepelev) do you think Enumerator#chain_of? would be useful as an specialization of produce().take_while {!_1.nil?}?

[mame (Yusuke Endoh)]

• Related to Feature #8506: Object#iter_for / Object#to_iter added
• Related to Feature #14423: Enumerator from single object added

[mame (Yusuke Endoh)]

• Related to Feature #14781: Enumerator.generate added

[matz (Yukihiro Matsumoto)]

I don't agree with Object#chain_of. Maybe there's a room for a gem, or enhancing Enumerable#product.

Matz.

[knu (Akinori MUSHA)]

• Related to Feature #20664: Add `before` and `until` options to Enumerator.produce added