Can "bind" do a reduce on a List monad?
functional-programming, monads
Solution
One of the defining properties of the bind operation is that the result is still "inside" the monad¹. So when you perform bind on a list, the result will again be a list. Since the reduce operation² often results in something other than a list, it can't be expressed in terms of the bind operation.
In addition to that the bind operation on lists (i.e. concatMap/flatMap) only looks at one element at a time and offers no way of reusing the result of previous steps. So even if we're okay with getting the result wrapped in a single-element list, there's no way to do it just with monad operations.
¹ So if you have a type that allows you to perform no operations on it except the ones defined by the monad type class, you can never "break out" of the monad. That's what makes the IO monad works.
² Which is called fold in Haskell and Scala by the way.
Problem
I know how to do the equivalent of Scheme's (or Python's) `map` and `filter` functions with the list monad using only the "bind" operation. Here's some Scala to illustrate: ``` scala> // map scala> List(1,2,3,4,5,6).flatMap {x => List(x * x)} res20: List[Int] = List(1, 4, 9, 16, 25, 36) scala> // filter scala> List(1,2,3,4,5,6).flatMap {x => if (x % 2 == 0) List() else List(x)} res21: List[Int] = List(1, 3, 5) ``` and the same thing in Haskell: ``` Prelude> -- map Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> [x * x]) [1,4,9,16,25,36] Prelude> -- filter Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> if (mod x 2 == 0) then [] else [x]) [1,3,5] ``` Scheme and Python also have a `reduce` function that's often grouped with `map` and `filter`. The `reduce` function combines the first two elements of a list using the supplied binary function, and then combines that result the the next element, and then so on. A common use to to compute the sum or product of a list of values. Here's some Python to illustrate: ``` >>> reduce(lambda x, y: x + y, [1,2,3,4,5,6]) 21 >>> (((((1+2)+3)+4)+5)+6) 21 ``` Is there any way to do the equivalent of this `reduce` using just the bind operation on a list monad? If bind can't do this on its own, what's the most "monadic" way to perform this operation? If possible, please limit/avoid the use of syntactic sugar (ie: `do` notation in Haskell or sequence comprehensions in Scala) when answering.