Fork me on GitHub
Slack Archive

This page is not created by, affiliated with, or supported by Slack Technologies, Inc.

2021-07-31

Channels

#off-topic
<
2021-07-31
>
seancorfield23:07:47

You can write map and filter in terms of reduce.

seancorfield23:07:33

into is written in terms of reduce as I recall?

seancorfield23:07:03

into = reduce conj

Max23:07:59

The usual example of an un-reduceable function is sort

Ben Sless05:08:07

Into sorted collection?

seancorfield23:07:29

@max.r.rothman I think you can write sort as a double-`reduce` implementation of insertion sort?

Max23:07:24

Hm, maybe you’re right. I vaguely remember from my haskell days that there’s an isomorphism between folds and recursion or something

Max23:07:00

I think it should be possible, lemme cook something up…

seancorfield23:07:05

Back when I was doing my PhD work on FP language implementation and design, one of the exercises was looking at "primitive" FP operations and as I recall there was a five(?) argument function from which you could build map, filter, reduce, etc...

Ben Sless05:08:44

Is this related to SKI combinators?

seancorfield05:08:58

That's kind of taking it to mathematical extremes but, yeah, it's all somewhat related.

seancorfield05:08:36

I can't remember the name I used in my thesis for the 5-argument HOF I outlined. I think I called it R. But part of the work was to show that if you implemented that as a primitive in the engine, you could build all the rest using pretty much any FP style syntax, and that was really where I was working: looking at a variety of syntax to see what was more expressive and what was a worthwhile set of primitives for a language.

seancorfield05:08:14

My other work was focused primarily on GC strategies to support FP languages. Back then, it was all single-threaded and so it was about figuring out how to interleave GC work with actual VM operations and still have a responsive interactive system.

💯 2
seancorfield23:07:43

Part of the way there is 

(defn chn [c h n l] (if (seq l) (c (h (first l)) (chn c h n (rest l))) n))
Then you abstract away the first/rest functions.

dgb2323:07:33

As long as it’s iterative?

Max23:07:13

In general, I think you can probably write any function that takes and returns a coll in terms of reduce. There may be special cases in which you can write certain functions in terms of reduce as long as they take a coll (even if they don’t return one)

Max23:07:18

Right, it’s a restricted form of the problem of “what’s foldable”

dgb2323:07:54

I’m rereading SICP in prep for Software Design for flexibility and it’s more useful to revisit fundamentals than I thought.

➕ 2
seancorfield23:07:26

I was slightly off with chn above (I've corrected it) but here's map in terms of it: 

user=> (defn chn [c h n l] (if (seq l) (c (h (first l)) (chn c h n (rest l))) n))
#'user/chn
user=> (defn map1 [f l] (chn cons f () l))
#'user/map1
user=> (map1 inc [1 2 3 4])
(2 3 4 5)

dgb2323:07:14

Reduce can also be abused, because it’s easy to pack tons of stuff in it

seancorfield23:07:43

With reduced letting you short-circuit execution, you can do a lot of interesting reduce ops.

dgb2323:07:21

It’s as important to know when not to use it I think.

dgb2323:07:14

I think the canonical examples are aggregate functions like sum, average etc. if it doesn’t feel like them, maybe it’s the wrong function?

deleted23:07:08

can you do average with reduce?

raspasov00:08:35

Using https://github.com/cgrand/xforms 

(require '[net.cgrand.xforms :as x])

(sequence
 (x/partition 3 x/avg)
 (range 9))

;=> (1.0 4.0 7.0)

hiredman03:08:18

You can also use a streaming average estimator if you don't need to be completely accurate

hiredman03:08:34

something like (fn [avg value] (+ avg (* 0.05 (- value avg)))) will often spit out something close to the average

hiredman03:08:41

(the 0.05 may need some tuning though)

hiredman03:08:48

user=> (reduce (fn [avg value] (+ avg (* (/ 1.61803 100) (- value avg)))) 0 (range 100))
50.290307530750695
user=>
(using the golden ratio)

jjttjj13:08:23

Also transduce can do it: 

(transduce identity
  (fn
    ([] [0 0]) ;;initiaize [ct sum]
    ([[ct sum]] (/ sum ct)) ;;calculate average on completion
    ([acc x] ;;update ct and sum on each step
     (-> acc
         (update 0 inc)
         (update 1 + x))))
  [1 2 3 4 5])