7 ms·

reduce package in Go

64 points by fosforsvenne 12y ago

falcolas 12y ago
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.
- kd0amg 12y ago
  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.
- hyperpape 12y ago
  This only handles functions of type a -> a -> a (https://github.com/robpike/filter/blob/master/reduce.go 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 https://news.ycombinator.com/item?id=9315721.
  - epidemian 12y ago
    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.
    - hyperpape 12y ago
      Ah, of course.
  - amscanne 12y ago
    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.
  - masklinn 12y ago
    And even with that, it still returns an interface{} which you need to cast.
  - falcolas 12y ago
    > 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.
- TheCoelacanth 12y ago
  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.
  - istvan__ 12y ago
    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.
  - falcolas 12y ago
    > 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.
    - TheCoelacanth 12y ago
      > 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.
      - falcolas 12y ago
        > 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.
- tome 12y ago
  > 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.
inglor 12y ago
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?
- bunderbunder 12y ago
  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.
  - drcode 12y ago
    That's the essence of Clojure's transducers http://clojure.org/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.
    - adrusi 12y ago
      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.
kyrra 12y ago
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 http://godoc.org/robpike.io/filter
pmahoney 12y ago
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).
- ryanthejuggler 12y ago
  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.
  - espadrine 12y ago
    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'])
EugeneOZ 12y ago
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"...
- falcolas 12y ago
  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).
  - EugeneOZ 12y ago
    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 https://github.com/robpike/filter/blob/master/apply.go#L19
- NateDad 12y ago
  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.
  - EugeneOZ 12y ago
    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.
fosforsvenne 12y ago
http://www.reddit.com/r/programmingcirclejerk/comments/317a7r/commander_rob_pike_tries_to_write_standard/cpyz11q http://www.reddit.com/r/programmingcirclejerk/comments/317a7...

64 points by fosforsvenne 12y ago

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.

kd0amg 12y ago
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.
hyperpape 12y ago
This only handles functions of type a -> a -> a (https://github.com/robpike/filter/blob/master/reduce.go 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 https://news.ycombinator.com/item?id=9315721.
- epidemian 12y ago
  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.
  - hyperpape 12y ago
    Ah, of course.
- amscanne 12y ago
  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.
- masklinn 12y ago
  And even with that, it still returns an interface{} which you need to cast.
- falcolas 12y ago
  > 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.
TheCoelacanth 12y ago
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.
- istvan__ 12y ago
  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.
- falcolas 12y ago
  > 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.
  - TheCoelacanth 12y ago
    > 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.
    - falcolas 12y ago
      > 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.
tome 12y ago
> 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.

inglor 12y ago

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?

bunderbunder 12y ago
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.
- drcode 12y ago
  That's the essence of Clojure's transducers http://clojure.org/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.
  - adrusi 12y ago
    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.

kyrra 12y ago

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 http://godoc.org/robpike.io/filter

pmahoney 12y ago

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).

ryanthejuggler 12y ago
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.
- espadrine 12y ago
  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'])

EugeneOZ 12y ago

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"...

falcolas 12y ago
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).
- EugeneOZ 12y ago
  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 https://github.com/robpike/filter/blob/master/apply.go#L19
NateDad 12y ago
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.
- EugeneOZ 12y ago
  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.

fosforsvenne 12y ago

http://www.reddit.com/r/programmingcirclejerk/comments/317a7r/commander_rob_pike_tries_to_write_standard/cpyz11q http://www.reddit.com/r/programmingcirclejerk/comments/317a7...