So far, we implemented a linked list and a stack as a list. One of the key concepts in functional programming is the concept of lazy evaluation. We can make our list lazy so that the elements will be evaluated once we access them. We need to change node
in such a way that it will return a function containing List as next, instead of the list itself. The function will be evaluated when it is called; therefore, our list will be lazy.
We start with modifying our node
case. In our LinkedList
example, next
was of the LinkedList<Element>
type. To make our list lazy, we will modify next
to be a function that returns our List:
enum LazyList<Element: Equatable> { case end case node(data: Element, next: () -> LazyList<Element>) }
As we can see in the preceding code, our Node
case is not defined as indirect because next
is not of the LazyList
type and is a reference to a function that returns LazyList
.
We need to accommodate this change into our properties and methods. It is going to be as easy as changing any next
to next()
. For example, our size
property becomes the following:
var size: Int { switch self { case .node(_, let next): return 1 + next().size case .end: return 0 } }
If we followed the code and changed it properly, we would see that our map
and filter
do not compile. We need to change the operator as follows:
infix operator <|| { associativity right precedence 100 } func <|| <T>(lhs: T, rhs: () -> LazyList<T>) -> LazyList<T> { return .node(data: lhs, next: rhs) }
Here, we change our rhs
to a function type that matches our LazyList's next
. This change did not fix our map
and filter
problems. It seems that the right-hand side of the infix
operator is evaluated before being passed to it and we do not want this.
This is because we do not pass a closure to our operator in the map
and filter
methods:
func map<T>(_ transform: (Element) -> T) -> LazyList<T> { switch self { case .end: return .end case .node(let data, let next): return transform(data) <|| next().map(transform) } }
In our map
method example, next().map(transform)
is not a closure. If we wrap it in { }
, then it becomes a closure. We can modify our infix
operator as follows:
func <|| <T>(lhs: T, rhs: @autoclosure(escaping) () -> LazyList<T>) -> LazyList<T> { return .node(data: lhs, next: rhs) }
The @autoclosure
attribute creates an automatic closure around the expression. So when we write an expression such as next().map(transform)
, it is automatically wrapped in a closure to become { next().map(transform) }
before it is passed to our infix
operator.
Starting in Swift 1.2, autoclosure
defaults to noescape
. This attribute ensures that parameters are not stored for later execution and will not outlive the lifetime of the call. The noescape
implementation adds minor performance optimizations and bypasses the need to annotate properties and methods with self
.
The escaping
annotation in brackets is necessary in order to signify that the closure will last longer than the lifetime of the scope that it is declared in.
Finally, we need to change our cons
method by wrapping self
in { }
as follows:
func cons(_ element: Element) -> LazyList { return .node(data: element, next: { self }) }
Let's test our LazyList
and see if it works properly:
let ourLazyList = 3 <|| 2 <|| 1 <|| LazyList.end // node(3, (Function)) print(ourLazyList.size) // prints 3
Our lazy list now becomes as follows:
/// Operator infix operator <|| { associativity right precedence 100 } func <|| <T>(lhs: T, rhs: @autoclosure(escaping) () -> LazyList<T>) -> LazyList<T> { return .node(data: lhs, next: rhs) } /// Lazy List enum LazyList<Element: Equatable> { case end case node(data: Element, next: () -> LazyList<Element>) var size: Int { switch self { case .node(_, let next): return 1 + next().size case .end: return 0 } } var elements: [Element] { switch self { case .node(let data, let next): return [data] + next().elements case .end: return [] } } var isEmpty: Bool { switch self { case .node(_ , _): return false case .end: return true } } static func empty() -> LazyList { return .end } func cons(_ element: Element) -> LazyList { return .node(data: element, next: { self }) } func removeLast() -> (element: Element, linkedList: LazyList)? { switch self { case .node(let data, let next): return (data, next()) case .end: return nil } } func map<T>(_ transform: (Element) -> T) -> LazyList<T> { switch self { case .end: return .end case .node(let data, let next): return transform(data) <|| next().map(transform) } } func filter(_ predicate: ((Element) -> Bool)) -> LazyList<Element> { switch self { case .end: return .end case .node(let data, let next): return predicate(data) ? data <|| next().filter(predicate) : next().filter(predicate) } } func reduce<Value>(_ initial: Value, combine: (Value, Element) -> Value) -> Value { switch self { case .end: return initial case .node(let data, let next): return next().reduce(combine(initial, data), combine: combine) } } static func contains(_ key: Element, list: LazyList<Element>) -> Bool { switch list { case .end: return false case .node(let data, let next): if key == data { return true } else { return contains(key, list: next()) } } } }