# Getting the last element of an iterator

**URL:** <https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696>\
**Category:** General Usage\
**Tags:** question\
**Created:** [November 6, 2020, 6:02pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696 "2020-11-06T18:02:17Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [November 6, 2020, 6:02pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/1 "2020-11-06T18:02:17Z")

</div>

Question 1: Is there a nice one-liner to get the last element of an iterator, without collecting in a temporary array? The obvious doesn’t work:

```julia
julia> eachline(`dir`) |> last
ERROR: MethodError: no method matching lastindex(::Base.EachLine{Base.PipeEndpoint})

```

Which leads to…

Question 2: Why is `last` not defined on iterators? The `last` documentation says:

> Get the last element of an ordered collection, if it can be computed in O(1) time.

Why this limitation?

BTW I suspect the person who wrote the documentation for `Base.Iterators.only` also expected this to work because it refers to `last`…

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 6, 2020, 6:04pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/2 "2020-11-06T18:04:17Z")

</div>

The last element of an iterator is clearly not `O(1)`. also note an iterator may not be finite (also probably because that iterator interface is not defined by some type, unlike `Range` which is also lazily represented but can be `last`ed easily).

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [November 6, 2020, 6:10pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/3 "2020-11-06T18:10:25Z")

</div>

But why implement `last` only when it’s O(1)?

As for finite/infinite… by this logic `collect` should not be supported either?

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [November 6, 2020, 6:19pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/4 "2020-11-06T18:19:18Z")

</div>

I think it is more that collect is clearly `O(n)`, there is no surprise there, as there is no other way it could be. Someone using last may unconsciously expect it to be `O(1)`. More than that, if `last` has this complexity guarantee, then anyone may write a generic algorithm using it and give the expected complexity for their algorithm.

---

<div class="post-metadata">

