Why can't I remove the Ord Typeclass from this haskell implementation of Kadane's algorithm?

Question

I have been implementing kadane's algorithm in haskell, AFAIK it is working correctly

kadane' :: (Ord a, Num a) => [a] -> a
kadane' xs = head$ foldl maxsub [0,0] xs

maxsub :: (Ord a, Num a) => [a] -> a -> [a]
maxsub x y
    | last(x)+y > head(x) = if last(x)+y > 0 then [last(x)+y, last(x)+y] else [last(x)+y, 0]
    | otherwise = if last(x)+y > 0 then [head(x), last(x)+y]  else [head(x), 0]

I want to remove Ord typeclass from function's type specification, since I can't find maximum sub array for all the types that can be ordered. But I can't get rid of the Ord typeclass from the type specification. I wrote them initially by asking haskell's type inference as shown below

*Main> :t kadane' 
kadane' :: (Ord a, Num a) => [a] -> a
*Main> :t maxsub 
maxsub :: (Ord a, Num a) => [a] -> a -> [a]
*Main>

If I remove Ord Typeclass as shown below

kadane' :: (Num a) => [a] -> a
kadane' xs = head$ foldl maxsub [0,0] xs

maxsub :: (Num a) => [a] -> a -> [a]
maxsub x y
    | last(x)+y > head(x) = if last(x)+y > 0 then [last(x)+y, last(x)+y] else [last(x)+y, 0]
    | otherwise = if last(x)+y > 0 then [head(x), last(x)+y]  else [head(x), 0]

and compiling the above code throws the following error

*Main> :l kadanes.hs 
[1 of 1] Compiling Main             ( kadanes.hs, interpreted )

kadanes.hs:6:21:
    Could not deduce (Ord a) arising from a use of ‘>’
    from the context (Num a)
      bound by the type signature for maxsub :: Num a => [a] -> a -> [a]
      at kadanes.hs:4:11-36
    Possible fix:
      add (Ord a) to the context of
        the type signature for maxsub :: Num a => [a] -> a -> [a]
    In the expression: last (x) + y > head (x)
    In a stmt of a pattern guard for
                   an equation for ‘maxsub’:
      last (x) + y > head (x)
    In an equation for ‘maxsub’:
        maxsub x y
          | last (x) + y > head (x)
          = if last (x) + y > 0 then
                [last (x) + y, last (x) + y]
            else
                [last (x) + y, 0]
          | otherwise
          = if last (x) + y > 0 then
                [head (x), last (x) + y]
            else
                [head (x), 0]
Failed, modules loaded: none.
Prelude>

According to the Possible Fix reported in the error I need to add Ord typeclass again, What am I doing wrong ?

And also please evaluate the correctness of the algorithm, if possible suggest alternative ways

Style comment: the maxsub function should take (a,a) instead of [a], since you know there will be exactly two arguments. This will also allow you to avoid dangerous partial functions like head,last, and simply use pattern matching to fetch those e.g. maxsub (x1,x2) y = ... — chi

Sibi Sibi · Accepted Answer · 2015-05-24T06:21:52

You cannot remove Ord since you are using functions like < and > and operating them on polymorphic type. See their type:

λ> :t (<)
(<) :: Ord a => a -> a -> Bool

But if you instead limit your polymorphic code to operate only on Int or any other monomorphic instance for which Ord instance is already defined, then you can remove it:

maxsub :: [Int] -> Int -> [Int]
maxsub x y
    | last(x)+y > head(x) = if last(x)+y > 0 then [last(x)+y, last(x)+y] else [last(x)+y, 0]
    | otherwise = if last(x)+y > 0 then [head(x), last(x)+y]  else [head(x), 0]

kadane' :: [Int] -> Int
kadane' xs = head$ foldl maxsub [0,0] xs

Why can't I remove the Ord Typeclass from this haskell implementation of Kadane's algorithm?

1 Answers