Fork me on GitHub
#clojure-dev
<
2018-12-11
>
mfikes00:12:27

Is there anything about nth that requires it to realize the sequence it operates upon? In terms of a concrete example, this (sketch) of an alternative nth doesn't

(defn nth' [coll n] (transduce (drop n) (completing #(reduced %2)) nil coll))
if applied to something directly reducible (like the result of iterate). Why am I asking? ClojureScript currently doesn't have locals clearing, and an nth that behaves this way is useful in situations where n is huge and the head holding will exhaust the heap. I can imagine reasons for not ever having core nth behave this way, but I'm asking simply to help clarify my thinking on the subject.

hiredman00:12:07

to me "realize the sequence" implies the construction of the sequence even if it is immediately thrown away, which that will still do for lazy seqs

hiredman00:12:59

when applied to something directly reducible, that still steps through the intervening items

mfikes00:12:29

Maybe a better definition of that is realized? returning true, and things not effectively acting like eduction, recalculating, etc.

hiredman00:12:05

which, technically isn't realizing a sequence, but it can be hard to make a meaningful distinction

hiredman00:12:08

I am not sure I follow, realized? (at least in clojure) seems pretty useless for reasoning about this kind of thing

hiredman00:12:01

if you really want to optimize nth for non-seq things, what not give range a version of nth that does it closed form?

mfikes00:12:03

Fair enough. Here is a motivating concrete example. Consider f, which may be pure, but expensive. The above nth' is nice on memory in ClojureScript if you do, say (nth (iterate f x) 100000)

Alex Miller (Clojure team)00:12:32

in seq worlc, nthrest / nthnext are used to avoid some portion of the realization cost

Alex Miller (Clojure team)00:12:23

I think you could use halt-when for something like this in a reducible context too

hiredman00:12:02

in clojure nth is backed by the Indexed interface, so you could have your reducible type implement what efficient nth you want

hiredman00:12:09

it sounds like the root problem is the lack of locals clearing, not some special optimization of nth though

mfikes00:12:30

Yes, really, to fix this ClojureScript should implement locals clearing.

mfikes00:12:16

Revising nth to workaround such a thing would be nothing more than a workaround. But, it got me thinking about whether it is even legitimate to consider nth behaving that way.

mfikes00:12:34

Put it another way, if someone asked: Why can't nth behave that way, it would be nice if there was a specific concrete reason that prohibited it.

mfikes00:12:28

This is mostly a mental exercise, I'm not pushing to have nth revised in ClojureScript, and it would even more put my mind at rest if I knew there was a prohibition of some sort.

hiredman00:12:59

does clojurescript have an analog to clojure.lang.Indexed?

mfikes00:12:21

Yeah, cljs.core/IIndexed, which is what nth is for.

mfikes00:12:47

And yes, iterate returns an Iterate that could implement IIndexed...

hiredman00:12:10

so any type can choose to provide a different nth implementation, which is a similar but not the same thing as could the generic nth implementation be different

mfikes00:12:33

(That would be odd though, because it is supposed to be O(1) , right? Hrm.)

mfikes00:12:50

Actually, nah, nth can be linear.

hiredman00:12:56

ah, actually that might be a thing, if it implements Indexed it is supposed to be O(1), and if doesn't implement Indexed it is O(n) via seq

mfikes00:12:41

My primary argument against making nth behave this way is that it would introduce recalculating in some code where things are currently cached, so in my mind I don't think it should ever happen in ClojureScript. But it sounds like, apart from that perf concern, it may actually be an open question on whether nth could be like nth' above.

mfikes00:12:43

By the way, halt-when is new to me. I must have missed it. Gonna definitely check that one out. 🙂