Julia Language Iterables Lazily-Evaluated Lists
Example
It's possible to make a simple lazily-evaluated list using mutable types and closures. A lazily-evaluated list is a list whose elements are not evaluated when it's constructed, but rather when it is accessed. Benefits of lazily evaluated lists include the possibility of being infinite.
import Base: getindex
type Lazy
thunk
value
Lazy(thunk) = new(thunk)
end
evaluate!(lazy::Lazy) = (lazy.value = lazy.thunk(); lazy.value)
getindex(lazy::Lazy) = isdefined(lazy, :value) ? lazy.value : evaluate!(lazy)
import Base: first, tail, start, next, done, iteratorsize, HasLength, SizeUnknown
abstract List
immutable Cons <: List
head
tail::Lazy
end
immutable Nil <: List end
macro cons(x, y)
quote
Cons($(esc(x)), Lazy(() -> $(esc(y))))
end
end
first(xs::Cons) = xs.head
tail(xs::Cons) = xs.tail[]
start(xs::Cons) = xs
next(::Cons, xs) = first(xs), tail(xs)
done(::List, ::Cons) = false
done(::List, ::Nil) = true
iteratorsize(::Nil) = HasLength()
iteratorsize(::Cons) = SizeUnknown()
Which indeed works as it would in a language like Haskell, where all lists are lazily-evaluated:
julia> xs = @cons(1, ys)
Cons(1,Lazy(false,#3,#undef))
julia> ys = @cons(2, xs)
Cons(2,Lazy(false,#5,#undef))
julia> [take(xs, 5)...]
5-element Array{Int64,1}:
1
2
1
2
1
In practice, it is better to use the Lazy.jl package. However, the implementation of the lazy list above sheds lights into important details about how to construct one's own iterable type.
