Head and Tail

Is there a function in Julia that returns two items: the first (head) element of an iterator/collection and the remainder (tail?) of that same iterator/collection?

help?> Base.Iterators.peel
  peel(iter)

  Returns the first element and an iterator over the remaining elements.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> (a, rest) = Iterators.peel("abc");

  julia> a
  'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)

  julia> collect(rest)
  2-element Array{Char,1}:
   'b'
   'c'
2 Likes

I wish it would pass through nothing instead though for empty collections, instead of throwing a BoundsError.

1 Like

I suspect this implementation will be inefficient for lisp-style tail recursion on anything but very small collections, as it seems to wrap the tail in an additional layer on each iteration.

julia> (a, rest) = Iterators.peel("abc")
('a', Base.Iterators.Rest{String,Int64}("abc", 2))

julia> (a, rest) = Iterators.peel(rest)
('b', Base.Iterators.Rest{Base.Iterators.Rest{String,Int64},Int64}(Base.Iterators.Rest{String,Int64}("abc", 2), 3))

julia> (a, rest) = Iterators.peel(rest)
('c', Base.Iterators.Rest{Base.Iterators.Rest{Base.Iterators.Rest{String,Int64},Int64},Int64}(Base.Iterators.Rest{Base.Iterators.Rest{String,Int64},Int64}(Base.Iterators.Rest{String,Int64}("abc", 2), 3), 4))

Wouldn’t it have been much more efficient to make the tail a view or similar?

Or does Julia have an optimization for repeated application of the same wrapper? (That would be both cool and useful!)

peel predates the new iterator interface, that is maybe the main reason.

Yeah, maybe there should be a method

Iterators.rest(itr::Iterators.Rest, state) = Iterators.Rest(itr.itr, state)

so that you get

julia> x = 1 : 3
1:3

julia> x1, r1 = Iterators.peel(x)
(1, Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 1))

julia> x2, r2 = Iterators.peel(r1)
(2, Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 2))

julia> x3, r3 = Iterators.peel(r2)
(3, Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 3))

instead of

julia> x = 1 : 3
1:3

julia> x1, r1 = Iterators.peel(x)
(1, Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 1))

julia> x2, r2 = Iterators.peel(r1)
(2, Base.Iterators.Rest{Base.Iterators.Rest{UnitRange{Int64},Int64},Int64}(Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 1), 2))

julia> x3, r3 = Iterators.peel(r2)
(3, Base.Iterators.Rest{Base.Iterators.Rest{Base.Iterators.Rest{UnitRange{Int64},Int64},Int64},Int64}(Base.Iterators.Rest{Base.Iterators.Rest{UnitRange{Int64},Int64},Int64}(Base.Iterators.Rest{UnitRange{Int64},Int64}(1:3, 1), 2), 3))

I agree.

3 Likes

Iterators.Stateful could kinda be used for this.

With the new range of zero-costs abstractions would be theoretically an iterator interface possible where state is just a regular iterator?

for i in 1:10  
     println(i)
end

lowers to

_iterate(u::UnitRange) = u.start <= u.stop ? (u.start, u.start+1:u.stop) : nothing 

r = 1:10
while true
    ϕ = _iterate(r)
    ϕ === nothing && break
    el, r = ϕ
    println(el)
end

Seems so:

struct LightRange # Range has a construction cost
    start::Int
    stop::Int
end
_iterate(u::LightRange) = u.start <= u.stop ? (u.start, LightRange(u.start+1,u.stop)) : nothing 


using BenchmarkTools
function f1(n) 
    k = 0
    for i in 1:n
        k += i
    end
    k
end

function f2(n) 
    k = 0
    r = LightRange(1,n)
    while true
        ϕ = _iterate(r)
        ϕ === nothing && break
        el, r = ϕ
        k += el
    end
    k
end

julia> @btime f1(10000)

  2.131 ns (0 allocations: 0 bytes)
50005000

julia> @btime f2(10000)
  2.131 ns (0 allocations: 0 bytes)
50005000