Haskell learning exercise gives strange results_问答_开发者

this is the question:

"Wr开发者_运维问答ite a function that computes the mean of a list, i.e. the sum of all elements in the list divided by its length. (You may need to use the fromIntegral function to convert the length of the list from an integer into a floating point number.)"

first i tried this:

mean :: [Double] -> Double
mean []     = 0
mean (x:xs) = (x + mean xs) / (1 + mean xs)

but it give me strange results, for example, when i use it like that:

mean [2,4,6]

it give me the result: 1.41176

where it should be: 4

why?

i tried another thing:

mean :: [Double] -> Double  
mean list = (summ list) / (count list)  
    where count []     = 0  
          count (x:xs) = 1 + count xs  
          summ []      = 0  
          summ (x:xs)  = x + summ xs

but i have an error when i tried to load the file into GHC.

the error is:

parse error on input 'count'  
Failed, modules loaded: none

again, what am i doing wrong?

at last, i tried this one (that succeeded):

mean :: [Double] -> Double

count []     = 0
count (x:xs) = 1 + count xs
summ  []     = 0
summ (x:xs)  = x + summ xs
mean list    = summ list / count list

it's the same as the above one (with the 'where' keyword), but it succeed only here, and not in the above one.

why?

thanks a lot.

p.s.

i'm learning from the book -- Real World Haskell and the exercise is from here -- (roll it down :-))

thanks to you all. it's a strange thing. the second example also work for me too when i copied it from here and tested it. i don't know why it didn't work for me yesterday :-)

but i still don't understand why the first one doesn't work. i think it should be like that


(2 + mean [4,6]) / (1 + mean [4,6])
(4 + mean [6  ]) / (1 + mean [  6])
(6 + mean [   ]) / (1 + mean [   ])

so now it is like that


(6 +  0        )    / (1 +  0          )  -- last recursion
(4 + (6 + 0)   )    / (1 + (1 + 0)     )
(2 + (4 + (6 + 0))) / (1 + (1 + (1 + 0))

so now it should be: 12 / 3

isn't it?

what i don't understand?

thank you :-).

You get the wrong answers for your first attempt, because you use an incorrect formula. Garbage in, garbage out. (Other people have covered this.)
You are probably getting a parse error because some lines are using spaces and others are using tabs. Or you are using all tabs, but with a non-standard tab width.
No indentation is used or required here, so the spaces -v- tabs issue doesn't arise.

Your first attempt evaluates like so:

6 / 1
4 + 6 / 1 + 6
2 + (10/7) / 1 + (10/7)

which isn't what you wanted.

The second attempt is fine.

Correct:

