Feature #20625
openObject#chain_of
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 aremap_chain
,
traverse
, andtrace_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!
Updated by zverok (Victor Shepelev) 3 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?}
?
Updated by mame (Yusuke Endoh) 2 months ago
- Related to Feature #8506: Object#iter_for / Object#to_iter added
- Related to Feature #14423: Enumerator from single object added
Updated by mame (Yusuke Endoh) 2 months ago
- Related to Feature #14781: Enumerator.generate added
Updated by matz (Yukihiro Matsumoto) 2 months ago
I don't agree with Object#chain_of
. Maybe there's a room for a gem, or enhancing Enumerable#product
.
Matz.
Updated by knu (Akinori MUSHA) 2 months ago
- Related to Feature #20664: Add `before` and `until` options to Enumerator.produce added
Updated by matheusrich (Matheus Richard) about 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?)