为什么我不能从 Kadane 算法的这个 haskell 实现中删除 Ord Typeclass？

Question

我一直在haskell中实现kadane的算法，我想它工作正常

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]

我想从函数的类型规范中删除Ord类型类，因为我找不到所有可以排序的类型的最大子数组。但是我不能从类型说明中去掉Ord类型类。我最初通过询问haskell的类型推断来编写它们，如下所示

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

如果我删除Ord typecclass，如下所示

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]

，编译上面的代码会抛出以下错误

*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> 

根据可能的修复报告的错误，我需要再次添加Ord类型类，我做错了什么?

并请评估算法的正确性，如果可能的话建议替代方法

Answer 1

您不能删除Ord，因为您正在使用<和>等函数并在多态类型上操作它们。查看它们的类型:

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

但是，如果您将多态代码限制为仅在Int或Ord实例已经定义的任何其他单态实例上操作，那么您可以删除它:

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