A function that returns maximum of list and count of occurrences

0
votes

I'm writing a recursive function mxAndC. When I give it a list, it should return a tuple. The tuple will have the maximum of the given list as its first element and the second element will be the number of times the element occurs in the list. Assignment does not allow me to create a helper function. I'm expecting following output:

mxAdC "bananas" = (s,1)

mxAdC "banana" =(n,2)

mxAdC [mod x 4 | x <- [1..50]] -> (3,12)

I did the following:

mxAdC = go 0
 where go count (x:xs)  
           | count /= 0      = (mx, count)
           | null ((x:xs))   = error "The list is empty"
           | x == mx         = go (count+1) xs
         where mx = maximum (x:xs)

And I'm getting error:

* Ambiguous type variable `a0' arising from a use of `go'
      prevents the constraint `(Ord a0)' from being solved.
      Relevant bindings include
        mxAdC :: [a0] -> (a0, Integer) (bound at hw06.hs:24:1)
      Probable fix: use a type annotation to specify what `a0' should be.
      These potential instances exist:
        instance (Ord a, Ord b) => Ord (Either a b)
          -- Defined in `Data.Either'
        instance Ord Ordering -- Defined in `GHC.Classes'
        instance Ord Integer
          -- Defined in `integer-gmp-1.0.0.1:GHC.Integer.Type'
        ...plus 23 others
        ...plus 38 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    * In the expression: go 0
      In an equation for `mxAdC':
          mxAdC
            = go 0
            where
                go count (x : xs)
                  | count /= 0 = (mx, count)
                  | null ((x : xs)) = error "The list is empty"
                  | x == mx = go (count + 1) xs
                  where
                      mx = maximum (x : xs)

I'm very new in Haskell. Would any benevolent expert out there like to reach out and help out this newbie?

3
haskellrecursionfunctional-programminghigher-order-functions
You should add type signatures to your functions. – duplode
Possible duplicate of Haskell: What is the source of error "Ambiguous type variable ... `Integral t' ... `RealFrac t' ..." in this code? – duplode
@duplode: I think it's not really a duplicate. That other question has a contradicting type, this one is in principle sound but has a monomorphism-restriction problem. Same error message, but quite different underlying problem. – leftaroundabout
@duplode the question you alluded to as being duplicate of that of mine does not really address my problem,although they have the same error message.Please re-read my question. Thank you. – Ali Toto
@leftaroundabout Indeed. Close vote retracted, then. – duplode

3 Answers

0
votes

A fairly straightforward implementation would use filter:

mxAdC :: Ord a => [a] -> (a,Int)
mxAdC xs = (mx,length $ filter (\x -> x == mx) xs) where mx = maximum xs
0
votes

You hit the dreaded Monomorphism Restriction.

You can fix the type error by

  • using mxAdC x = go 0 x
  • putting {-# LANGUAGE NoMonomorphismRestriction #-} at the beginning of your file
  • adding the type signature

Your function is still wrong, but now it typechecks.

Haskell prohibits polymorphic functions that look like top-level constants (don't have parameters before the = sign). So in general you cannot eta-reduce (replace foo x = bar x with foo = bar). The full explanation is rather long - see this answer: https://stackoverflow.com/a/32496865/805266

0
votes

Others have explained the type error. Let's look at the more interesting mistakes.

  | null ((x:xs))   = error "The list is empty"

What's wrong? x : xs is never null. It can't possibly be, because its first element is x! What you meant to do here was

mxAdC ys
  | null ys = error "mxAdC: the list is empty"
  | otherwise = go 0 ys
  where ...

The next problem is

  | count /= 0      = (mx, count)

This says that as soon as the count is non-zero, you're done. So you'll never get above 1. You recognized that your recursion needed a base case, so you tried to put one in, but you missed the mark. The base case you need is to deal with the empty list:

go count [] = ?
go count (x:xs)  
  | x == mx         = go (count+1) xs

Something is still missing from go, however. What do you want to happen when x /= mx? You need to add one more case (I've left question marks for you to fill in):

go count [] = ?
go count (x:xs)  
  | x == mx         = go (count+1) xs
  | otherwise       = ?

The final major problem is that you defined mx within the go function. This will calculate the maximum of whatever piece of the list go was handed, each time. What you want to do is define mx in mxAdC

mxAdc ys
  | ....
  where
    go ...
    mx = maximum ys

There are still two big efficiency problems to deal with. One problem is that go no longer forces calculation of the accumulator in the recursive call, which may lead to a space leak. This is easily fixed using the BangPatterns language extension with

go !count [] = ?
go !count (x:xs)  
  | x == mx         = go (count+1) xs
  | otherwise       = ?

The last problem is that you still traverse the list twice: once to calculate the maximum and then again to count how many times it occurs. It's possible to do it in just one pass. I won't give you all the details, but the basic trick is to change your go function to take the greatest element seen thus far as well as the number of times it's been seen. You'll have to adjust the rest of mxAdC to fit, using a pattern match to get things going instead of null.