Iterating over pairs in a functional programming way · helpdesk (published)

Stream: helpdesk (published)

Topic: Iterating over pairs in a functional programming way

Davi Sales Barreira (Jun 16 2023 at 17:48):

Suppose I have a struct Line that takes two values. I want to write a function p(x) that tkes [x_1,...,x_n] and returns a vector of
[Line(x_1,x_2), Line(x_2,x_3)...].

I know I can simply write p(x) = map(Line, x[1:end-1], x[2:end]), but I was looking for a functional programming way of doing this... Something in the lines of map((x,y)->Line(x,y) zip(head(x), tail(x))... But this head and tail functions do not seem to be shipped on Julia. Also, it would be neat to have a general function for iterating over such pairs, triples, and so on.

I thought of using a foldl, but this does not work properly, as it returns something like Line(1,Line (2, Line(3,4))).

Another point is that the functiion should work for any Vector type, hence, it should not use stuff like [2:end], where one assumes that the vector has at least two values...

I imagine that p(x) should be something similar to a fold in the sense of having an init. For a singleton vector could perhaps return Line(init, x[1]), and for an empty vector it could return Line(init,init).

Any ideas?

Michael Fiano (Jun 16 2023 at 17:55):

It sounds like you just want to define a couple methods with that linear function to implement the iteration interface?

Michael Fiano (Jun 16 2023 at 17:56):

Base.iterate and its 2 methods for your type, that is.

Mason Protter (Jun 16 2023 at 17:58):

Davi Sales Barreira said:

Suppose I have a struct Line that takes two values. I want to write a function p(x) that tkes [x_1,...,x_n] and returns a vector of
[Line(x_1,x_2), Line(x_2,x_3)...].

I know I can simply write p(x) = map(Line, x[1:end-1], x[2:end]), but I was looking for a functional programming way of doing this...

What about that is not functional?

Michael Fiano (Jun 16 2023 at 18:02):

I took it to mean lazily compute the values, and then I immediately thought iteration interface. @Davi Sales Barreira if you check out the Interfaces section of the Manual, it lays out the iteration interface, and proceeds with an example similar (lazily computing the squares of a scalar) to what (I believe) you are looking for.

Mason Protter (Jun 16 2023 at 18:03):

Doing this with iterators instead of slicing could work, but it sounds hard to do it in a way that wouldn't be silently incorrect with stateful iterators

Davi Sales Barreira (Jun 16 2023 at 18:03):

Mason Protter said:

Davi Sales Barreira said:

Suppose I have a struct Line that takes two values. I want to write a function p(x) that tkes [x_1,...,x_n] and returns a vector of
[Line(x_1,x_2), Line(x_2,x_3)...].

I know I can simply write p(x) = map(Line, x[1:end-1], x[2:end]), but I was looking for a functional programming way of doing this...

What about that is not functional?

I mean, it assumes the vector to be at least of size 2, hence it fails for the other cases.

Mason Protter (Jun 16 2023 at 18:03):

I guess I don't understand what that has to do with functional programming

Michael Fiano (Jun 16 2023 at 18:03):

Neither do I

Davi Sales Barreira (Jun 16 2023 at 18:04):

Here is what I came up with:

getlast(x::Nothing) = nothing
getlast(x::Tuple) = x[end]

safecollect(x::Nothing) = nothing
safecollect(x) = collect(x)

tail(x) = safecollect(getlast(Iterators.peel(x)))
head(x) = safecollect(getlast(Iterators.peel(Iterators.reverse(x))))
map(x->Line(x[1],x[2]), zip(head(x), tail(x)))

Davi Sales Barreira (Jun 16 2023 at 18:05):

Mason Protter said:

I guess I don't understand what that has to do with functional programming

Sorry, I'm not very proficience on functional programming... When I say this, I mostly mean something that would be directly implementable in Haskell.

Davi Sales Barreira (Jun 16 2023 at 18:07):

Makes sense?

Michael Fiano (Jun 16 2023 at 18:08):

Ok, so do you mean that you want state to be hidden away with monads?

Michael Fiano (Jun 16 2023 at 18:09):

Iterators may mutate the state, and it is explicitly passed as an argument.

Michael Fiano (Jun 16 2023 at 18:09):

I'm not sure how to program like haskell in Julia though, sorry.

mbaz (Jun 16 2023 at 18:17):

Also, take a look at Base.front and Base.tail (not exported for some reason)

Mason Protter (Jun 16 2023 at 18:20):

Is returning an empty list an acceptable fallback instead of some init value?

Mason Protter (Jun 16 2023 at 18:20):

julia> using Transducers

julia> struct Line{T}
           x::T
           y::T
       end;

julia> [:x1, :x2, :x3] |> Consecutive(2; step=1) |> MapSplat(Line) |> collect
2-element Vector{Line{Symbol}}:
 Line{Symbol}(:x1, :x2)
 Line{Symbol}(:x2, :x3)

julia> [:x1,] |> Consecutive(2; step=1) |> MapSplat(Line) |> collect
Any[]

julia> [] |> Consecutive(2; step=1) |> MapSplat(Line) |> collect
Any[]

Davi Sales Barreira (Jun 16 2023 at 18:22):

Very interesting. I've been trying to understand how transduscers work. I'll take a look at the package again. Thanks

Mason Protter (Jun 16 2023 at 18:26):

If you feel a need for a haskell version of everything I guess you could look at https://github.com/hypirion/haskell-transducers

Mason Protter (Jun 16 2023 at 18:27):

No idea if this thing is well implemented or not though

Mason Protter (Jun 16 2023 at 18:29):

Personally, I think Transducers are a much more elegant and natural functional programming approach to data traversal than anything I've seen come out of Haskell land

Davi Sales Barreira (Jun 16 2023 at 20:21):

Ok, I'm reading Transducers.jl documentation, and it's amazing. I was wondering if fthere is a formalization of it in terms of category theory,

Michael Fiano (Jun 16 2023 at 20:27):

@Davi Sales Barreira I am not sure, but also check out libraries that work with transducers, like Folds.jl and FLoops.jl

(also note that these projects live in the JuliaFolds organization, but the original maintainer went missing. Upgraded versions are forming in the JuliaFolds2 organization)

Mason Protter (Jun 16 2023 at 20:42):

I was wondering if fthere is a formalization of it in terms of category theory

The core idea is not new, it's just the concept of lenses which are described in category theoretic terms here: https://ncatlab.org/nlab/show/lens+%28in+computer+science%29

Mason Protter (Jun 16 2023 at 20:43):

but the details of various things are important, such as how transducers handle early termination, state, initialization, etc.

jar (Jun 16 2023 at 20:44):

https://hypirion.com/musings/haskell-transducers
https://hypirion.com/musings/transducers-to-conduits-and-back

Davi Sales Barreira (Jun 17 2023 at 11:53):

You mean @Takafumi Arakaki (tkf) is not contributing anymore??? I've followed lots of his sutff. Any idea on what happened?

Michael Fiano (Jun 17 2023 at 12:02):

Davi Sales Barreira said:

You mean Takafumi Arakaki (tkf) is not contributing anymore??? I've followed lots of his sutff. Any idea on what happened?

Since October, and unfortunately, nobody knows why.

Davi Sales Barreira (Jun 17 2023 at 12:14):

Michael Fiano said:

Davi Sales Barreira said:

You mean Takafumi Arakaki (tkf) is not contributing anymore??? I've followed lots of his sutff. Any idea on what happened?

Since October, and unfortunately, nobody knows why.

That is truly unfortunate.

Last updated: Oct 02 2023 at 04:34 UTC