Fork me on GitHub
#beginners
<
2018-02-03
>
michael74017: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?

michael74017: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

michael74017:02:19

it's not cheap to reverse a clojure list?

michael74017: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

michael74018:02:58

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

michael74018: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

michael74018: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)

michael74018:02:38

assoc-in is defined recursively

michael74018: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)))

michael74018: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

michael74018: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)

michael74018:02:11

well bless my nippers

michael74018:02:18

bless them all day long!

michael74018: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

michael74019:02:54

@ 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

michael74021:02:45

wow, this is terrific

michael74021: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 🙂

michael74018:02:54

good to know

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

michael74019: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

michael74019: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

michael74019: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

michael74019: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

michael74019:02:12

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

michael74019:02:35

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

michael74019:02:55

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