Lazy comonadic array zipper

TL;DR: Stacking functions lazily can speed up your code.

Previously i showed the array zipper, which is really great. But: There is one big problem. And if you read the article you should have spotted it right away. I even added a dog-ear for myself in order to remind me that there is something left to be solved.

The dog-ear 🐶

  func map<A>(f: T -> A) -> ArrayZipper<A> {
    switch self {
    case let .zipper(head, focus, tail):
      return .zipper(head.lazy.map(f), f(focus), tail.lazy.map(f))
    }
  }

Yeah. There is the original code. calling head.lazy.map(f) which is kinda romantic. There is nothing lazy in this code. It is all evaluated immediately. So as soon as you create the .zipper enum case … your beautiful lazy type gets converted into a stupid old array. Thats the way it is.

If you want to have full laziness in your type better prepare yourself.

Ah, that type of type ⛓

Whats the key? Having a lazy collection type as a starting point:

struct ArrayZipper<S: LazyCollectionType> {
  // the elements
  let elements: S
  // i was too lazy to add a property for each position and count
  // so there is only a nameless tuple.
  let pointed: (Int, Int)
  
  /// Move the zipper to next position
  func moveTo(position: Int) -> ArrayZipper<S>? {
    guard position >= 0 && position < pointed.1 else { return nil }
    return ArrayZipper(elements: elements, pointed: (position, pointed.1))
  }
}

Based on this the whole thing has to keep track of the lazy type. like in

  func map<U>(f: S.Elements.Generator.Element -> U) -> ArrayZipper<LazyMapCollection<S.Elements, U>> {
    return ArrayZipper<LazyMapCollection<S.Elements, U>>(elements: elements.map(f), pointed: pointed)
  }

So here if we have a ArrayZipper<LazyCollection<Int>>> we will receive a ArrayZipper<LazyMapCollection<Int, Int>>.

Wanna really read that? Be Lazy! 👻

The hard part is really extract:

extension ArrayZipper where
  S.SubSequence: SequenceType,
  S.SubSequence.Generator.Element == S.Generator.Element,
  S.SubSequence.SubSequence == S.SubSequence {
  
  /// get the focus of the current structure
  func extract() -> S.Generator.Element {
    let g = elements.dropFirst(pointed.0).dropLast(Int(pointed.1.toIntMax() - pointed.0 - 1))
    // next call evaluates finally  
    return Array(g)[0]
  }
  
}

I found a great hint which made it clear to me. The lazy SubSequence stuff is kinda weird. We need to ensure it`s the same type.

So while calling extend you will se, that if you don`t want to evaluate, you have to provide the type information. Thats why at the end of the example we get a:

ArrayZipper<LazyMapCollection<LazyMapCollection<Range<Int>, ArrayZipper<LazyMapCollection<LazyMapCollection<Range<Int>, ArrayZipper<LazyMapCollection<LazyMapCollection<Range<Int>, ArrayZipper<LazyMapCollection<[Int], Int>>>, Int>>>, Int>>>, Int>>

But - when you call

zipper.map(map).extend(avg(radius: 3)).extend(avg(radius: 2)).moveTo(3)

it gets crazy - you will find out when you check the printin the avg call.

Let me see it 🙈

This is the current version. Maybe i am going to add further improvements. Still some TODOs left.

👻 Feel free to hit me on twitter. @elmkretzer