TWiki . Doc . LazyVectorExample

LazyVector is an example of a lazy data structure, one whose contents are computed only when they're actually examined. One nice thing you can do with a lazy data structure is to create an infinite data structure, as some of the tests at the bottom of the page do. Since the items are only computed when you ask for them, it doesn't take infinite space to have an infinite data structure. It's just however big you need it to be. Not all uses of LazyVector are of the infinite variety, there's an example of a finite one (look for "intsTo9") in the tests at the bottom of the page as well.

Using a technique known as memoization, the elements of the LazyVector are saved for future use once they've been computed. So you only pay the cost of computation the first time you access a given index.

If you want your LazyVector to end eventually, your generator function should throw ArrayIndexOutOfBoundsException when it's been called too many times.

<Any T> LazyVector<T> makeLV(()->T func) = new LazyVector(elements: cast(new T[10]),
                      length: 0,
                      generator: func);
                     

class LazyVector<T> extends Vector<T> {
  boolean forced = false;
  ()->T generator;
  Vector<T> adds = makeVector(5);

  void raw_add(T element) {
    if(this.elements==null) {
      this.elements = cast(new T[10]);
      this.length = 0;
    }
    
    if (this.length >= this.elements.length)
      this.elements = this.elements.resize(this.length * 2);
    
    this.elements.set(this.length, element);
    this.length = this.length+1;
  }
  
  void force(int index = -1) {
    while(!this.forced && (index < 0 || this.length <= index)) {
      try {
   this.raw_add((this.generator)());
      } catch (ArrayIndexOutOfBoundsException e) {
   this.adds.foreach(T item => this.raw_add(item));
   this.forced = true;
   break;
      }
    }
  }

  boolean isForced() {
    return this.forced;
  }

  size() {
    if (!this.forced)
      this.force();
    return this.length;
  }

  add(item) {
    if (this.forced) {
      this.raw_add(item);
    } else {
      this.adds.add(item);
    }
  }

  get(index) {
    if (!this.forced)
      this.force(index);
    return this.elements[index];
  }

  set(index, value) {
    if (!this.forced)
      this.force(index);
    this.elements[index] = value;
  }

  foreach(func) {
    for(int i = 0; i < this.length || !this.forced; i++) {
      func(this[i]);
    }
  }

  map<C,T,U>(func) {
    int currentIndex = 0;
    LazyVector<U> lvec = makeLV(() => {
      T item = this[currentIndex];
      currentIndex++;
      return func(item);
    });    
    return lvec;
  }


 filter<C,T>(test) {
   int currentIndex = 0;
   LazyVector<T> lvec = makeLV(() => {
     T item = this[currentIndex];
     while (!(test(item))) {
       item = this[++currentIndex];
     }
     currentIndex++;
     return item;
   }
   );
   return lvec;
 } 

}

void indexError() {
  throw new ArrayIndexOutOfBoundsException();
}

//Temporary replacement for assert. :-)
void shouldBe(boolean res, String err = "Error!") {
  if (!res)
    throw new RuntimeException(err);
}
  
main(args) {
  LazyVector<int> ones = makeLV(()=> 1);
  shouldBe(ones[0] == 1);
  shouldBe(ones[250] == 1);
  shouldBe(ones[300] == 1);
//   try {
//     size(ones);
//   } catch (StackOverflowError e) {
//     ones = cast(null); //Let ones be GC'd. Not safe for general use.
//   } catch (OutOfMemoryError e) {
//     ones = cast(null); //Let ones be GC'd. Not safe for general use.
//   }
  int->()->int natsFrom = int start => {
    return () => {return start++;};
  };
  LazyVector<int> natsFromFive = makeLV(natsFrom(5));
  shouldBe(natsFromFive[0] == 5);
  shouldBe(natsFromFive[1] == 6);
  shouldBe(natsFromFive[2] == 7);
  LazyVector<int> evens = makeLV(natsFrom(1)).filter(int num => num % 2 == 0);
  shouldBe(evens[0] == 2, toString(evens[0]));
  shouldBe(evens[1] == 4, toString(evens[1]));
  shouldBe(evens[2] == 6);
  LazyVector<String> toStrings = evens.map(int i => toString(i));
  for(int i = 0; i < 10; i++) {
    println(toStrings[i]);
  }
  shouldBe(equals(toStrings[0],"2"), toStrings[0]);
  shouldBe(equals(toStrings[1],"4"), toStrings[1]);
  shouldBe(equals(toStrings[2],"6"), toStrings[2]);

  int->()->int intsTo9 = int start => {
    return () => {
      if (start > 9)
        indexError();
//    throw new ArrayIndexOutOfBoundsException();
      return start++;
    };
  };
  
  LazyVector<int> finiteSeq = makeLV(intsTo9(0));

  println("Sizing...");
  shouldBe(size(finiteSeq) == 10);
  shouldBe(finiteSeq[0] == 0);
  shouldBe(finiteSeq[9] == 9);
  try {
    finiteSeq[10];
    throw new RuntimeException("Shouldn't get here!");
  } catch (ArrayIndexOutOfBoundsException e) {
    //pass
  }
  println("Tests complete");
    
}

