Fork me on GitHub
#beginners
<
2018-02-03
>
Michael Stokley17:02:25

reduce is left to right. is there a generic way to reduce right to left, without a) reversing the collection or b) using the reducers library?

Michael Stokley17:02:31

seems like the answer is, 1) try not to need foldr and 2) use the reducers library

noisesmith17:02:25

if the input is a vector, rseq is cheap unlike reverse

Michael Stokley17:02:19

it's not cheap to reverse a clojure list?

Michael Stokley17:02:02

it's because vectors are optimized for indexing?

noisesmith17:02:07

no, you have to consume the whole thing - it's O(n)

noisesmith17:02:22

because vectors are indexed, and have cheap methods for walking in reverse

noisesmith17:02:30

sorry - that is, reversing list or seq is not cheap, you need to consume the whole thing in order to construct it, a vector is cheap because there's a simple way to consume it end to beginning order, rseq packages that as a feature

Michael Stokley18:02:58

i take it it's idiomatic to recursively invoke a function if you are handling multiple arities. can anyone confirm?

Michael Stokley18:02:28

e. g.

(defn tax-amount
  ([amount]
     (tax-amount amount 35))
  ([amount rate]
     (Math/round (double (* amount (/ rate 100))))))

noisesmith18:02:38

yes, that's the correct way to do multiple arities

Michael Stokley18:02:09

because even though the stack frames will be left open, it won't be very deep?

noisesmith18:02:38

right - it's bounded to one - there's a lot of standard clojure idioms that go deeper than that

noisesmith18:02:06

(every use of a var by name does a var lookup implicitly, for example)

Michael Stokley18:02:38

assoc-in is defined recursively

Michael Stokley18:02:40

user=> (source assoc-in)
(defn assoc-in
  "Associates a value in a nested associative structure, where ks is a
  sequence of keys and v is the new value and returns a new nested structure.
  If any levels do not exist, hash-maps will be created."
  {:added "1.0"
   :static true}
  [m [k & ks] v]
  (if ks
    (assoc m k (assoc-in (get m k) ks v))
    (assoc m k v)))

Michael Stokley18:02:00

i thought this was not correct?

noisesmith18:02:14

it's something that can't be done with recur

noisesmith18:02:33

unless you create an extra local binding to represent the pending parent data structures as you go

Michael Stokley18:02:12

why wouldn't that have been done here, in the clojure source code?

bronsa18:02:37

because the stackframe grows only in the lenght of the binding vector here

bronsa18:02:48

which is never going to be so big to be an issue in practice

noisesmith18:02:50

because an extra local to capture the pending data structures increases the complexity of the code quite a bit

noisesmith18:02:03

(plus the extra step to wrap it all up again)

Michael Stokley18:02:11

well bless my nippers

Michael Stokley18:02:18

bless them all day long!

Michael Stokley18:02:53

if i'd known this was permitted for short collections...

schmee18:02:10

be wary of get-in, assoc-in et. al if you’re trying to write tight loops with high performance, they are fast enough for general use but in those cases they don’t cut it

Michael Stokley19:02:54

@U3L6TFEJF what alternative to assoc-in would you use if you did need the performance?

schmee20:02:33

for me, two options: either https://github.com/nathanmarz/specter, or write a method and unroll it manually

Michael Stokley21:02:45

wow, this is terrific

Michael Stokley21:02:36

and gratifying to see confirmation that "querying and transforming nested and recursive data is complex in vanilla clojure"!

schmee23:02:40

yeah, specter is a life-saver in certain situations 🙂

bronsa19:02:42

if the recursion depth is known at invoke time and is quite small no reason to avoid recursion

bronsa19:02:02

for assoc-in the depth is (* 2 (count b)) which will always be quite small

Michael Stokley19:02:53

maybe it's that with nested maps, in order to add another innermost map, you have to traverse the entire nested structure. and you'd do that every loop, going one level deeper each time

Michael Stokley19:02:26

i think you have to keep track of the sequence of keys you used to get to where you are as well as the in-progress, pending result

Michael Stokley19:02:26

compared to cons-ing a list together item by item as you go, for example, where there's no need to understand "where you are" in that list

Michael Stokley19:02:52

in an imperative style, you'd have a cursor and mutate as you go and have no need to recreate the map as a whole every time

Michael Stokley19:02:12

as opposed to either imperative style in place mutation or real recursion, loop/recur seems to be uniquely difficult

Michael Stokley19:02:35

and maybe you can't always express these other algs into loop/recur

Michael Stokley19:02:55

i guess i saw that earlier today with the lack of foldr