Hacker News Reader

Comment by rspeele | Hacker News Reader

Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.

Reduce has an accumulator and a 2-arg function and languages are not very consistent amongst each other as to whether it's reduce(initial_acc, callback(acc, elem)) or reduce(callback(acc, elem), initial_acc) or reduce(callback(elem, acc), initial_acc) or what.

Hard to remember. Also some languages have a version of reduce that doesn't take an initial accumulator at all, which is just a footgun waiting for you to hit an empty collection. Also ALSO, the accumulator can easily become awkward in languages that don't support anonymous types or don't support easy mutation of an anonymous type record. Which is most of them!

View on HN

Haskell got this right. You have foldr (right fold) and foldl' (left fold), and the order of the callback is opposite. If you do a left fold, then the initial accumulator is applied on the left; if you do a right fold, then the initial accumulator is applied on the right.

    foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
    foldl' f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

The mnemonic here is that the folding function (aka the callback) replaces the comma.

I find this slightly easier to remember than other languages. In contrast most other languages do not simultaneously provide a left fold and a right fold, so they do not consider this aspect, making things more difficult to remember.

That said I totally agree this requires more brainpower to read and write than map or filter. For this reason I have sometimes refactored code to use foldMap instead of foldr or foldl', so one no longer needs to think of the direction of the fold or the order of arguments.

In other words, look at the types. The type of the folding function (the first argument) indicates how each fold works.

  foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

  foldr  :: Foldable t => (a -> b -> b) -> b -> t a -> b

That's what I tend to do, but since foldr/foldl' is so ubiquitous in Haskell it would be nice if I could just remember the argument order of the callback. kccqzy's explanation (in particular "it replaces the comma") might just help me do that :)

Since you mention mnemonics, here are the mnemonics I use to remember the (symmetrical) differences between foldr and foldl

https://arialdomartini.github.io/fold-mnemonics

I admit that I have always looked at an explanation like yours with x1,...,xn when using fold because I could never keep it straight in my mind.

It's still a complex and more abstract function than map or filter. Those do a single thing that's easy to grasp. reduce/fold can be easily abused to duplicate the effect of most other collection functions, at the cost of making the code less readable. Although for slightly-too-clever people, that could mean you only need to know one function instead of all of them.

But it hurts readability. If you're going to do it, at least don't use it anonymously, but give it a name that clearly describes what's going on.

But even then, there can be hidden performance traps. I've often seen javascript that used reduce and created the new accumulator by using a spread on the old accumulator and adding the new one: `[...acc, newValue]`. But that spread is another iteration inside a loop, turning it from O(n) to O(n^2). A for loop where you append it is much faster.

When the accumulator isn't the second argument in a fold, left or right, it feels wrong and I waste some time cursing whomever made a silly mistake like getting the order wrong.

You want the accumulator second to match up with `cons` and similar functions that expect an initial/existing value second.

Luckily the functional languages I use the most are sane in that respect.

Ruby's `[1, 2, 3].inject(:+)` alias for `reduce` (name borrowed from Smalltalk) nicely reinforces that very mnemonic: you inject the operator _between_ the elements: 1 + 2 + 3. :+ here is symbol meaning "send + message", more general form takes a block:

    [1, 2, 3].inject { |a,b| a + b }

The downside of the "between" mnemonic is encouraging not handling an empty collection! Ruby's separate syntax to pass (args) {block} at least offers natural place to add initial value, but with symbol shorthand the API is harder to guess:

    numbers.inject(0) { |a,b| a + b }
    numbers.inject(0, :+)

