Cannot comform type when implementing max iterator with own typeclass in Haskell

user_8804960 0
Viewed 38

I'm trying to implement max iterator(like in Ruby) by using my own typeclass Max and List instance. But I cannot make the type correct. Does that mean 'b' cannot be same as 'a'? But what is I would like to get max item by their own value?

class Max t where
  c_max :: (a->b) -> t a -> a

instance Max [] where
  c_max f [a] = a
  c_max f (x:xs) = max (f x) (c_max f xs)

main = putStrLn $ show $ c_max (\x-> x) [1,2]
haskell
1 Answers

I cannot make the type correct. Does that mean b cannot be same as a?

It can, but the two are not per se the same.

The problem however does not arise from the use of c_max in the main function. There are basically two problems here.

First, you perform a mapping from a to b, but you did not restrict b to a type that is an instance of Ord. As a result, we can not compare the two bs to decide what b is the largest. We thus should add an Ord b typeconstraint:

class Max t where
    c_max :: Ord b => (a -> b) -> t a -> a

In your instance Max [] your max compares two bs, and returns the largest b. But given your type signature, you want to return the corresponding a. We can implement this with:

instance Max [] where
    c_max f [a] = a
    c_max f (x:xs) | f x > f mx = x
                   | otherwise = mx
        where mx = c_max f xs

For example:

Prelude> putStrLn $ show $ c_max (\x-> x) [1,2]
2

The above is not the most efficient implementation, since we here will calculate f x multiple times per item. I leave it as an exercise to optimize this further.

Note that in Haskell there is a maximum :: (Foldable f, Ord a) => f a -> a function that works on Foldables. This thus will work with a list, a Tree, etc. One can define a maximumBy or something similar that operates on a Foldable as well, by slightly altering the "fold function".

user_675790
Related