Non-empty & persistent linked lists

NZLists.jl

struct NZList{T}
    head::T
    tail::Union{NZList{T},Nothing}
end

cons(x) = NZList(x, nothing)
cons(x::T, xs::Union{NZList{T},Nothing}) where {T} = NZList(x, xs)

function Base.iterate(xs::NZList)
    xs.head, xs.tail
end

function Base.iterate(xs::NZList, state::Union{Nothing, NZList})
    if isnothing(state)
        nothing
    else
        state.head, state.tail
    end
end

function Base.collect(xs::NZList{T}) where T
    let xs::Union{NZList{T},Nothing} = xs
        out = T[]
        while !isnothing(xs)
            push!(out, xs.head)
            xs = xs.tail
        end
        out
    end
end

function Base.show(io::IO, xs::NZList)
    show(io, collect(xs))
end