Simple apply/filter/reduce package in Go | Hacker News Reader

reduce package in Go

github.com

64 pointsfosforsvenne64 comments

I don't get why someone would rather write a for loop than use declarative data syntax. If I want to get the names of all administrators doing `users.Where(user => user.isAdmin()).Select(user => user.Name)` is so much nicer than using a for loop - or maybe he's suggesting we start writing FOR loops instead of SQL for our databases too?

In most languages, the for loop ends up being faster. Sometimes noticeably so. Me, I generally start with declarative syntax, but the profiler frequently tells me to go back and change it.

Being a systems programmer, wonder if it's easier for him to just use the for loop as a default. Performance demands are always high in systems programming (because there'll be a whole stack of additional software standing on top of your code and depending on it for performance), so one might end up needing to use for loops often enough that it's easier to just use them all the time for consistency's sake.

That's the essence of Clojure's transducers http://clojure.org/transducers

...they give you the declarative syntax of filter/reduce/etc but can have the same evaluation strategy as for loops, with comparable performance.

That's not why clojure has transducers. You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map.

There's nothing inherently slow about higher order collection functions, rust has them and they compile to the same machine code as the equivalent loop construct. Its just that most languages implement them on the wrong data structures. Functional languages implement them on lazy lists, which is good, but has overhead. A lot of languages implement them on arrays, which is bad because then it needs to process the whole array at once, and allocate all the memory, even though the next transformation in the pipeline doesn't need all that memory. Rust implements them on iterators, which have all the sane benefits as lazy lists, but fit better into a performance-focused imperative language.

.NET implements them on iterators, too, but that's not an inherently fast approach. .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item.

Those two function calls introduce an overhead that may be significant in a "tight loop", and that may not exist in a hand-coded for loop.

Perhaps .NET's optimizer is smart enough to get things down to a for loop equivalent in some cases, but in general I haven't seen much evidence of that happening.

> .NET iterators are objects that implement a specific interface, and iterating over them involves two function calls per element - one to move to the next item, and one to retrieve the current item.

Any optimizing compiler will inline those functions. "Avoid function calls for performance" hasn't been relevant optimization advice for at least a decade.

In particular - the Microsoft .NET JIT will gladly make them as fast as loops in most cases - there might be overhead involving closures but that's mostly taken care of.

A good optimizer can inline those functions, but that doesn't necessarily mean it will. .NET JIT is conservative in what it decides to inline. There's even a special hint you can use to ask it to be more aggressive about inlining a method. You can't necessarily apply that hint to every function, though. Anonymous ones, for example.

> A good optimizer can inline those functions, but that doesn't necessarily mean it will.

If the optimizer isn't choosing to inline where it is a performance win, it's not a good optimizer.

Especially for trivial functions like Current() and MoveNext(), which are pretty much the textbook example of functions where inlining really helps (not so much because of the function call overhead, but because it enables so many intraprocedural loop optimizations).

> You can use a mapping transducer to express map, but it's actually going to have slightly worse performance than regular map.

That's a strawman argument- Neither OP nor my comment made any mention of "map". This is a discussion about reduction and filtering. Yes, using transducers in a way that is silly like you suggest will produce disappointing results.

Bad example, but my point holds.

Transducers aren't performance improvers, they're an abstraction over the process of iteration. They actually degrade performance in the absence of a particularly smart inlining compiler.

> They actually degrade performance in the absence of a particularly smart inlining compiler.

So it sounds like you're saying that iterators in Rust are faster than transducer-based filter/reduce.

I think it's clear that my original point was that transducer-based filter/reduce is faster than lazy-list based filter/reduce, and comparable in performance to a for loop. (in that lazy-list operations are MUCH MUCH slower in most cases for filter reduce operations than the latter two approaches)

I'm not sure what languages you are referring to, but Rust and D's iterator methods compile to the same code that you would write if you were using raw loops.

> In most languages, the for loop ends up being faster. Sometimes noticeably so. Me, I generally start with declarative syntax, but the profiler frequently tells me to go back and change it.

The optimization techniques to make higher-order functions compile down into the same code as a for loop are well-known. All you have to do is inline, constant propagate, and maybe SROA. Every optimizing compiler I know of, even JavaScript, has no problem doing this.

FWIW, PyPy has a hard time with this since Python's iterators are really heavyweight.

It's easy to dismiss an opinion but that doesn't mean it's wrong. For example, if you like filter/reduce you may criticize languages that don't encourage it (Go, Python, etc). But often this leads to copying ideas from one language resulting in code that's hard to maintain in another language which encourages different ways of expressing the same logic.

filter and reduce are both builtins in Python and I see nothing discouraging anyone from taking full advantage of them.