(Also, it's always a left fold ((a) OP b) OP c, even if you give a symbol like :* which parses right-assiciative without parens — making the "inject operator between values" mental model less accurate.)

In GNU Guile `reduce` is described as a special case of `fold`, where the first element is suitable to be used as initial value, while `fold` is more general and lets you specify another initial value. I think that makes a lot of sense.

> … to call them Select and Where.

While map is a great name, I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them.

I mean, it’s like a colander: you filter noodles and water, but which one do you keep? The noodles, right? But, replace noodles with tea and now you want to keep the water part.

Naming is hard I guess.

I've never run into a generic "filter" function which keeps only the non-matching elements.

Smalltalk has #reject: which does that. You could, of course, just wrap a not around the test in the closure, but sometimes reject with a well-named predicate is easier to read.

bsnpApproved := tvShows reject: [ :eachShow | eachShow hasNaughtyContent ].

Common Lisp's filter is remove-if which works this way.

(It also has remove-if-not but that's deprecated and if you use it your code smells.)

`remove-if-not` was deprecated before the Common Lisp standard was approved and yet it remained (and will never be removed because the standard will never be updated). That's not deprecated for any practical purpose. And it's more convenient than using `(remove-if (complement #'some-predicate) sequence)`

Scheme has `filter` and `filter-not` in the SRFI-1 list library. Both of which can easily be written using a fold to bring this vaguely on topic.

Nope! Common Lisp's filter is in fact remove-if-not, which is exactly the same thing as "keep if": keep all items which match the predicate (removing those that do not).

I suspect the reason the function was deprecated was its naming, nothing more; had it been called retain-if or keep-if, it would not have attracted deprecating attention.

The smell added to your code is just the double-negative name of that function, not what it's doing for you.

The name filter smells even more. Is that filtering for items that match? Or filtering out?

In physical filters, sometimes the filtrate is considered the payload output (that which passes through the filter) and sometimes the retentate (that which is caught in the filter).

keep-if is readable.

I agree that keep-if is a better name. But you reiterated my point: remove-if works in the counterintuitive way the original comment noted, i.e. not like the common connotation of 'filter.'

As for deprecation, IIRC the '-if-not' functions were deprecated because the committee felt the 'complement' function accomplished that task better.

Edit: My IIRC seems largely correct. More detail at

https://www.lispworks.com/documentation/HyperSpec/Issues/iss...

Nonetheless, they were fooled by that function, because it's just keep-if by a funny name that includes "not" suggesting that it contains a complement that might be factored out.

If you want keep-if, you don't want to use a different function, which forces you to complement your predicate. If you want (keep-if #'redp jellybean-list) to keep the red jelly beans, you don't want to write (remove-if (complement #'not-red-p) jellybean-list). If keep-if has a silly name remoe-if-not, you might nonetheless prefer (remove-if-not #'redp jelly-bean-list).

Shims like complements are ugly, and compilers won't optimize through them for arbitrary function definitions (whose source code is not even in scope), so it is good to have both keepers and removers. Heck, it's useful to have a function which does both in one pass returning two values: the filtrate and the retentate.

Maybe those two could be filter_for (the “where” case) and filter_out.

Kotlin has filter and filterNot (it also has separate "reduce" and "fold" functions, dependingon whether you want to specify an initial accumulator value or not)

If you're making tea with a colander something is very wrong ;)

depends on the size of the sieve, but sometimes one does cook a whole stewpot of tea at once (f.e. in canteen)

A colander would allow the tea leaves through to no purpose. A colander is a type of sieve but a sieve is not necessarily a colander.

I was thinking an apt analogy might be making stock -- you filter out all the solid food you don't want to keep in the liquid.

And it's a doubly-good analogy, because I have occasionally gotten that confused in real-life as well. Twice in the past ten years I've had a stock boil away for three hours, and then set a colander in the sink and poured it through, only to watch my beautiful stock swirl down the drain because motor-memory made me forget that I wasn't draining pasta but should have put the colander in a bowl...

This is painfully relatable.

Talking about un-guessable, misleading function names,

C++ std::remove.

I would never have guessed what it does exactly. (It moves elements that match the filter to the front, and moves the end-marker forward. Leaves all the elements in the collection. You need to erase them yourself. )

It returns the new end marker

Oh it's a bit like unordered-delete when using an arena. I guess I would have expected an ordered-delete instead

  > I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them

if you had parameter names maybe it might help?

`filter(where:)` like in swift...?

Doesn't seem to help the ambiguity to me.

maybe its the verb?

what about `exclude()` or `keep()`?

in those cases its less ambiguous (to me anyways) that returning true means 'yes' to 'keep' or 'exclude', whereas saying yes or no to filter is like 'filter to exclude or include?'

thats my take anyway

select/reject (Ruby)

There's always the Ruby strategy of just making all the names work. `select` and `filter` are buddies and you can use whichever you want or even go back and forth. Not a fan of `reduce`? That's fine, `inject` has got your back. Miss getting to type `collect` from Java or Rust? Don't worry, just use it instead of `map`, it's the same thing.

I believe Ruby uses names inspired by SmallTalk.

Yeah, Smalltalk has select, reject (inverted filter), collect (map) and inject.

Right, I'm just saying that it has a lot of aliases, which is fairly uncommon in most mainstream languages

The filter keeps the tea... it's just that you then lift the filter out of the cup, carrying the tea with it. Flip your brain around to see it from that direction and it might help you with the mnemonics.

> While map is a great name, I always struggle to remember if ‘filter’ keeps elements that match the condition or removes them.

In Common Lisp both functions exist, under the names `remove-if` and `remove-if-not`.

In elixir we have Enum.filter (run a predicate over the enumerable keeping the things that match the predicate) and Enum.reject (run a predicate over the enumerable removing the thing that match the predicate)

I think since we have a pair of them and reject is so obvious it helps me remember which way filter works.

I think Enum.keep and Enum.reject might be a better pair, but I've used them enough to internalize it now

In some programming languages with RPN you can avoid this problem, because it makes sense to put it in the stack as the initial value, and then you can as easily have multiple initial values; and then the callback function can read that from the stack that you had put there, like anything else you will push into the stack to read it back later. For example, in PostScript you can write something like:

  0 exch {add} forall

However, this is not as good if you want to use the first element as the initial value instead, but still it can be done but it is then not as simple (unlike in programming languages that do not use RPN but instead with function call with arguments, in which case it might be simpler).

I guess names as SELECT and WHERE are like SQL (although SQL works differently than other programming langauges).

Also reduce is a weird name.

Why? It does, after all, reduce a collection to a single value.

I suppose it's just so ... reductive, you know?

The resulting value can be anything you want. You can turn a list into a tree, or another list.

Bad example:

    reduce(lambda x,y: x+x.extend([y+2,y*2,y**2]), [1,2,3,4], [])

Reduces the list to another list three times as long.

It's a reduction in the sense of a transformation (also often seen in complexity theory), not in the "this makes this smaller" everyday usage that I think about first.

In the book "Simply Scheme", map is "every", filter is "keep", and reduce is "accumulate".

What about fold?

In rust iterators there's both fold (you supply the initial value) and reduce (it uses the first element as the initial value, doesn't work on empty iterators)

