# Custom iterators over custom types

**URL:** <https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160>\
**Category:** General Usage\
**Created:** [December 27, 2016, 1:22pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160 "2016-12-27T13:22:05Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 27, 2016, 1:22pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/1 "2016-12-27T13:22:05Z")

</div>

I am exploring the type system of Julia seriously for the first time and I got stuck with a practical problem I have in one of my packages. Suppose I have various grid types following an interface:

```julia
@doc doc"""
  A data point in an `N`-dimensional space represented by
  `N` scalars (a.k.a. coordinates) of type `T`, holding a
  value of type `V`.
""" ->
abstract AbstractDataPoint{N,T,V}

@doc doc"""
  An iterable collection of points of type `P`.
""" ->
abstract AbstractPointCollection{P}

@doc doc"""
  A grid of points of type `P`.
""" ->
abstract AbstractGrid{P}

@doc doc"""
  Valid representations of a spatial domain.
""" ->
AbstractDomain = Union{AbstractPointCollection,AbstractGrid}

@doc doc"""
  A path in a spatial domain of type `D`.
""" ->
abstract AbstractPath{D}

```

In this interface, I have various representations of a spatial domain `AbstractDomain`, either grids types or point collections. I would like to traverse such domains with different types of paths. For achieving this goal I tried to introduce the `AbstractPath` type.

Now consider one possible implementation of the interface:

```julia
immutable DataPoint{N} <: AbstractDataPoint{N,Real,Real}
  coords::NTuple{N,Real}
  value::Real
end
coords(p::DataPoint) = p.coords
value(p::DataPoint) = p.value

type PointCollection{N} <: AbstractPointCollection{DataPoint{N}}
  points::AbstractVector{DataPoint{N}}
end
npoints(pc::PointCollection) = length(pc.points)

type ImageGrid{N} <: AbstractGrid{DataPoint{N}}
  data::AbstractArray{Real,N}
  dx::Real
  dy::Real
  dz::Real

  ImageGrid(data) = ImageGrid(data,1.,1.,1.)
end
npoints(g::ImageGrid) = prod(size(g.data))

```

Finally, the question. Suppose there is a natural order for traversing spatial domains. For example, an image grid is naturally traversed in column-major order, a point collection is traversed in forward order, etc. I would like to define a `DefaultPath` for all `AbstractDomain`:

```julia
type DefaultPath{AbstractDomain} <: AbstractPath{AbstractDomain}
  # TODO
end

```

How would you approach this problem? Should I define a `start`, `next` and `done` for all new types, make them part of the interface specification and then call these methods inside of the `DefaultPath`? How to do that in a Julian way?

Besides the question, please feel free to give feedback on the interface, if there is anything that can be done better in terms of performance, etc.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [December 27, 2016, 3:38pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/2 "2016-12-27T15:38:28Z")

</div>

There’s one issue here for performance, you are using abstract types (i.e. Real) in your concrete types, which is a “real” performance killer. Also, does ImageGrid need to be a `type` instead of an `immutable`? (do you need to modify the dx/dy/dz values, or replace the data value (which is another case of having an abstract type in a concrete type).

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 27, 2016, 3:46pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/3 "2016-12-27T15:46:58Z")

</div>

Thank you @ScottPJones I was thinking about this `Real` issue too, I will probably replace it by `Float64` in the concrete types. Regarding the `type` versus `immutable` issue, I don’t plan to change the array to which the type points to, but the content of the array instead (`data[i,j,k] = foo`), can I use `immutable` safely in this case?

---

<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:** [December 27, 2016, 4:13pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/4 "2016-12-27T16:13:05Z")

</div>

Normally you would do parameterize the type, so that it can be both generic and concrete:

```julia
immutable DataPoint{N,T<:Real,S<:Real} <: AbstractDataPoint{N,T,S}
  coords::NTuple{N,T}
  value::S
end

```

If you have an array of `DataPoint` and only need `data[...] = foo`, then it being `immutable` is not a problem.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [December 27, 2016, 4:18pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/5 "2016-12-27T16:18:39Z")

</div>

Yes, Steven is correct, parameterization of types is your friend in Julia, will let you avoid the performance problems of run-time dispatching, and allow the structures themselves to be much more efficient as far as memory and avoiding double indirection to get to the values.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 27, 2016, 5:52pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/6 "2016-12-27T17:52:04Z")

</div>

Thank you @stevengj , in that case the type is concrete? Could you please elaborate? I am still trying to grasp the syntax for parametric types in Julia, could you please explain the meaning of the expressions below?

```julia
abstract Base{T}

# expression 1
type Foo{T} <: Base{T} end

# expression 2
type Foo{T<:Real} <: Base{T} end

# expression 3
type Foo <: Base{Real} end

```

What are the implications of using each?

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [December 27, 2016, 6:28pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/7 "2016-12-27T18:28:06Z")

</div>

1. T is able to take any type it got constructed from.
2. T restrict to subtypes of Real
3. `Base{Real}` will alway be `Base{Real}` independent of what Foo is doing.  
More about parametric types:  
[http://docs.julialang.org/en/release-0.5/manual/types/#man-parametric-types](http://docs.julialang.org/en/release-0.5/manual/types/#man-parametric-types)

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 27, 2016, 6:33pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/8 "2016-12-27T18:33:36Z")

</div>

Thank you @sdanisch, that is very clear.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 27, 2016, 6:52pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/9 "2016-12-27T18:52:12Z")