In Python 3 reduce was removed and you'd have to use functools.reduce. Similarly lambda functions are a bit of a mistake, in Guido's opinion, as well as his preference to use list comprehensions over filter(). I don't expect to see more functional programming constructs anytime soon in Python. That being said, list comprehensions work quite well in Haskell, Python, etc.

GvR discourages them if that's a strong enough reason for you :)

its not, actually. he seems to discourage them on the grounds that a list comprehension would be better. however, that's just alternate syntax for a logically equivalent operation. personally, I use whichever one is more clear to me based on context. I appreciate having the option. Maybe you say that's un-Pythonic because "there should be just one way to do things", but I'm not particularly dogmatic and not persuaded by that.

List comprehension produces a different output than reduce (since reduce does not have to produce a list). Reduce and for loops are better compared.

For loops make the logic occurring on each operator explicit and in the current frame of reference, as opposed to reduce, which splits the logic from the point of operation.

Also, when reduce is used to produce an artifact similar to a list comprehension: the list comprehension is going to be better optimized, more comprehensible for many programmers, and with two character changes can be turned into a generator instead of a memory-heavy list.

http://www.artima.com/weblogs/viewpost.jsp?thread=98196

http://python-history.blogspot.com/2009/04/origins-of-python...

Python is a bad example since it has declarative data manipulation syntax. You'd use a comprehension and not a for loop which is practically the same thing in my opinion.

Debugging. Try debugging a Select/Where stream in C#; it is a PITA. I often find myself unwinding my list comprehensions into for loops because I need to debug.

There is a reason Haskell's type system has to be so strong :)

I was pretty confused by this post for a minute until I remembered I've been on VS2015 since the first preview release. This problem is greatly reduced there.

I saw that in June, and I'm interested in how effective it is, and what the usability characteristics are (it looked complex at the time, but it was an early demo). But going from 2010 to 2013 was a painful, and I don't want to throw this in a VM, so I'll just wait for RTM.

2013 to 2015 is a much smaller jump. Unless you are doing weirder things than me (and I mean, that's kind of hard!), I'd bet you'd be party. YMMV, of course.

I use a plugin that makes curly braces very small, so that my C# code looks more like Python. it seems to break on every version upgrade, and I can't stand normal sized C# curly braces anymore.

I'd honestly be surprised if that broke this time around. Every extension I've tried in VS2015 worked fine. Some I had to fight with (VSIX manifests with too-restrictive versions), but it's mostly just drop-in-and-go.

They do run side-by-side just fine, too, FWIW.

Super useful. Debugging Select/Where is now as easy as debugging for loops. Also remember that the pain point for debugging is the laziness and not the declarative syntax and you can just use `.ToList()` to get rid of it.

Wasn't one of Pike's earliest published whitepapers basically stating that "most of what you need is binary trees, linked lists and hashes" when it came to data structures/algorithms? (Probably add CSP to that list, given his prior work)

So I'd dare to say he's a bit of a minimalist. Fanboys and fellow travelers aside, one of the few persons with a similar point of view that I can think of would be Niklaus Wirth.

But that's the luxury that research and academia offer to you, if your problems can be approach from a tabula rasa view, you can tailor your tools to be similary pure (his "pure" obviously not being of the mathematical/functional persuasion).

I mean, there's no solid reason why we have several different kinds of screwdrivers. But that doesn't help you when you have to assemble your IKEA Wöbsörwös furniture to earn your living.

The letter W isn't used in Swedish except in proper names and the occasional loanword.

And just when I felt so smart about using "ö" and not "ø" for fake furniture…

Actually, I both noticed and appreciated that :). And a lot of IKEA product names are just first names anyway, so it _was_ overly pedantic.

Because for loops are special forms to the compiler and don't require general parametric polymorphism to be implemented in the language. Parametric polymorphism adds a lot of complexity to the language, so I guess the go team has decided to just not have it in the language. I'm not sure I agree with that decision, but it is true that parametric polymorphism isn't all that useful for the types of programs go is usually used for.

You don't want to use this implementation because it uses reflection, which makes it slow and means the compiler can't catch your errors.

    var admins = users.Where(user => user.isAdmin()).Select(user => user.Name)

    var admins []string
    for _, user := range users {
        if user.IsAdmin() {
            admins = append(admins, user.Name)
        }
    }

So, at the end of the day, these two pieces of code do the exact same thing, and have mostly the exact same meaning. I read them almost identically...

Make a list of admins. iterate through the users, if the user is an admin, append its name to the list of admins.

The unrolled version is a lot easier to modify later. What if you decide that each of these admin users should have a star next to their name? For the go code, you just add one line:

    var admins []string
    for _, user := range users {
        if user.IsAdmin() {
            admins = append(admins, user.Name)
            user.Name = user.Name + "*"
        }
    }

