product of list iteratively

Question

I'm trying to learn coding in Haskell.

I started with an easy example "the product of a list".

product :: [Integer] -> Integer  
product []     = 1  
product (x:xs) = x * product xs

I finished this quickly. Another way is the product function in the API. (product List -> product)

I wonder if there is another iterative way to solve my problem?

Answer 1

You can use a fold:

product :: Num a => [a] -> a
product xs = foldl (*) 1 xs

This can also be done strictly with foldl' or foldr, the differences mostly are performance, but since you're just starting out I'll skip that lecture this time.

---

So what does a fold do? Let's start with the basic definition of foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

What this does is takes a function f :: a -> b -> a which takes an accumulator and an additional value, which is fed to it from the list of values. It iteratively applies this function, generating a new accumulator at each step, until it runs out of values in the list. For (*) it looks something like

> foldl (*) 1 [1, 2, 3, 4]
|   foldl (*) (1 * 1) [2, 3, 4] = foldl (*) 1 [2, 3, 4]
|   foldl (*) (1 * 2) [3, 4]    = foldl (*) 2 [3, 4]
|   foldl (*) (2 * 3) [4]       = foldl (*) 6 [4]
|   foldl (*) (6 * 4) []        = foldl (*) 24 []
|   24

I should add that this isn't exactly how it's performed in memory unless you use foldl', which is the strict version, but it's easier to follow this way.

Answer 2

Well in Haskell we don't have loops so iterative is relative, but here's the "functional iteration approach"

 product = foldl' (*) 1

folds are the equivalent of loops in imperative languages. foldl' in particular is tail recursive and strict so it will run in constant space, similar to a loop.

If we were to write it explicitly

 product = go 1
   where go accum (x:xs) = go (accum * x) xs
         go accum _      = accum -- Subtle performances
                                 -- differences with strictness

This is still recursive, but will compile to similar assembly.