检查haskell中函数参数的最佳方法

Question

我有一个函数说foo :: [Integer] - > Bool,但只有当传入的参数对某些条件有效时它才有效,否则它应该立即终止.

 foo x | not $ isSorted x = False
       | otherwise = some_recursive_stuff_here
       where
            isSorted ax = ax == sort ax

等等

但是我不希望每次都检查它是否已经排序.有没有一种好方法可以处理其他内容然后引入另一个内部函数？

Answer 1

你可以通过创建一个"携带"来保持你的不变量newtype.

newtype Sorted a = Sorted { fromSorted :: [a] }

sorted :: Ord a => [a] -> Sorted a
sorted = Sorted . sort

foo :: Sorted Integer -> Bool
foo (Sorted as) -> some_recursive_stuff_here

如果您将Sorted构造函数隐藏在单独的模块中,那么在foo不创建排序证明的情况下,您的代码用户将无法使用.他们也将无法sort一个Sorted,所以你可以肯定这只是发生过一次.

如果您愿意,甚至可以支持证明维护操作.

instance Monoid (Sorted a) where
  mempty = Sorted mempty
  mappend (Sorted as) (Sorted bs) = Sorted (go as bs) where
    -- lazy stable sort
    go :: Ord a => [a] -> [a] -> [a]
    go [] xs = xs
    go xs [] = xs
    go (x:xs) (y:ys) | x == y = x : y : go xs     ys
                     | x <  y = x     : go xs     (y:ys)
                     | x >  y =     y : go (x:xs) ys

(此代码现已在Hackage上提供:http://hackage.haskell.org/package/sorted )