for the C# code, you either have to write a second LINQ query (and now you're iterating the list twice unnecessarily), or you have to unroll it into a normal loop.

So now you've added complexity to the language that is only really good for saving carriage returns, and it makes your code harder to maintain. Sure, it's pretty and interesting from a programming theory POV... but at the end of the day, I don't get paid to write pretty or interesting code. I do get paid to write maintainable code.

I humbly disagree - in the C# code I can pass an IQueryable and reuse the same code to make an SQL query, or a RavenDB query, or an XML query and it works just the same - there is a unified way to access data in the language.

As for your query:

``` var admins = users.Where(u => u.IsAdmin()).Select(u => u.Name); var stars = admins.Select(name => name + "*"); ```

Like you said, you don't get paid per line feed - it's ok to have multiple lines and you can keep the nice syntax. It's ok to not like complicated code - no one likes complicated code - which is why I don't like for loops - I don't _care_ how something is iterated I just want to map every object.

Well, so, that's actually not doing the right thing. You just changed the names in the list of strings that holds admin names, but not the names on the user objects themselves.

Even if the first half were returning the users themselves to the admins list, you're still iterating over the list twice.

This is yet another reason why the for loop is good - it makes it more clear what is actually going on. This is your code in for loops:

    var admins []string
    for _, u := range users {
        if u.IsAdmin() {
            admins = append(admins, u.Name)
        }
    }
    
    for i := range admins {
        admins[i] = admins[i] + "*"
    }

The problem with the fancy syntax is that it makes it too easy to write suboptimal code that you'd never write if you were writing plain old for loops, like the above.

> you're still iterating over the list twice

There is nothing about higher-order operations that would require developers to implement xs.map(...).map(...).map(...) or xs.Select(...).Select(...).Select(...) or whatever as multiple traversals over the data structure.

> The problem with the fancy syntax is that it makes it too easy to write suboptimal code that you'd never write if you were writing plain old for loops, like the above.

Maybe Google should just invest in hiring better people? I know it's getting increasingly harder to find people who still haven't evolved from the 1960ies mindset, but still ...

I'm not familiar specifically with LINQ but in most languages that implement map/reduce/filter operations, the "*" requirement could be clearly expressed using a map.

What happens when you need an alphabetical list of admins who have logged in during the last week? The for-loop approach becomes progressively more and more cluttered with implementation cruft, while a declarative approach just adds a filter and a sort.

And, to be frank, even the example you present is clearer to me in LINQ than in Go, and I am much more familiar with Go.

This isn't "reduce" as I know it.

It requires the user function return the same data type as contained by the slice. Furthermore, for a slice of size 1, it simply returns that single element.

  case 1:
  	return in.Index(0)

  ...

  if !goodFunc(fn, elemType, elemType, elemType) { ... panic }

So I could not, for example, reduce a slice of numbers into a struct of (min,max,mean).

The "official" way to do this is map, then reduce. The way reduce is meant to be used exactly matches this implementation.

Consider that you have a large quantity of numbers that you want to get the min, max, mean for. If you write something like the following:

    function minMaxMean(list) {
      return list.reduce(function(lastState, n) {
        var min = lastState.min,
            max = lastState.max,
            sum = lastState.sum,
            count = lastState.count;
        if(n < min) min = n;
        if(n > max) max = n;
        sum += n;
        count += 1;
        return {
          min: min,
          max: max,
          sum: sum,
          count: count
        }
      }, {min: Infinity, max: -Infinity, sum: 0, count: 0});
    }

...then you're assuming that the reduce function will run once, over a single list of numbers, in order from left to right. However, if you implement it as the following:

    function minMaxMean(list) {
      return list.map(function(n){
        return {
          min: n,
          max: n,
          sum: n,
          count: 1
        }
      }).reduce(function(a, b) {
        return {
          min: (a.min < b.min ? a.min : b.min),
          max: (a.max > b.max ? a.max : b.max),
          sum: a.sum + b.sum,
          count: a.count + b.count
        }
      });
    }

...then you can distribute this out across multiple threads/machines/etc, update it when new data comes in, reduce in any order.

There are many cases of elegantly using reduce() with a different return type than the list's item type.

Here is a JS function which computes the combined length of all strings in a list:

    stringsLen = (strings) => strings.reduce((acc, item) => acc += item.length, 0);
    
    stringsLen(['hello', 'world'])  //> 10

Sure, you can argue that this works, but it misses the point.

    stringsLen = (strings) => strings.map(s => s.length).reduce((acc, n) => acc += n, 0);
    
     stringsLen(['hello', 'world'])

Not with this specific implementation. However, it would be fairly trivial to substitute one of the elemType arguments with the type of `zero`.

Perhaps a pull request is in order?

With so many "interface{}"s Go looks more like weakly-typed.

