best way to check arguments of a function in haskell

Question

I have a funciton say foo :: [Integer] -> Bool , but it only works if the incoming argument is valid for some criteria, otherwise it should terminate immediately.

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

etc.

But I don't want to check invariant every time if it is sorted or not. Is there a good way to deal with that other then introducing another internal function?

Answer 1

You can carry around "proof" that your invariant holds by creating a 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

If you hide the Sorted constructor in a separate module then users of your code will be unable to use foo without creating proof of sorting first. They also won't be able to sort a Sorted so you can be sure it's only occurred once.

You can even support proof-maintaining operations if you like.

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

(This code is available now on Hackage: http://hackage.haskell.org/package/sorted)