</div>

@stevengj how can the type be concrete? Also, in my case I want to have `DataPoint` depending only on the dimension `N`. I want to fix `T` and `V` to be `Float64` for example.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 28, 2016, 9:51am UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/10 "2016-12-28T09:51:53Z")

</div>

Does anyone have a suggestion for the implementation of `DefaultPath`? What I have in mind is something like:

```julia
immutable DefaultPath{D<:AbstractDomain} <: AbstractPath{D} # is this the best way to write it?
  domain::D # pointer to domain object?
end
function start{D<:AbstractDomain}(p::DefaultPath{D}) # do we need this boilerplate?
  if isa(p.domain, PointCollection) # any cleaner way of doing this?
    return start(p.domain.points)
  elseif isa(p.domain, ImageGrid)
    return start(p.domain.data)
  else
    error("not implemented")
  end
end

```

As you can see, this code isn’t very elegant and I actually don’t know if it works, just brainstorming and learning the syntax.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 28, 2016, 11:48am UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/11 "2016-12-28T11:48:46Z")

</div>

You can do

```nohighlight
start{D <: PointCollection}(p::DefaultPath{D}) = start(p.domain.points)
start{D <: ImageGrid}(p::DefaultPath{D}) = start(p.domain.data)
start(p::DefaultPath) = error("not implemented")

```

instead of type checking inside a function. I would argue this is typically more “Julian” way of programming.

---

<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:** [December 28, 2016, 4:21pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/12 "2016-12-28T16:21:09Z")

</div>

> [@juliohm](#):
>
> @stevengj how can the type be concrete?

If you declare e.g. `immutable Foo{T<:Real}; x::T; end`, then it effectively defines an abstract type `Foo` and a family of concrete types `Foo{T}` for different types `T`. (`Foo{Int}`, `Foo{Float64}`, etcetera).

If, in turn, you use a concrete type `T`, e.g. `Foo{Int}`, then the resulting `Foo{Int}` type can have all of the benefits of a type where you just declared the fields explicitly to be `Int` (i.e. it is a “pointer-free” type and `x` is stored “inline” in the structure rather than as a pointer to some “boxed” heap object, and `Array{Foo{Int}}` is as efficient as `Array{Int}`). That’s why parameterized types allow you to write type-generic data-structures that still have the efficiency of fully concrete types.

---

<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:** [December 28, 2016, 4:22pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/13 "2016-12-28T16:22:04Z")

</div>

> [@kristoffer.carlsson](#):
>
> start(p::DefaultPath) = error(“not implemented”)

Also, you would normally not bother with this method; just omit it, and it will throw a `MethodError` if you try to call it.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 28, 2016, 6:40pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/14 "2016-12-28T18:40:16Z")

</div>

Thank you @kristoffer.carlsson, what do you think of doing:

```julia
start(p::DefaultPath{PointCollection}) = start(p.domain.points)
start(p::DefaultPath{ImageGrid}) = start(p.domain.data)
start(p::DefaultPath) = error("not implemented")

```

Is there an advantage in restricting `D <: PointCollection` or `D <: ImageGrid`?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 28, 2016, 6:55pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/15 "2016-12-28T18:55:47Z")

</div>

It depends if `ImageGrid` and `PointCollection` are abstract types or not. If they are concrete type, then doing your way works just well. If it is `abstract` (or parameterized) then this will happen:

```nohighlight
julia> immutable A{T}
       x::T
       end

julia> f(x::Vector{A}) = print("a")
f (generic function with 1 method)

julia> f([A(1), A(2)])
ERROR: MethodError: no method matching f(::Array{A{Int64},1})
Closest candidates are:
  f(::Array{A,1}) at REPL[19]:1

julia> f{T <: A}(x::Vector{T}) = print("b")
f (generic function with 2 methods)

julia> f([A(1), A(2)])
b

```

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 28, 2016, 10:58pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/16 "2016-12-28T22:58:41Z")

</div>

@kristoffer.carlsson that is tricky, why the first attempt fails? Shouldn’t it work just fine?

---

<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:** [December 28, 2016, 11:05pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/17 "2016-12-28T23:05:40Z")

</div>

> [@juliohm](#):
>
> @kristoffer.carlsson that is tricky, why the first attempt fails? Shouldn’t it work just fine?

See the section about “invariant types” in the [Julia manual](http://docs.julialang.org/en/stable/manual/types/#man-parametric-types). This is very important to understand when working with parametric types.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [December 28, 2016, 11:43pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/18 "2016-12-28T23:43:40Z")

</div>

@stevengj I understand the “invariant types” property of Julia, but I don’t understand how defining a method for the abstract type `A` is not enough for catching the case with `A{Int64}`. I understood that `A{T} <: A` always.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [December 28, 2016, 11:49pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/19 "2016-12-28T23:49:09Z")

</div>

Yes but `Vector{A}` is not `<: Vector{A{Int64}}`

---

<div class="post-metadata">

**Author:** ![Evizero](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/evizero/32/10118_2.png) [@Evizero](https://discourse.julialang.org/u/Evizero)\
**Post date:** [December 28, 2016, 11:54pm UTC](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160/20 "2016-12-28T23:54:17Z")

</div>

> [@kristoffer.carlsson](#):
>
> Vector{A} is not \<: Vector{A{Int64}}

you mean the other way around for this particular situation (?)

[Next page](https://discourse.julialang.org/t/custom-iterators-over-custom-types/1160.md?page=2)