"Apply takes a slice of type []T and a function of type func(T) T"

And after that golang.org docs are saying "We don't feel an urgency for them" about generics"...

Looks are deceiving. `interface{}` != `void *`. The value inside the `interface{}` box is still strongly typed, it's just boxed to make function interfaces simpler (given Go's lack of generics).

I don't want to say interface{}=void (at least while type assertion isn't used). But please read comment to Apply function [0] and tell me you don't see usual generics record.

[0] https://github.com/robpike/filter/blob/master/apply.go#L19

He does say "don't do this" and that's exactly one of the reasons why... because you lose compile-time type safety (it's still type safe at runtime, though). All the reflection is bound to be slow, as well.

My point is not to say "look, this code is dirty". My point is "look, he use generics in comments, in his mind, so it's natural thing and obviously should exist in Go". Only this.

To see the docs, use godoc.org, copy/paste the full URL for the repo into the search, and you get this[0]. Nicer way to see the API for the package.

[0] http://godoc.org/robpike.io/filter

But you can't write generic functions in Go!

Oh, wait. He just did.

As a caveat to my exasperated sarcasm, I do realize he's using reflection to identify and type the data at runtime, as opposed to compile time as with C++ templating, but this is kind of generalization is still quite useful when writing general purpose library code.

Personally, I'd not be inclined to use this either, the number of times I've actually had to write generic code using reflect in my time writing Go could be counted with one finger.

I do appreciate that it's there, however, since it is what allows the JSON library to do its magic.

Yeah, my immediate reaction was, "all that work manually doing what a type checker should have done for you?" Given that, it seems sensible enough to just inline and type-specialize the 5 or so lines you actually care about.

This only handles functions of type a -> a -> a (https://github.com/robpike/filter/blob/master/reduce.go), whereas a generic reduce takes functions of type a -> a -> b. So this is certainly not proof that you can write generics in go. See also pmahoney's comment in this thread: https://news.ycombinator.com/item?id=9315721.

Minor nitpick: a generic reduce should take functions of type a -> b -> a, where a is the type of the reduced values, and b is the type of the elements in the sequence to be reduced.

Ah, of course.

You could very easily relax that constraint by changing a couple of lines. Rob Pike has simply chosen the classic MapReduce form.

I'm not sure why you would need "proof" that generics are possible in Go. You have reflection and type assertions, and their capabilities are well documented. Does it give you generics? All depends on your definition of generics.

And even with that, it still returns an interface{} which you need to cast.

> This only handles functions of type a -> a -> a

So, since his toy code was explicitly written to accept the same type for both parameters of the function, you are unable to see how it could be modified to accept a different type signature for the reduce function? It looks to me like a fairly trivial change to get the type of argument `zero`, and use that as one of the parameters to the reduce function.

As for pmahoney's comment, looks like there's a bug. Perhaps he should file a bug report, or pull request.

It's 30 lines long (the equivalent in Haskell would be 1 fairly simple line of code). Type errors are detected at runtime instead of at compile type, and it's not as generic as actual reduce.

> It's 30 lines long (the equivalent in Haskell would be 1 fairly simple line of code).

Bully for Haskell. Language N can always do it better/faster/shorter than language M. What matters in this case is that it can be done, in a type safe way.

> Type errors are detected at runtime instead of at compile type

Already mentioned that.

> it's not as generic as actual reduce.

It's toy code, forgive him for not writing it perfectly. If it can accept one ambiguous type throughout, there's no reason it could not accept multiple types throughout.

> If it can accept one ambiguous type throughout, there's no reason it could not accept multiple types throughout.

I'm sure it could, but only at the expense of ballooning to an even more disproportionate length.

> I'm sure it could, but only at the expense of ballooning to an even more disproportionate length.

If you looked at the code, you would see that it could be done in zero additional lines of code if he wanted, or in one if he wanted to be explicit.

    if !goodFunc(fn, elemType, zero.Type().Elem(), elemType) {
        str := elemType.String()
        panic("apply: function must be of type func(" + str + ", " + zero.Type().Elem().String() + ") " + str)
    }

There would be a few other inline changes to add `zero` to the function calls (and fix the 0/1 cases), but they are all pretty trivial.

If we want to be pedantic about it, the goodFunc call is not even technically required, it just makes the error output a bit better.

In fairness not only in Haskell. I think Go is just not a great choice for this sort of effort. On Haskell though, languages are not a single dimension thing, so it is very easy to say that X is better in Y and leave out all the other dimensions, but that just oversimplification of the problem.

> But you can't write generic functions in Go!

Did anyone claim this? What I heard was that you can't write generic data structures (and I guess that really means type-checked, parameterized data structures). I don't know though, I've never used Go.

Reply on news.ycombinator.com