Julia equivalence of Haskells unfoldr

Might be a stupid question but I know julia has the foldl and foldr functions but I cannot find the unfold versions. For example in Haskell we have the unfoldr function which produces a list based on an initial value. Does julia have an equivalent function for this? I tried searching for it but nothing useful came up.

1 Like

Since it that is very close to the iterator protocol, you can just do

struct UnfoldingIterator{T,F}
    init::T
    f::F
end

Base.iterate(uf::UnfoldingIterator) = uf.init, uf.init

function Base.iterate(uf::UnfoldingIterator, state)
    maybestate = uf.f(state)
    if maybestate ≡ nothing
        nothing
    else
        state = something(maybestate)
        state, state
    end
end

Base.IteratorSize(::Type{<:UnfoldingIterator}) = Base.SizeUnknown()

Base.IteratorEltype(::Type{<:UnfoldingIterator}) = Base.EltypeUnknown()

then

julia> collect(UnfoldingIterator(10, x -> x == 0 ? nothing : Some(x-1)))
11-element Array{Int64,1}:
 10
  9
  8
  7
  6
  5
  4
  3
  2
  1
  0
4 Likes

Cool and indeed it is. Maybe it’s worth making a Functional.jl containing this. I quite like the functional programming approach. Do you know if it’s a conscious decision to not have it in base as foldl and reduce are there?

I don’t really know. I can make a PR to IterTools.jl.

1 Like

I am guessing this didn’t happen?

It’s pretty similar to the accumulate function, no?

I don’t think so but I am a julia noob. A fold takes a list and squashes it down to something; an unfold takes a something and creates a list. Here’s an example of taking an integer and creating a binary representation and a list of 0s and 1s.

extractBinDigits :: Int -> [Int]
extractBinDigits =
  unfoldr (\x -> if x == 0 then Nothing else Just (mod x 2, div x 2))
1 Like

uh, no? accumulate applies a binary operator to an already existing list, and return a list of the same size. unfoldr applies an unary operator to any value (not only lists) and return a list of unknown size (potentially infinite).

Ah, thanks, sorry for the confusion.

Thank you for taking the time :grinning:

No, I didn’t make the PR, but if my solution works for you, feel free to use the code for the purposes of a PR.

Made a PR for this that arguably improves on the definition a bit: Add `unfoldr` to Iterators by cmcaine · Pull Request #43203 · JuliaLang/julia · GitHub

2 Likes