import Data.List (foldl')
mean :: Fractional a => [a] -> a
mean = uncurry (/) . foldl' (\(s, n) x -> (s + x, n + 1)) (0, 0)

mean [2,4,6] = uncurry (/) $ foldl' (...) (0, 0) [2,4,6]
             = uncurry (/) $ foldl' (...) (2, 1) [4,6]
             = uncurry (/) $ foldl' (...) (6, 2) [6]
             = uncurry (/) $ foldl' (...) (12, 3) []
             = uncurry (/) (12, 3)
             = 12 / 3
             = 4

Incorrect:

mean [] = 0
mean (x:xs) = (x + mean xs) / (1 + mean xs)

mean [6] = mean (6 : [])
         = (6 + mean []) / (1 + mean [])
         = (6 + 0) / (1 + 0)
         = 6
mean [4,6] = mean (4 : [6])
           = (4 + mean [6]) / (1 + mean [6])
           = (4 + 6) / (1 + 6)
           = 10/7
mean [2,4,6] = mean (2 : [4,6])
             = (2 + mean [4,6]) + (1 + mean [4,6])
             = (2 + 10/7) / (1 + 10/7)
             = 24/17

Say we define

naivemean l = sum l / fromIntegral (length l)

It has a couple of serious limitations. First, the definition does not cover lists of Int:

*Main> naivemean ([1] :: [Int])

<interactive>:1:0:
    No instance for (Fractional Int)
      arising from a use of `naivemean' at <interactive>:1:0-21
    Possible fix: add an instance declaration for (Fractional Int)
    In the expression: naivemean ([1] :: [Int])
    In the definition of `it': it = naivemean ([1] :: [Int])

Second, it blows the stack for large lists:

*Main> naivemean [1..1000000]
*** Exception: stack overflow

Also, it makes two passes, one for sum and one for length, over the list when a single pass will do.

We can correct all three problems with

{-# LANGUAGE BangPatterns #-}

mean :: (Real a, Fractional b) => [a] -> b
mean = go (toRational 0) 0
  where
    go !s !l []     = fromRational s / fromIntegral l
    go  s  l (x:xs) = go (s+.x) (l+1) xs
    s +. x = s + toRational x

Bang patterns force strict evaluation of the marked parameters. Without the bangs, the code above will also blow the stack when given a long list, but for a different reason: lazy evaluation of l for example generates a long unevaluated chain of the form

0 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + ...

In this case, lazy evaluation is creating more work in the form of allocating all the suspended computations than it would be to simply increment the counter on every iteration.

As a beginner, fromRational and toRational are probably confusing too. Consider the type of the division function:

*Main> :t (/)
(/) :: (Fractional a) => a -> a -> a

That means division is defined for any two values of the same type that is an instance of Fractional. Int is not one of those types:

*Main> (1::Int) / (2::Int)

<interactive>:1:0:
    No instance for (Fractional Int)
      arising from a use of `/' at <interactive>:1:0-18
    Possible fix: add an instance declaration for (Fractional Int)
    In the expression: (1 :: Int) / (2 :: Int)
    In the definition of `it': it = (1 :: Int) / (2 :: Int)

One definition of mean ought to cover all of [Int], [Float], and [Double] but without the rational bits (and without the type annotation), the type inferred for mean is

*Main> :t mean
mean :: [Double] -> Double

because of the division by the length of the list.

It turns out that Int, Float, and Double are instances of the typeclass Real,and any Real may be converted to Rational

*Main> :t toRational
toRational :: (Real a) => a -> Rational

and Rational may be converted to Fractional:

*Main> :t fromRational
fromRational :: (Fractional a) => Rational -> a

Finally, for large lists, there's also a chance that we could overflow a machine double, but Rational gives us arbitrary precision.

If you have a background in languages such as C or Java that promote types automatically to handle these cases, you'll find this particular inflexibility of Haskell's type system to be confusing and frustrating. I'm afraid you just have to learn to deal with it.

Having done all that, we can now

*Main> mean ([1..1000000] :: [Int])
500000.5

*Main> mean ([1..1000000] :: [Double])
500000.5

Warning: untested code ahead. In your definition of mean, you need to accurately carry along both the running sum and the running length, and as others have pointed out, you're not doing that. Something like the following should work:

mean0 sum len [] = sum / len
mean0 sum len (x:xs) = mean0 (sum+x) (len+1) xs

This definition passes along two accumulators, one each for the running total and the running count, that are updated as you recurse along the list. When the function finally runs out of list to process (the base case) it just does the needed calculation.

To use mean0, you just write

mean0 0 0 [2, 4, 6]

As you can see, it's sort of annoying to provide the initial values for the accumulators, so it's common to provide a wrapper like

mean xs = mean0 0 0 xs

Now, you write mean [2, 4, 6] just like you wanted to.

Haskell: The most beautiful imperative language

import Control.Monad.ST
import Data.STRef 
import Control.Monad

mean xs = s / l  
    where (s,l) = runST $ do{
       acc <- newSTRef (0,0);
       forM_ xs $ \x -> do{
          modifySTRef acc $  \(a,b) -> (x+a,1+b)
       };
       readSTRef acc }

let mean x = sum (x) / fromIntegral(length(x))

mean [2.0, 4.0, 6.0]

Of course, this must be improved (empty list, does work for doubles...).