CODEWITHSUNDEEP
haskellrecursion
user485498
user485498

Reputation:

Finding mean of list in Haskell

I think my code to find the mean of a list (of integers) works ok, but has a problem. This is my code

listlen xs = if null xs
             then 0
             else 1 + (listlen (tail xs))

sumx xs = if null xs
         then 0
         else (head xs) + sumx (tail xs)

mean xs = if null xs
          then 0
          else (fromIntegral (sumx xs)) / (fromIntegral (listlen xs))

my mean function has to go through the list twice. Once to get the sum of the elements, and once to get the number of elements. Obviously this is not great.

I would like to know a more efficient way to do this (using elementary Haskell - this is a a question from Real World Haskell chapter 3.)

Upvotes: 0

Views: 4078

Answers (4)

AJF
AJF

Reputation: 11923

Now, there's an idea: a function that takes a bunch of monoids and applies each to a list, all at the same time. But that can come later!

I think what you'll need is a fold and a tuple for a good speed:

avg :: (Fractional a) => [a] -> a
avg []   = error "Cannot take average of empty list"
avg nums = let (sum,count) = foldr (\e (s,c) -> (s+e,c+1)) (0,0)  nums
            in sum / count

I've tried this out, and it's decently speedy in GHCi, though It may not be the best. I thought up a recursive method, too, though it requires a helper function:

avg :: (Fractional a) => [a] -> a
avg []     = error "Cannot take average of empty list"
avg nums = let (sum, count) = go nums
            in sum / count
    where go [] = (0,0)
          go (x:xs) = let (sum',count') =  go xs
                       in (sum' + x, count' + 1)

Then again, that's really slow. Painfully slow.

Looking at your solution, that's alright, but it's not really idiomatic Haskell. if statements within functions tend to work better as pattern matches, especially if the Eq class instance isn't defined for such-and-such a datatype. Furthermore, as my example illustrated, folds are beautiful! They allow Haskell to be lazy and therefore are faster. That's my feedback and my suggestion in response to your question.

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 152857

I like the other answers here. But I don't like that they write their recursion by hand. There are lots of ways to do this, but one handy one is to reuse the Monoid machinery we have in place.

Data.Monoid Data.Foldable> foldMap (\x -> (Sum x, Sum 1)) [15, 17, 19]
(Sum {getSum = 51}, Sum {getSum = 3})

The first part of the pair is the sum, and the second part is the length (computed as the sum of as many 1s as there are elements in the list). This is a quite general pattern: many statistics can actually be cast as monoids; and pairs of monoids are monoids; so you can compute as many statistics about a thing as you like in one pass using foldMap. You can see another example of this pattern in this question, which is where I got the idea.

Upvotes: 6

ErikR
ErikR

Reputation: 52039

What @simonzack is alluding to is that you should write listlen and sumx as folds.

Here is listlen written as a fold:

listlen :: [a] -> Int
listlen xs = go 0 xs                 -- 0 = initial value of accumulator
  where go s [] = s                  -- return accumulator
        go s (a:as) = go (s+1) as    -- compute the next value of the accumulator
                                     -- and recurse

Here s is an accumulator which is passed from one iteration of the helper function go to the next iteration. It is the value returned when the end of the list has been reached.

Writing sumx as a fold will look like:

sumx :: [a] -> Int
sumx xs = go 0 xs
  where go s [] = s
        go s (a:as) = go ... as      -- flll in the blank ...

The point is that given two folds you can always combine them so they are computed together.

lenAndSum :: [a] -> (Int,Int)
lenAndSum xs = go (0,0) xs             -- (0,0) = initial values of both accumulators
  where go (s1,s2) [] = (s1,s2)        -- return both accumulators at the end
        go (s1,s2) (a:as) = go ... as  -- left as an exercise

Now you have computed both functions with one traversal of the list.

Upvotes: 2

Amit Kumar Gupta
Amit Kumar Gupta

Reputation: 18567

Define a helper function that only goes through once:

lengthAndSum xs = if null xs
                  then (0,0)
                  else let (a,b) = lengthAndSum(tail xs) in (a + 1, b + head xs)

mean xs = let (a, b) = lengthAndSum xs in (fromIntegral b / fromIntegral a)

Upvotes: 1

Related Questions