Project

General

Profile

Actions

Feature #20625

open

Object#chain_of

Added by matheusrich (Matheus Richard) 4 months ago. Updated 2 months ago.

Status:
Open
Assignee:
-
Target version:
-
[ruby-core:118535]

Description

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!


Related issues 4 (1 open3 closed)

Related to Ruby master - Feature #8506: Object#iter_for / Object#to_iterRejectedActions
Related to Ruby master - Feature #14423: Enumerator from single objectClosedActions
Related to Ruby master - Feature #14781: Enumerator.generateClosedActions
Related to Ruby master - Feature #20664: Add `before` and `until` options to Enumerator.produceOpenActions

Updated by zverok (Victor Shepelev) 4 months ago

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).

Updated by matheusrich (Matheus Richard) 3 months ago

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

Actions #3

Updated by mame (Yusuke Endoh) 3 months ago

Actions #4

Updated by mame (Yusuke Endoh) 3 months ago

Updated by matz (Yukihiro Matsumoto) 3 months ago

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

Matz.

Actions #6

Updated by knu (Akinori MUSHA) 3 months ago

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

Updated by matheusrich (Matheus Richard) 2 months ago

@matz (Yukihiro Matsumoto) since we don't have a not_nil? method, what do you think about adding a take_until method to Enumerable or Enumerator? That would make things easier to write/read

Enumerator.produce(parent, &:parent_directory).take_until(&:nil?)
Actions

Also available in: Atom PDF

Like0
Like1Like0Like0Like0Like1Like0Like0