Stream: helpdesk (published)

Topic: Iterator exercise


view this post on Zulip rocco sprmnt21 (Oct 23 2021 at 16:46):

I was reading this blog trying to understand how iterators work

I tried to adapt the following script using the iterate function in place of start (), next () and done () . With some difficulty, but in the end I succeeded.

#######
Jeff Bezanson • 8 years ago

Very nice and thorough discussion of julia iterators!

I'm surprised the fibonacci example uses mutation, since it is very naturally functional:

immutable Fibs
end

start(f::Fibs) = (0, 1)
next(f::Fibs, st) = (st[2], (st[2], st[1]+st[2]))
done(f::Fibs, st) = false

Then you can do e.g. take(Fibs(), 10) (using the Iterators package).

#################

struct Fibs
end

Base.iterate(f::Fibs) = (0,(0, 1))
Base.iterate(f::Fibs, st) = (st[2], (st[2], st[1]+st[2]))

using IterTools

collect(takestrict(Fibs(),10))

I tried later to define a non-infinite iterator, as follows:

struct Fibn
    n::Int
end

ϕ=2/(1-sqrt(5))
fb(n)=Int(trunc(((-ϕ)^n -ϕ^(-n))/sqrt(5)))

f(n)=Fibn(n)
length(f::Fibn)=f.n
Base.iterate(f::Fibn) = (0,(0, 1))
Base.iterate(f::Fibn, st) = st[1] <= fb(f.n-1) ? (st[2], (st[2], st[1]+st[2])) : nothing

using IterTools

for i=f(10)
    println(i)
end

I just wanted to do an exercise on iterators, it's not meant to be a solution to some real problem.
I was unable to fix things to get the collect () function to work though.

julia> collect(f(10))
ERROR: MethodError: no method matching length(::Fibn)

How should I do instead of ...?

length(f::Fibn)=f.n

view this post on Zulip Sundar R (Oct 23 2021 at 17:27):

julia> Base.length(f::Fibn)=f.n

julia> collect(f(10))
10-element Vector{Any}:
  0
  1
  1
  2
  3
  5
  8
 13
 21
 34

view this post on Zulip rocco sprmnt21 (Oct 23 2021 at 17:30):

tanks! :smile:

view this post on Zulip Sundar R (Oct 23 2021 at 17:30):

length(f::Fibn)=f.ncreates a Main.length, which is why that didn't work

view this post on Zulip rocco sprmnt21 (Oct 23 2021 at 17:33):

As an alternative to using the Base prefix, could I import the functions of which I need to define a new method?
So

import Base: iterate, eltype, length, size, peek

view this post on Zulip Sebastian Pfitzner (Oct 23 2021 at 17:51):

yes

view this post on Zulip rocco sprmnt21 (Oct 23 2021 at 21:51):

this is the version without bothering with Binet's formula

struct Fibn{Int}
    n::Int
end
import Base: iterate, length
f(n)=Fibn(n)
length(f::Fibn)=f.n
iterate(f::Fibn) = (0,(0, 1, 1))
iterate(f::Fibn, st) = st[3] < f.n ? (st[2], (st[2], st[1]+st[2],st[3]+1)) : nothing
collect(f(17))

view this post on Zulip Mason Protter (Oct 23 2021 at 22:55):

Nice!

view this post on Zulip Mason Protter (Oct 23 2021 at 23:10):

By the way the type parameter you used is a bit misleading. It defines a parameter named "Int" that can be any type

view this post on Zulip Mason Protter (Oct 23 2021 at 23:40):

Here is the naïve way one might translate this to Transducers.jl speak:

julia> using Transducers; using Transducers: @next, complete

julia> struct Fibnt
           n::Int
       end

julia> function Transducers.__foldl__(rf, val, f::Fibnt)
           val = @next(rf, val, 0)
           st = (0, 1, 1)
           while st[3] < f.n
               val = @next(rf, val, st[2])
               st = (st[2], st[1]+st[2], st[3]+1)
           end
           complete(rf, val)
       end

julia> collect(Map(identity), Fibnt(17))
17-element Vector{Int64}:
   0
   1
   1
   2
   3
   5
   8
  13
  21
  34
  55
  89
 144
 233
 377
 610
 987

view this post on Zulip Mason Protter (Oct 23 2021 at 23:43):

This gives you a lot of things for free, like an efficient implementation of the sum of the sines of the first 5 Fibonacci numbers:

julia> foldl(+, Map(sin), Fibnt(5))
2.733359404501342

view this post on Zulip rocco sprmnt21 (Oct 24 2021 at 07:37):

Tanks @Mason.
In fact I don't know well the syntax of structures and types (I went a little naively, maybe too much ...)
I'll try to study your example once I understand how the iterate interface works.
For example, I don't know what's wrong with the collect (f (10)) part in the following script - the rest seems to work fine.
It seems that the iterate function that calls collect is different from the ones defined by me.
Can't I change the position of the parameters (itr and status)?
Must these parameters necessarily be two and in the above order?

struct Fib
    n::Int
end

f(n)=Fib(n)
Base.length(f::Fib)=f.n
Base.iterate(f::Fib) = ((0, 1, 1),0)
Base.iterate(st,f::Fib) = st[3] < f.n ? ((st[2], st[1]+st[2],st[3]+1),st[2]) : nothing
# this seems work

julia> f1=Base.iterate(f(10))
((0, 1, 1), 0)

julia> f2=Base.iterate(f1[1],f(10))
((1, 1, 2), 1)

julia> f3=Base.iterate(f2[1],f(10))
((1, 2, 3), 1)

#this not
julia> collect(f(5))
ERROR: MethodError: no method matching iterate(::Fib, ::Int64)

The first thing I'm not sure I understand well is the following definition:

f(n)=Fib(n)

view this post on Zulip Simeon Schaub (Oct 24 2021 at 14:01):

Base.iterate(st,f::Fib) = st[3] < f.n ? ((st[2], st[1]+st[2],st[3]+1),st[2]) : nothing

This is the wrong argument order. f::Fib needs to be the first argument.

view this post on Zulip rocco sprmnt21 (Oct 24 2021 at 16:35):

I apologize in advance if I say nonsense: I proceed a little by analogies.
I have not explicitly seen the constraint that the arguments to iterate (args ...) must be 1 or 2 and in the order itr, state.
But I am aware that thinks are like this ( (that's why I asked the questions on these aspects at the beginning of the previous message),
I wanted to understand if it was just a convention or a strict necessity.
The hand-made simulation of the iterative calls of the iterate function that I have defined seems to work.
Collect () instead seems to expect another function / method iterate.
There is a way to force the function to zero type
Base.iterate (f :: Fib) = ((0, 1, 1), 0)
so that it is of type Fib?
That is to have
Base.iterate (f :: Fib) = ((0, 1, 1), zero (Fib)).
Would this force collect () to call the iterate function with the arguments reversed?

view this post on Zulip Sebastian Pfitzner (Oct 24 2021 at 16:47):

check out https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration for you questions about the iteration API


Last updated: Nov 22 2024 at 04:41 UTC