Head and Tail

General Usage
1

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?

1 Like
2 
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'
3 Likes
3

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

1 Like
4

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!)

5

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

6

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
7

Iterators.Stateful could kinda be used for this.

8

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