https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

It doesn't help that fold/reduce often have different orders depending on the ecosystem. Every few months when I have a reason to reach for `fold` in nutshell I forget that it has the next element as the first arg instead of the second, which is what I'm used to from Rust. I guess I should just be happy I don't need to specify which direction I want like in OCaml.

> Map and filter usually have only one arg and if they have 2, the 2nd is almost always a 0-based index. They look identical in most languages, even when Microsoft chooses to call them Select and Where.

I don't understand. Map takes input of type a and size n and returns output of type b and size n.

Filter takes input of type a and size n and returns output of type a and size ≤ n.

They look nothing alike?

I think their point was that map/filter _individually_ look identical in most languages, i.e. map looks the same across most languages, and filter looks the same across languages, not that map and filter look identical to each other in most languages.

Exactly, and sometimes you also get the indez as argument of the function. `reduce(acc,(acc,elem,idx)=>…)`

and in many case the accumulator is a tuple, and in many cases you need to know the length of the collection ( like average)

all in all, it’s a lot just to avoid a for loop.

More trivially, map and filter are operations that can be understood by what they do to individual elements, while reduce is a folding operation that is applied recursively on its own output. Much harder to think about.

An IDE can fix that

Meh, if you need a computer program to understand an API its a bad api.

APIs should make sense inherently. An IDE can band-aid a bad design, but that doesn't make it a good design.

There are lots of APIs where the order of argument isn't obvious, it doesn't mean they're bad designs

That's why I only program in punched cards. If you need a visual editor you're a bad programmer.

Luxury! All I need is a magnetic needle and a steady hand to flip the bits directly on the silicone.

excuse me, but real programmers use butterflies.

Reply on news.ycombinator.com