Welcome! Please see the About page for a little more info on how this works.

+1 vote
in Clojure by
Many apis (elasticsearch, github, s3, etc) have parts of the api
which, in usage, end up being used in an interative way. You make an
api call, and you use the result to make another api call, and so
on. This most often shows up in apis have some concept of pages of
results that you page through, and is very prevalent in http apis.

This appears to be such a common pattern that it would be great if
Clojure had in built support for it.

You may think Clojure already does have support for it, after all,
Clojure has `iterate`. In fact the docstring for `iterate`
specifically says the function you give it must be free of side
effects.

I propose adding a function `unfold` to clojure.core to support this
use case. `unfold` would return an implementation of ReduceInit. The
name `unfold` matches what would be a similar Haskell function
(https://hackage.haskell.org/package/base-4.8.2.0/docs/Data-List.html#v:unfoldr)
and also matches the name for a similar function used in some existing
Clojure libraries
(https://github.com/amalloy/useful/blob/develop/src/flatland/useful/seq.clj#L128-L147).

`unfold` in some ways looks like a combination of `take-while` and
`iterate`, except for the fact that `iterate` requires a pure
function. Another possible solution would be a version of `iterate`
that doesn't require a pure function.

It seems like given the use case I envision for `unfold`, a
non-caching reducible would be perfect. But that would leave those
that prefer seqs high and dry, so maybe at least some consideration
should be given to seqs.

Mailing list discussion is here
(https://groups.google.com/forum/#!topic/clojure-dev/89RNvkLdYc4)

A sort of dummy api you might want to interact with would look something like


(import '(java.util UUID))

(def uuids (repeatedly 1000 #(UUID/randomUUID)))

(def uuid-index
  (loop [uuids uuids
         index  {}]
    (if (seq uuids)
      (recur (rest uuids) (assoc index (first uuids) (rest uuids)))
      index)))

(defn api
  "pages through uuids, 10 at a time. a list-from of :start starts the listing"
  [list-from]
  (let [page (take 10 (if (= :start list-from)
                        uuids
                        (get uuid-index list-from)))]
    {:page page
     :next (last page)}))


given the above api, if you had an implementation of `unfold` that took a predicate that decided when to continue unfolding, a producer which given a value in a sequence produced the next value, and an initial value, you could do something like this:


(= uuids (into [] (mapcat :page) (unfold :next (comp api :next) (api :start))))


and the result would be true.

The equivilant take-while + iterate would be something like:


;; the halting condition is not strictly the same
(= uuids (into [] (mapcat :page) (take-while (comp seq :page) (iterate (comp api :next) (api :start)))))

14 Answers

0 votes
by

Comment made by: hiredman

I made two patches, one adds unfold as discussed above, one adds ingeminate which is like iterate but without the function purity restrictions, and doesn't return a seq.

0 votes
by

Comment made by: gshayban

Though syntax is less important than the semantics, may I propose the name progression for this? Clojure's fold is called reduce, so unfold is too much like Haskell. Other names I was considering include evolve & derivations.

0 votes
by

Comment made by: alexmiller

Another option would be productions (reminiscent of reductions).

0 votes
by

Comment made by: hiredman

productions has a nice ring to it. emanate could work too, would sort near eduction

0 votes
by

Comment made by: gshayban

Adding a patch with a generator impl that is clojure.lang.{Seqable,IReduceInit}.

Generative tests assert that the seq and reduce halves are equivalent.

Tests assert basic functionality, obeying reduced, and maximal laziness of the seq impl.

Docstring has been wordsmithed and the function named productions.

0 votes
by

Comment made by: hiredman

apparently unfold is part of SRFI 1: List Library in scheme land http://srfi.schemers.org/srfi-1/srfi-1.html#FoldUnfoldMap

it looks like their unfold is take-while + iterate + map

0 votes
by

Comment made by: gshayban

Main differences between Scheme's impl and this proposed one:
Predicate reversed (stop? vs continue?)
Scheme has a "mapping function" to produce a different value from the current seed, Clojure doesn't (but has transducers)
Scheme has an extra optional arg to build the tail of the list

Now I'm partial to the name {{successions}}.

0 votes
by
_Comment made by: michalmarczyk_

I can confirm that I found {{unfold}} quite useful in my Scheme days.

In Clojure, this general pattern can be expressed using transducers at a modest cost in keystrokes:


(def numbers (doall (range 1000)))

(defn api [list-from]
  (if list-from
    (let [page (vec
                 (take 10 (if (= :start list-from)
                            numbers
                            (drop list-from numbers))))]
      {:page page
       :next (some-> (last page) inc)})))

(= numbers
   (sequence (comp (take-while some?)
                   (mapcat :page))
             (iterate (comp api :next)
                      (api :start))))
;= true


Maybe this could be simplified with an xform-enabled version of {{iterate}}?


(defn iterate*
  ([f seed]
   (iterate f seed))
  ([xform f seed]
   (sequence xform (iterate f seed))))

(= numbers
   (iterate*
     (comp (take-while some?) (mapcat :page))
     (comp api :next)
     (api :start)))
;= true


Admittedly this takes more characters, but is quite generic and a transducer-enabled overload in {{iterate}} feels pretty natural to me. Attaching a simple patch implementing this in {{clojure.core/iterate}} – I'll look at {{clojure.lang.Iterate}} to see if it's worth implementing direct support later, unless of course nobody wants this. :-)
0 votes
by

Comment made by: michalmarczyk

0001-CLJ-1906-transducer-enabled-iterate.patch adds a ternary overload to {{iterate}} that delegates to the binary overload and {{sequence}}.

0 votes
by

Comment made by: gshayban

A few unsatisfactory things about overloading {iterate}
1) iterate's docstring says {f must be free of side-effects}
2) There is boilerplate and subtlety around the terminating item. In this case the final API call is made unconditionally, leading to an extra empty/marker item that is filtered by take-while. With the current proposal, the predicate controls iteration from the inside out

0 votes
by

Comment made by: gshayban

updated patch to apply cleanly to core

0 votes
by

Comment made by: gshayban

I'm not sure I'm sold on this anymore, and have suggested a different approach on the mailing list https://groups.google.com/d/msg/clojure-dev/89RNvkLdYc4/PAJh8gfmDAAJ

0 votes
by

Comment made by: gshayban

I have been marinating upon two generator functions that cover use-cases including the one listed above.

One of them is similar to Scheme's unfold but with some deviations more appropriate to Clojure. The other function takes a side-effecting producer and a sentinel value.

Ignore the naming and examine the semantics. https://gist.github.com/ghadishayban/902373e247e920855139902912d237f0

0 votes
by
Reference: https://clojure.atlassian.net/browse/CLJ-1906 (reported by hiredman)
...