-- BrynKeller - 24 Jul 2002

This is a nice example. I had two concerns:

LazyVector extends Vector, but much of the code seems to be duplicated (e.g. raw_add looks very much like Vector's add). The need to use the unsafe cast, which generated runtime bugs in the begining of writing this class. Here is a slightly modified version: it contains a Vector instead of extending it, so it can delegate the addition work instead of duplicating it. In addition it does not need cast: we only add elements to the vector when they are computed, and then they have the right type.

It is porbably possible to improve it further, but you will do that better than me. In particular I don't really understand what adds is. My class implements Sequence and not list because it does not implement remove (at least). Therefore I add to declare add, not just implement it. Feel free to change that.

Here is the class. The unchanged tests run correctly on it. Note that makeLV should not be needed anymore, it could be replaced with new LazyVector?(...).

<Any T> LazyVector<T> makeLV(()->T func) = new LazyVector(generator: func);
                     

class LazyVector<T> implements Sequence<T> finally implements Collection<T> {
  Vector<T> elements = makeVector(10);
  boolean forced = false;
  ()->T generator;
  Vector<T> adds = makeVector(5);

  void raw_add(T element) {
    this.elements.add(element);
  }
  
  void force(int index = -1) {
    while(!this.forced && (index < 0 || this.elements.size() <= index)) {
      try {
   this.raw_add((this.generator)());
      } catch (ArrayIndexOutOfBoundsException e) {
   this.adds.foreach(T item => this.raw_add(item));
   this.forced = true;
   break;
      }
    }
  }

  boolean isForced() {
    return this.forced;
  }

  size() {
    if (!this.forced)
      this.force();
    return this.elements.size();
  }

  void add(T item) {
    if (this.forced) {
      this.raw_add(item);
    } else {
      this.adds.add(item);
    }
  }

  get(index) {
    if (!this.forced)
      this.force(index);
    return this.elements[index];
  }

  set(index, value) {
    if (!this.forced)
      this.force(index);
    this.elements[index] = value;
  }

  foreach(func) {
    for(int i = 0; i < this.size() || !this.forced; i++) {
      func(this[i]);
    }
  }

  map<C,T,U>(func) {
    int currentIndex = 0;
    LazyVector<U> lvec = makeLV(() => {
      T item = this[currentIndex];
      currentIndex++;
      return func(item);
    });    
    return lvec;
  }


 filter<C,T>(test) {
   int currentIndex = 0;
   LazyVector<T> lvec = makeLV(() => {
     T item = this[currentIndex];
     while (!(test(item))) {
       item = this[++currentIndex];
     }
     currentIndex++;
     return item;
   }
   );
   return lvec;
 } 

}
Feel free to merge the two versions of the class if you like.

-- DanielBonniot - 25 Jul 2002

Daniel wrote:

This is a nice example. I had two concerns: LazyVector extends Vector, but much of the code seems to be duplicated (e.g. raw_add looks very much like Vector's add). The need to use the unsafe cast, which generated runtime bugs in the begining of writing this class.

The only duplicated code is that raw_add method, which should really be eliminated, and a call to super.add() used in place of the call to raw_add. I'll make this change later. The unsafe cast is needed to initialize Vector 's elements member, not for LazyVector. Using super in the constructor to initialize the Vector parts would solve this too - but we don't have constructors, and Vector doesn't define an init method that we can use in this fashion. If we had requirements (say, an existing library which only accepted Vector arguments) which dictated that we must make LazyVector a subclass of Vector , how can we initialize Vector.elements without an unsafe cast? My biggest concern with making it a subclass of Vector is that it can break the contract of size (because it may diverge). This concern applies to making LazyVector implement Collection as well, however. I don't see any good solution for this problem. Also:

It is probably possible to improve it further, but you will do that better than me. In particular I don't really understand what adds is. My class implements Sequence and not list because it does not implement remove (at least). Therefore I add to declare add, not just implement it. Feel free to change that. I should have added a remove method, I'll do that soon also. The adds member is where we keep things that have been added to the LazyVector before it's been completely forced. So, for example:

  LazyVector<int> finiteSeq = makeLV(intsTo9(0));
  finiteSeq.add(35); //Still no elements have been computed
  shouldBe(finiteSeq[0] == 0); //Computed first element
  shouldBe(finiteSeq[9] == 9); //Computed all computable elements 
  shouldBe(finiteSeq[10] == 35); //Appended things from 'adds'.

I'll add this to the tests.

-- BrynKeller - 25 Jul 2002

----- Revision r1.1 - 30 Jan 2003 - 00:16 GMT - TWikiGuest
Copyright © 1999-2003 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback.