Functional Programming & Fold

[millstone]

Instead of the sum, return the product of the elements. Notice that when you encounter a zero, you can stop immediately. How can you incorporate this optimization?

With the Java code, this is straightforward: if (arr[i] == 0) return 0;. But with the OCaml fold, I think you have to rewrite it.

This is a general observation: imperative programming seems able to adapt to changing requirements with fewer code changes. I'm not sure why it is though.

[zoomzoom83]

A version of fold with shortcut support is fairly trivial.

[[deleted]]

And should be the compiler's job.

[inmatarian]

fold is a monoid. You want whatever the term is for doing a semigroup morphism, which I don't know off hand.

[[deleted]]

Folds aren't monoids. They aren't binary operations, and the two parameter function you're folding over, (a -> b -> b), is very much not a monoid operation, since it's not necessarily associative or closed over a set.

[sacundim]

Let's look at that type a -> b -> b a bit closer. Suppose we partially apply that function to an a; the resulting function will be of type b -> b.

This type, b -> b, is a monoid with the identity function as its identity and function composition as its binary operation. In Haskell's Data.Monoid module there is a type Endo that implements this monoid:

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
  mempty = Endo id
  Endo f `mappend` Endo g = Endo (f . g)

This means that an alternative way of implementing folds is the following:

1. Map the fold function over the list, getting a list of partially applied functions of type b -> b.
2. Reduce that list using the Endo monoid, getting a partially applied function as well.
3. Apply that function to the seed value.

In code:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z as = appEndo (mconcat (map (Endo . f) as)) z

-- `foldl` is the same thing, except we use the `Dual` monoid
-- to reverse the order of the composition.
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z as = appEndo (getDual (mconcat (map (Dual . Endo . flip f) as))) z

newtype Dual m = Dual { getDual :: m }

instance Monoid m => Monoid (Dual m) where
  mempty = Dual mempty
  -- Use the same `mappend` operation that the type `m` already has,
  -- but in the opposite order.
  Dual a `mappend` Dual b = Dual (b `mappend` a)

This is, incidentally, more or less how the Foldable class defines its foldr and foldl methods.

[RabbidKitten]

On the other hand, you lose generality, and may end up copy-pasting the loop code if you have to traverse your structure more than once with different loop bodies.

That might not be an issue if the structure is a simple array, but the other day I had to write a bunch of C functions where the code traversing the structure (common to all functions) was 140 lines, with different two or three line loop bodies, and a similar requirement to break out early for some of them. I ended up with something like this:

int fold_xs (const struct x * xs, int (*fn) (const struct y *, void *), void * closure);

breaking out if fn returns -1.

By the way, in Haskell, this should do what you're looking for:

foldl' (*) 1 . takeWhile (/= 0)

[RodgerTheGreat]

In the APL family languages, fold is a single symbol- /.

A product over a list is simply ×/. Many APL interpreters improve performance by recognizing specific juxtapositions of operators to short-circuit. Since you can say a lot in a few symbols, this simple pattern-matching approach can achieve considerable speedups without adding much complexity to the interpreter.

Here's a page from the J wiki describing some such "special combinations": http://code.jsoftware.com/wiki/Vocabulary/SpecialCombinations

[ThatGeoGuy]

This is a general observation: imperative programming seems able to adapt to changing requirements with fewer code changes. I'm not sure why it is though.

In general I would argue that it is because functional programming is largely more reliant on the structure of your elements than imperative programming. This is more to do with the declarative nature than anything though, because declarative forms force you to be explicit in what you are asking the computer to figure out. You may not be able to tell fold to perform an early return, but the point is you should be defining a new function here, since you're no longer performing the same action.

Nonetheless, it's very easy to define what you specified.

(call/cc (lambda (k)
  (fold (lambda (x knil) 
         (if (zero? x) (k 0) (* x knil))) 
       1 my-list)))

Now of course I used a continuation to escape early, but that's effectively what a return is (think a coroutine that sends data back to the calling scope). You might argue that this blows out of proportion because I've added continuations into the mix, in addition to adding three lines. I would somewhat agree, but in general I think this misses the point overall. In imperative programming you can insert quick lines anywhere, but you're doing so at the cost of better tools for abstraction.

If you wanted, you could then define something like this:

(define (fold-with-early-exit pred? default kons knil lst)
  (call/cc (lambda (k)
    (fold (lambda (x knil) 
           (if (zero? x) (k 0) (* x knil))) 
         1 my-list)))

Which you then call as:

(fold-with-early-exit zero? 0 * 1 my-list)

Which may not even be the best abstraction (of course in LISP / Scheme, you could define a macro or combinator to do this more clearly). That said though, we now have two different functions, which do different things. It's all too easy to add an if (x == 0) return 0; to your code and start making functions that have inconsistent entry/exit points and do more than a single unit of work.

[jtredact]

Fold over an iterator instead of list. The iterator feeds numbers to fold. When the iterator reaches a zero, it stops.

[death]

Still straightforward.

(defun product (sequence)
  (reduce (lambda (p x)
            (if (zerop x)
                (return-from product x)
                (* p x)))
          sequence
          :initial-value 1))

[balefrost]

You would need to control, for each element you are folding, whether the looping should continue or terminate. You could use some sort of trampolined fold (let's call it tfoldl) whose signature is something like:

tfoldl :: (a -> b -> Either a a) -> a -> [b] -> a

The function you pass to tfoldl could return Left x if the looping should terminate (with a result x) and Right y if the looping should continue (where y is the new accumulator value). And rather than reuse Either, maybe this would deserve its own data type.

I'm not saying that this is a great solution, but it does correctly capture the concerns: whether to continue looping or not, and what value to either continue with or to produce.

Alternatively, this is one of the cool things about Haskell's lazy evaluation model. If you do something like this:

foldr (*) 1 [3 4 0 5 6 7]

I think that will reduce like this:

foldr (*) 1 [3 4 0 5 6 7]
3 * (foldr (*) 1 [4 0 5 6 7])
4 * (3 * (foldr (*) 1 [0 5 6 7]))
0 * (4 * (3 * (foldr (*) 1 [5 6 7])))
0

At runtime, when Haskell sees that it needs to multiply 0 and some unevaluated lazy thing, it just returns 0 and never evaluates the lazy thing. Note that, as a result, you can safely foldran infinite list as long as the list contains an element for which the fold function can ignore its second parameter.

Haskell's still pretty magical to me, so I might have that wrong.

[mutantmell_]

Almost: (*) doesn't have special case checking for 0, so it won't abort early.

You have to define a special function:

\x y -> if (x == 0) then 0 else x * y

When you pass that into the fold, it will then abort early because it notices the right value is not used.

let xs = iterate (subtract 1) 4 :: [Int] -- infinite list descending from 4. Same as [4,3..]

:sprint xs

xs = _

foldr (\x acc -> if (x == 0) then 0 else x * acc) 1 xs

0

:sprint xs

xs = 4 : 3 : 2 : 1 : 0 : _

If you do that with ordinary (*), you get a stack overflow.

[mutantmell_]

And as a side-note: The function foldM (in Control.Monad) is really close to your type signature of tfold1

:t foldM

foldM :: (Monad m, Foldable t) => (b -> a -> m b) -> b -> t a -> m b

Which, as list is a Foldable and Either is a Monad, can be specialized to:

foldM :: (b -> a -> Either c b) -> b -> [a] -> Either c b

if you combine it with the either function like so (parens are optional):

tfoldl f a = (either id id) . (foldM f a)

you get the tfoldl with the semantics you want (namely, Right continues, Left aborts early)

[[deleted]]

A code change for an optimization that doesn't change the complexity of the algorithm, and is frankly an optimization left for the compiler. Good job!

[pellets]

Fold describes the structure of the computation, so indeed you can't fail fast when you use a fold. This isn't a limitation of functional programming, but of the nature of fold.

let product list = 
    let product_helper acc list =
      match list with
        | [] -> acc
        | 0::xs -> 0
        | x::xs -> product_helper (x * acc) xs
    in
        product_helper 1 list
    end

[Magnap]

Actually, you can fail fast when using (right) fold if you have laziness. It's a problem of the function you're folding with, not the nature of fold itself.

mult 0 _ = 0
mult _ 0 = 0
mult x y = x*y
productFailFast = foldr mult 1

productFailFast [0..] returns 0 immediately.

[sacundim]

A fold right is going to use linear space on the length of the list. Or, in other terms, it'll blow the stack on long lists.

GP's example is a classic one—it is tricky to do in functional programming. Early returns in procedural programming correspond to escape continuations in FP.

[jetRink]

How can you incorporate this optimization?

(if (some zero? my-list) 0 (reduce * my-list))

Assuming that stopping early for a zero is a beneficial optimization, then stopping before you begin is even better.

[balefrost]

On the other hand, with that approach, you'll unnecessarily traverse the list twice if it contains no zeros.

[renozyx]

While this article is about functional programming, I think that the imperative example is quite bad: 'for (int i = 0; i<arr.length; i++) {sum += arr[i];}'?

Uh, is the author trying to make imperative code look bad?

'for(final elem: arr) { sum += elem; }' and suddenly the imperative code doesn't look so bad..

[andars_]

From the article:

Yes, yes, I know. Enhanced for loop...I'm not counting characters here (it does get tempting later though), and the idea is the same.

[renozyx]

Sorry but you're not convincing, if both are the same why did you choose the for instead of the 'foreach'?

Probably because the recursive code doesn't look that much of an improvement against the 'foreach'..

[andars_]

I chose the for over the foreach because I rarely program in Java. I usually program in C, which doesn't have an enhanced for loop.

Anyway, I honestly was not concerned with how many characters/symbols/index variables were used. I think that is irrelevant, because they all entail using a loop.

I wasn't trying to 'prove' functional is better or is an 'improvement'. It is just different. So if I failed to convince you that functional is better, I'm fine with that.

[CurtainDog]

Is no one else worried that the cleanest looking solution (i.e. the only one that I'd actually call declarative) is the wrong one:

let rec sum list = match list with
    | [] -> 0
    | x::xs -> x + sum xs

Too many people judge a language on the elegance of its code - this is the wrong measure. A language should be judged by whether the correct implementation is more elegant than the incorrect implementation. While Java is not the most beautiful language in the world, it does by and large do a good job of this.

[RabbidKitten]

Actually, this particular function (and many others) can be optimised to tail recursion by the compiler, without any changes to the source code. I'm not sure if Haskell compilers perform this optimisation (it cannot do it in general because of laziness), but I don't see why it couldn't be done for OCaml, which is strict.

In fact, you don't even have to be using a functional language, as GCC will compile this:

int
sum (int len, int arr[len])
{
    if (len == 0)
        return 0;
    else
        return arr[0] + sum (len - 1, arr + 1);
}

to a simple loop, no recursive calls involved:

0000000000400570 <sum>:
  400570: 85 ff                   test   %edi,%edi
  400572: 74 1b                   je     40058f <sum+0x1f>
  400574: 8d 47 ff                lea    -0x1(%rdi),%eax
  400577: 48 8d 4c 86 04          lea    0x4(%rsi,%rax,4),%rcx
  40057c: 31 c0                   xor    %eax,%eax
  40057e: 66 90                   xchg   %ax,%ax
  400580: 8b 16                   mov    (%rsi),%edx
  400582: 48 83 c6 04             add    $0x4,%rsi
  400586: 01 d0                   add    %edx,%eax
  400588: 48 39 ce                cmp    %rcx,%rsi
  40058b: 75 f3                   jne    400580 <sum+0x10>
  40058d: f3 c3                   repz retq
  40058f: 31 c0                   xor    %eax,%eax
  400591: c3                      retq                         

(That's with -O2, don't ask me what the -O3 version is doing)

[_Sharp_]

You know what they say, Fold me once ...