5 ms·

If add is taken to be any associative operation of a monoid, then Python's sum is merely equivalent to Haskell's mconcat, which is not nearly as general as

If __add__ is taken to be any associative operation of a monoid, then Python's sum is merely equivalent to Haskell's mconcat, which is not nearly as general as reduce/foldl. Plus, unless you implement something akin to newtype wrappers for alternative monoid instances (hardly Pythonic), you're going to be restricted to a single foldable function for any given type. I think you were right the first time; removing reduce from Python is very lame.

andreasvc 14y ago
Don't worry, it has not been removed: http://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce http://docs.python.org/3/library/functools.html?highlight=re...
jewbacca 14y ago
> If __add__ is taken to be any associative operation of a monoid, then Python's sum is merely equivalent to Haskell's mconcat, which is not nearly as general as reduce/foldl I don't have the math to back this up, so please correct me if you know otherwise (and especially if you can demonstrate otherwise, though I know this being wrong is not contingent on that), but: I'm pretty sure `mconcat` with a `map` (or a list comprehension) is exactly as general as `fold`. > Plus, unless you implement something akin to newtype wrappers for alternative monoid instances (hardly Pythonic), you're going to be restricted to a single foldable function for any given type. Again, I know this isn't an argument and demonstrates shitty memory on my part, but a single solid example here would be key to me understanding this debate: What is an example of a type with more than 2 monoids on it, whose fold could not be cleanly expressed with a sum/product and a map/comprehension, which is not already included in the standard library (any/all/gcd/lcm/max/min)? [I suspect there either won't be an easy answer, or it will be so basic that I'll be brutally embarrassed... this is all kinda talking out of my ass, I have no exposure to category theory outside of reading haskell papers]
- tmhedberg 14y ago
  I don't know much category theory either; my argument is based solely on my knowledge of Haskell. Maybe I'm being obtuse, but I don't quite understand what you mean when you say "mconcat with a map". But to see why mconcat isn't as general as a fold, you need only to take a look at the types: mconcat :: Monoid a => [a] -> a foldl :: (a -> b -> a) -> a -> [b] -> a mconcat is constrained to only operating on monoidal types, whereas foldl has no such constraint. Likewise, mconcat must always yield a result of the same type as the list elements, while foldl is capable of accumulating a result of any type. mconcat can be implemented in terms of a fold, e.g. mconcat = foldl mappend mempty Such a partially applied foldl is obviously less general than an unapplied foldl, as its first 2 arguments are fixed. There is no way to implement foldl (or even foldl1) in terms of mconcat. There are plenty of uses for folds that don't involve monoids, and therefore can't be implemented with mconcat plus a Monoid instance. As a trivial example, take Prelude> foldl (/) 400 [4, 4, 5] 5.0 There is no "quotient monoid", because a monoid is defined as a type with an associative binary operation and an identity element with respect to that operation. Division has a right identity (1), but it isn't associative, so it can't be used as a monoidal operation like addition and multiplication can. But foldl still works fine in this case, as the above example shows, where mconcat would not (unless you write a Monoid instance that violates the monoid laws). Associativity notwithstanding, it's also not adequate to say that 2 monoid instances should be enough for any type. Maybe that is true in some or even most cases, but it is certainly not true in the general case. Haskell has newtypes to mitigate this problem, essentially enabling an arbitrary number of Monoid instances to be defined per type, but Python only lets you write one __add__ and one __mul__ for a given class. On top of that, I don't believe Python even has a product function that folds __mul__ over a list the way sum folds __add__, so really the limit is 1, not 2. Anyway it's all moot because, as someone pointed out, reduce hasn't been removed from Python, just relegated to a library. :) I think it's a fundamental enough operation that it should be built in, but obviously Guido and I have differing opinions on FP.
  - jewbacca 14y ago
    On the off chance you ever check this again, byorgey discusses this here: http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-monoids/ http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-mon...

If __add__ is taken to be any associative operation of a monoid, then Python's sum is merely equivalent to Haskell's mconcat, which is not nearly as general as

andreasvc 14y ago

Don't worry, it has not been removed: http://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce http://docs.python.org/3/library/functools.html?highlight=re...

jewbacca 14y ago

> If __add__ is taken to be any associative operation of a monoid, then Python's sum is merely equivalent to Haskell's mconcat, which is not nearly as general as reduce/foldl I don't have the math to back this up, so please correct me if you know otherwise (and especially if you can demonstrate otherwise, though I know this being wrong is not contingent on that), but: I'm pretty sure `mconcat` with a `map` (or a list comprehension) is exactly as general as `fold`. > Plus, unless you implement something akin to newtype wrappers for alternative monoid instances (hardly Pythonic), you're going to be restricted to a single foldable function for any given type. Again, I know this isn't an argument and demonstrates shitty memory on my part, but a single solid example here would be key to me understanding this debate: What is an example of a type with more than 2 monoids on it, whose fold could not be cleanly expressed with a sum/product and a map/comprehension, which is not already included in the standard library (any/all/gcd/lcm/max/min)? [I suspect there either won't be an easy answer, or it will be so basic that I'll be brutally embarrassed... this is all kinda talking out of my ass, I have no exposure to category theory outside of reading haskell papers]

tmhedberg 14y ago
I don't know much category theory either; my argument is based solely on my knowledge of Haskell. Maybe I'm being obtuse, but I don't quite understand what you mean when you say "mconcat with a map". But to see why mconcat isn't as general as a fold, you need only to take a look at the types: mconcat :: Monoid a => [a] -> a foldl :: (a -> b -> a) -> a -> [b] -> a mconcat is constrained to only operating on monoidal types, whereas foldl has no such constraint. Likewise, mconcat must always yield a result of the same type as the list elements, while foldl is capable of accumulating a result of any type. mconcat can be implemented in terms of a fold, e.g. mconcat = foldl mappend mempty Such a partially applied foldl is obviously less general than an unapplied foldl, as its first 2 arguments are fixed. There is no way to implement foldl (or even foldl1) in terms of mconcat. There are plenty of uses for folds that don't involve monoids, and therefore can't be implemented with mconcat plus a Monoid instance. As a trivial example, take Prelude> foldl (/) 400 [4, 4, 5] 5.0 There is no "quotient monoid", because a monoid is defined as a type with an associative binary operation and an identity element with respect to that operation. Division has a right identity (1), but it isn't associative, so it can't be used as a monoidal operation like addition and multiplication can. But foldl still works fine in this case, as the above example shows, where mconcat would not (unless you write a Monoid instance that violates the monoid laws). Associativity notwithstanding, it's also not adequate to say that 2 monoid instances should be enough for any type. Maybe that is true in some or even most cases, but it is certainly not true in the general case. Haskell has newtypes to mitigate this problem, essentially enabling an arbitrary number of Monoid instances to be defined per type, but Python only lets you write one __add__ and one __mul__ for a given class. On top of that, I don't believe Python even has a product function that folds __mul__ over a list the way sum folds __add__, so really the limit is 1, not 2. Anyway it's all moot because, as someone pointed out, reduce hasn't been removed from Python, just relegated to a library. :) I think it's a fundamental enough operation that it should be built in, but obviously Guido and I have differing opinions on FP.
- jewbacca 14y ago
  On the off chance you ever check this again, byorgey discusses this here: http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-monoids/ http://byorgey.wordpress.com/2012/11/05/foldr-is-made-of-mon...