Crystal: Allow yield in recursive function?

Created on 21 Feb 2017 · 4Comments · Source: crystal-lang/crystal

Hi,

It's en enhancement request I guess: could we allow yield to be used in a recursive function?

For instance, in this code: https://github.com/Fusion/data.cr/blob/master/src/crdata/tree.cr in the each() function I have to build a stack of traversed nodes to enumerate a tree's leaves. As a result, going through my AVL tree-based map cannot be done lazily.

Cheers!

Source

Fusion

Most helpful comment

Hi @Fusion the challenge here is that for non-captured blocks crystal inlines the called method. Hence, the problem for yielding recursively.

A workaround is to use captured blocks though.

class Tree
  property left : Tree?
  property root : Int32
  property right : Tree?

  def initialize(@left, @root, @right)
  end

  def each(&block : Int32 -> )
    l.each(&block) if l = @left
    yield @root
    r.each(&block) if r = @right
  end
end

t = Tree.new(Tree.new(nil,1,nil), 2, Tree.new(nil,3,nil))

t.each do |n|
  puts n # => 1, 2, 3
end

bcardiff on 21 Feb 2017

👍4

All 4 comments

Hi @Fusion the challenge here is that for non-captured blocks crystal inlines the called method. Hence, the problem for yielding recursively.

A workaround is to use captured blocks though.

class Tree
  property left : Tree?
  property root : Int32
  property right : Tree?

  def initialize(@left, @root, @right)
  end

  def each(&block : Int32 -> )
    l.each(&block) if l = @left
    yield @root
    r.each(&block) if r = @right
  end
end

t = Tree.new(Tree.new(nil,1,nil), 2, Tree.new(nil,3,nil))

t.each do |n|
  puts n # => 1, 2, 3
end

bcardiff on 21 Feb 2017

👍4

Ooooh...that's quite straightforward. Thanks!

(Doesn't this mean that I will be keeping data in memory for all recursive closure contexts?)

Fusion on 22 Feb 2017

close?