From: Robert Klemme <shortcutter@...>
Date: 2008-11-02T19:38:48+09:00
Subject: Re: Iterator objects and lazy evaluation

On 02.11.2008 00:22, Yuh-Ruey Chen wrote:
> On Nov 1, 6:36 am, Robert Klemme <shortcut...@googlemail.com> wrote:

> Per my previous reply, I'm trying to find a way to chain iterators
> without nesting blocks (so they can be passed freely into other
> functions expecting enumerables) and without intermediate arrays.

I see you have been referred to Enumertor and to_enum already.

> Hmm, what I'm looking for is not just a simple memoization technique.
> Suppose I have a function that computes the union of two arrays
> whenever each array is changed. Using a perhaps more possible syntax:
> 
> attr_accessor :array_a
> 
> def foo
>    lazy_union = lazy_expr { lazy_depends(:array_a) +
> lazy_depends(:array_b) }
>    @array_a = [1,2]
>    @array_b = [3,4]
>    p lazy_union # [1,2,3,4]
>    @array_a[1] = 5
>    p lazy_union # [1,5,3,4]
> end
> 
> This is a case your memoization technique doesn't address. Yet I'm
> pretty sure this is a common use case, so I was thinking that there
> should be some library out there that provides this functionality.

Well, for this I'd rather create a custom class.  In your case of Array 
you could do something like this

# ALT: require 'md5'

class MemoFunc
   def initialize(*args, &b)
     @args = args
     @hsh  = nil
     @fun  = b
     @result = self
   end

   def call
     h = arg_hash
     if @result == self || h != @hsh
       @result = @fun[*@args]
       @hsh    = h
     end
     @result
   end

   def invalidate
     @result = self
   end

   def rearg(*a)
     @args = a
     self
   end

private
   def arg_hash
     @args.hash
     # ALT: MD5.digest(Marshal.dump(@args))
   end
end

irb(main):024:0> a = [1,2]
=> [1, 2]
irb(main):025:0> b = [3,4]
=> [3, 4]
irb(main):026:0> f = MemoFunc.new(a,b) {|x,y| puts "eval"; x | y}
=> #<MemoFunc:0x7ffa63cc @hsh=nil, @args=[[1, 2], [3, 4]], 
@result=#<MemoFunc:0x7ffa63cc ...>, @fun=#<Proc:0x7ffa646c@(irb):26>>
irb(main):027:0> f.call
eval
=> [1, 2, 3, 4]
irb(main):028:0> f.call
=> [1, 2, 3, 4]
irb(main):029:0> a[1] = 5
=> 5
irb(main):030:0> f.call
eval
=> [1, 5, 3, 4]
irb(main):031:0> f.call
=> [1, 5, 3, 4]
irb(main):032:0> f.call
=> [1, 5, 3, 4]
irb(main):033:0>


The difficult part is to get detection of changes of the arguments right 
(meaning safe and fast).  There is no general solution that fits well to 
all situations.  My implementation with Array#hash is too weak for a 
general solution.  I am thinking that creating an MD5 of the marshalled 
stream of the argument Array is more robust, but you may pay a 
performance penalty.  Which might be ok depending on the complexity of 
the operation.

Kind regards

	robert