**Author:** ![tomerarnon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomerarnon/32/3170_2.png) [@tomerarnon](https://discourse.julialang.org/u/tomerarnon)\
**Post date:** [November 6, 2020, 6:36pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/5 "2020-11-06T18:36:18Z")

</div>

Presumably though you could define an `Iterators.last` that does something trivial like:

```julia
function Iterators.last(itr)
    # should throw in a check for Base.IsInfinite() 
    # before doing this. Also potentially defer to 
    # `Base.last` when a method of `lastindex` exists
    x = nothing # or first(itr), if that makes more sense
    for y in itr
        x = y
    end
    return x
end
```

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [November 6, 2020, 6:50pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/6 "2020-11-06T18:50:28Z")

</div>

@Henrique_Becker this doesn’t seem like a very good deal…

We could have:

- An algorithm that works both with arrays and iterators, O(1) in the first case, O(n) in the other case, which can be documented.
- A generally useful `last` (including situations like mine).
- People that really want this selective behavior can use `lastindex` with minimal differences in the code.

Instead we have;

- An algorithm that doesn’t work at all in the second case.
- Many situations where `last` would be natural but doesn’t work.
- People that want `last` for iterators need to replace a function call with a for loop and temporary variable, a much more intrusive change.

(Note that in many cases the algorithm would not work with iterators anyway, since `last` would consume the elements.)

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [November 6, 2020, 7:04pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/7 "2020-11-06T19:04:07Z")

</div>

I disagree. I prefer code clearly broken than surprises. I have nothing against a “generic `last`”, but I would prefer it to be separated. You can wrap your solution in a differently-named function, or even extend `Base.last` though it is not recommended.

---

<div class="post-metadata">

**Author:** ![apo383](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/apo383/32/11272_2.png) [@apo383](https://discourse.julialang.org/u/apo383)\
**Post date:** [November 6, 2020, 7:15pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/8 "2020-11-06T19:15:10Z")

</div>

Part of it is that the minimal interface only needs `iterate`, and doesn’t necessarily know anything about size. It’s optional to implement `IteratorSize(IterType)` and `length()`, let alone `last`. You could easily implement your own fallback `last` that works when an iterator `HasLength()` and errors otherwise. But right now you already get the error anyway.

It seems reasonable to leave it up to the implementer what optional methods to include with their iterator. Even if their iterator has an end, it could cause problems when a user expects `last(iter)` or `iter[end]` to give an answer quickly.

---

<div class="post-metadata">

**Author:** ![malacroi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/malacroi/32/19745_2.png) [@malacroi](https://discourse.julialang.org/u/malacroi)\
**Post date:** [November 7, 2020, 12:22am UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/9 "2020-11-07T00:22:03Z")

</div>

`collect` isn’t ‘supported’ for infinite iterators. If you work according to the interface, you should be calling `Iterators.IteratorSize()` before `collect`, an infinite iterator will return `IsInfinite()` and you should abort. Or instead collect the composition of your iterator with `take`, to guarantee termination.

For `SizeUnknown()` iterators, the generation phase is no less efficient than in the known size case, except the output array cannot be preallocated, and must be grown by pushing.

---

<div class="post-metadata">

**Author:** ![malacroi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/malacroi/32/19745_2.png) [@malacroi](https://discourse.julialang.org/u/malacroi)\
**Post date:** [November 7, 2020, 12:36am UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/10 "2020-11-07T00:36:33Z")

</div>

> [@apo383](#):
>
> You could easily implement your own fallback `last` that works when an iterator `HasLength()` and errors otherwise.

Checking for `HasLength()` is too weak, sinch `HasShape()` also guarantees finite size, and `SizeUnknown()` actually suggests finite size by virtue of not being `IsInfinite()`. It seems like the interface is lacking a way to distinguish between `SizeUnknown()` but definitely finite, when `collect` is safe, and `SizeUnknown()` but possibly infinite.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [November 8, 2020, 1:02pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/11 "2020-11-08T13:02:50Z")

</div>

> [@sijo](#):
>
> An algorithm that works both with arrays and iterators

should just use `Base.iterate` and it will be fine for arrays.

Except if it needs the _last_ value without performing an iteration, then it shouldn’t because `Base.iterate` is not a random access interface, while `last` implicitly requires that.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [November 9, 2020, 4:52pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/12 "2020-11-09T16:52:46Z")

</div>

Thanks for all the answers! I’ve thought about it for a while and I have to say it still looks quite wrong to me. Please consider the following points:

Generic function names such as `last` should be generally useful. It’s weird and inconsistent to reserve a name for some data structures because of performance characteristics. If we want a constraint like this, it should be a different function with a hint in the name.

Do algorithm writers really want to prevent uses that don’t meet some performance guarantee? I doubt it. Much better to document the assumptions for the complexity guarantee!

Now on the specifics. The main idea seems to be:

> No generic fallback for `last`. This way people can use `last` with a guarantee of O(1).

But that’s **misleading** : there is no such guarantee. For example `SLinkedList` (from LinkedLists.jl) has an O(n) implementation of `last`. Do we really want to say package authors should not include such methods, even when it’s very useful? Conclusion: it makes things more surprising, not less.

And there is the added surprise that reasonable code such as `eachline(cmd) |> last` will fail. It gives the API a bad feeling, like there are random holes that can catch you when writing generic code.

Regarding `Iterators`: Algorithmic complexity seems like a bad reason to put a method there. For example we need `Iterators.filter` and `Iterators.map` (Julia 1.6) because they have different _semantics_ than the `Base` version (returning iterators rather than arrays).

I think a real effect of the current behavior is that many people will do the equivalent of `collect |> last`, which has terrible performance. It’s unfortunate that the API nudges people to do that.

---

<div class="post-metadata">

**Author:** ![sijo](https://avatars.discourse-cdn.com/v4/letter/s/da6949/32.png) [@sijo](https://discourse.julialang.org/u/sijo)\
**Post date:** [November 9, 2020, 4:54pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/13 "2020-11-09T16:54:03Z")

</div>

> [@Tamas\_Papp](#):
>
> not a random access interface, while `last` implicitly requires that.

I’m arguing that this should be changed (for the reasons given in my previous comment).

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 9, 2020, 5:14pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/14 "2020-11-09T17:14:43Z")

</div>

> [@Length from iterator?](https://discourse.julialang.org/t/length-from-iterator/27821/20):
>
> Sometimes I found it useful to get the length and the last iterate, e.g. if the iterator does some numerical work until a convergence criteria holds. So a generally useful function is: lastiterate(itr) = foldl((x, y) -\> y, itr) And then julia\> lastiterate('A':'Z') 'Z' and julia\> lastiterate(enumerate('A':'Z')) (26, 'Z')

```julia
lastiterate(itr) = foldl((_, y) -> y, itr)

```

or

```julia
lastiterate(itr) = applicable(last, itr) ? last(itr) : foldl((_, y) -> y, itr)

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 9, 2020, 5:47pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/15 "2020-11-09T17:47:59Z")

</div>

The most general method for iterators that should be O(1) is

```julia
first(Iterators.reverse(iterator))

```

which works for any iterator type that has [implemented reverse iteration](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration).

However, currently `eachline` has no implementation of reverse-order iteration, so this throws a `MethodError`. In principle, it would be straightforward to implement reverse-order `eachline` for _files_, but it doesn’t seem possible to do efficiently for pipes.

(There is an [`Iterators.last(iterator, n)` iterator](https://github.com/JuliaLang/julia/pull/34868) that uses this `reverse` approach.)

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [November 9, 2020, 7:06pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/16 "2020-11-09T19:06:26Z")

</div>

> [@sijo](#):
>
> For example `SLinkedList` (from LinkedLists.jl) has an O(n) implementation of `last` . Do we really want to say package authors should not include such methods, even when it’s very useful?

For future reference, yes, this is what I want, specifically. The author should not be extending a `Base` method if the base documentation is generic and goes against the behavior they want to implement. At very least, if they do this then they should create a documentation for the specific method (over their data structure) with a warning.

> [@sijo](#):
>
> Do algorithm writers really want to prevent uses that don’t meet some performance guarantee?

I want package authors to not ignore performance guarantees set by the `Base`, so I can get a datastructure of some package and pass it to some algorithm that I know the complexity without needing to check if the author has violated any of the performances guaranteed. If it works then it is the right complexity. Simple. If I really do not care about the performance degradation I can carefully extend `Base.last` myself for the third-party data structure.

> [@sijo](#):
>
> But that’s **misleading** : there is no such guarantee. For example `SLinkedList` (from LinkedLists.jl) has an O(n) implementation of `last` .

You are basically saying it is misleading the fact that package authors are not perfect programmers and may make mistakes that compromise API guarantees… there is no way to guarantee many things except by believing package authors will try to be faithful to the API, and disregarding packages that you discover to fail to do so.

I opened [a PR in LinkedLists.jl](https://github.com/ChrisRackauckas/LinkedLists.jl/issues/9) to get this corrected, if possible.

> [@sijo](#):
>
> I think a real effect of the current behavior is that many people will do the equivalent of `collect |> last` , which has terrible performance. It’s unfortunate that the API nudges people to do that.

And when the programmer hits that point, it will be clear to them what is the expected overhead. They may decide to not support iterators, or spend an extra minute to do a loop that avoids the extra allocation, or save that value when it was readily available before, or even rethink their datastructure. It seems to me a problem of bad programmers, not bad API.

---

<div class="post-metadata">

**Author:** ![apo383](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/apo383/32/11272_2.png) [@apo383](https://discourse.julialang.org/u/apo383)\
**Post date:** [November 9, 2020, 7:19pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/17 "2020-11-09T19:19:24Z")

</div>

The algorithmic complexity is more a reason why `last` hasn’t been implemented generically thus far, rather than a justification why it _should never_ be implemented. As others have shown, there are some simple ways to do `last` when you know the iterator is finite. Maybe it’s time to incorporate a solution.

One simple approach would be to implement something for I/O cases alone. Relatively conservative would be `lastline(io::IO...)` perhaps borrowing from `countlines`, which already exists. And actually, would be nice to have something like Unix, e.g. `tail(io::IO, n)`.

Another approach is a generic fallback `last` for finite iterators (more general than I/O). To sort out all the cases would take some thought, as @malacroi points out. But a conservative fallback could be implemented (e.g., only for `HasLength()`) with appropriate warnings and documentation. It may be fine if it’s O(\>1) as long as not infinite.

A pull request might be entertained for either approach.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [November 9, 2020, 7:31pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/18 "2020-11-09T19:31:30Z")

</div>

> [@Henrique\_Becker](#):
>
> If I really do not care about the performance degradation I can carefully extend `Base.last` myself for the third-party data structure.

Are you really recommending type piracy as a general solution for this?

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [November 9, 2020, 7:43pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/19 "2020-11-09T19:43:58Z")

</div>

Yes and no. If you do not really care about breaking the API contract, then I do not see why you would care about a little type piracy (which, I say, is not a greater evil if you know what you are doing). However, as most problems solved by type piracy, you can just take the extra step and wrap the third-party type inside your own type, delegate all methods to the wrapped object, and then you do not have type piracy anymore.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [November 9, 2020, 7:59pm UTC](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696/20 "2020-11-09T19:59:13Z")

</div>

> [@Henrique\_Becker](#):
>
> delegate all methods to the wrapped object

I wish this were a bit easier than it actually is.

[Next page](https://discourse.julialang.org/t/getting-the-last-element-of-an-iterator/49696.md?page=2)