1
\$\begingroup\$

I initialized a tree using a nested hash as input, but when I recursively call Tree.new on the children, it doesn't seem to pass each child as a hash. As a pretty ugly, but working, alternative, I translated everything to arrays.

Is there a way to preserve the hash?

I'm doing this exercise using Ruby 1.9.3, so I can't use Ruby 2.0.0's to_h method.

class Tree
  attr_accessor :node_name, :children

  def initialize(arr)
    arr = arr.to_a unless arr.is_a?(Array)
    arr.flatten!
    @node_name = arr.first
    @children = []
    arr.last.each { |c| @children << Tree.new(c) }
  end

  def visit(&block)
    block.call self
  end

  def visit_all(&block)
    visit &block
    children.each { |c| c.visit_all(&block) }
  end
end

family_tree = Tree.new({'grandpa' => { 'dad' => { 'child 1' => {}, 'child 2' => {} },
                                      'uncle' => {'child 3' => {}, 'child 4' => {} } } })

family_tree.visit_all { |node| p node.node_name }
\$\endgroup\$
1
\$\begingroup\$

Some notes:

  • The initialize method of a class should be its most basic and fundamental constructor, don't use it as a "helper". A tree has a name and some children, so these should be the arguments. You want to construct a Tree from a hash to make things easier for the caller? then create a helper classmethod, for example Tree::new_from_hash(hash).
  • Tree#visit. That's an imperative construct, I'd write first the functional ones (which can also be used imperatively if needed).
  • node.node_name: That repetition is a cue that node_name is redundant, name is enough.
  • (Subjective) I prefer to write hash literals without losing indentation space.

I'd write (I'd inherit from Struct to save some lines, not really needed):

class Tree < Struct.new(:name, :children)
  def self.new_from_hash(hash)
    name, children_hash = hash.first
    children = children_hash.map { |k, v| Tree.new_from_hash({k => v}) }
    Tree.new(name, children)
  end

  def visit_all(&block)
    yield(self)
    children.each { |c| c.visit_all(&block) }
  end
end

family_tree = Tree.new_from_hash({
  'grandpa' => {
    'dad' =>   {'child 1' => {}, 'child 2' => {}},
    'uncle' => {'child 3' => {}, 'child 4' => {}},
  },
})

family_tree.visit_all { |node| puts node.name }

Additional notes:

  • Include module Enumerable and implement Tree#each so you can use all enumerable methods for you trees. Note that enumerable methods assume a single-level iteration, so you'd still need custom methods (like visit_all/map_all) that perform nested operations.
  • If that's a learning code I'd explore this path: create a NestedEnumerable module -very similar to Enumerable- which would provide some xyz_all (or xyz_nested, whatever) methods. Like Enumerable, you would only be required to implement the "each" method (i.e. each_all).
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, this is exactly what I needed. I am doing this as a learning exercise. gist.github.com/yubrew/5175022 I implemented the Enumerable, but not really sure what to do to make NestedEnumerable. I'm not sure how to recognize 'children' inside NestedEnumerable. Is there some tutorial or a hint you can give me? \$\endgroup\$ – John Mar 17 '13 at 4:06
  • \$\begingroup\$ Ruby is not very orthodox on that matter, if you include Enumerable you get methods on each element individually, that may or may not be useful. On custom data containers the idea is that map/select/reject/... equivalents return the same input structure, with the block applied/filtering the value of each node (here you only have name to play with). That's for example how Haskell and Functors work (see fmap for a Tree for example). If you're not familiar with the language is quite a task to understand it though. learnyouahaskell.com/functors-applicative-functors-and-monoids \$\endgroup\$ – tokland Mar 17 '13 at 9:33
  • \$\begingroup\$ At the end it all depends on what operations you want on the trees. visit has the problem that only works through side-effects. That's a pity in a language like Ruby. More on functional programming: code.google.com/p/tokland/wiki/RubyFunctionalProgramming \$\endgroup\$ – tokland Mar 17 '13 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.