Understanding the Problem

In functional programming, especially in Haskell, you often encounter algorithms designed around total functions. For instance, consider the standard sorting function signature:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

What happens when you need to sort elements where the comparison function might fail? For example, if two elements are non-orderable or invalid, you want the entire sorting operation to short-circuit and return Nothing. Your desired signature becomes:

failableSortBy :: (a -> a -> Maybe Ordering) -> [a] -> Maybe [a]

Can you automatically convert higher-order functions like sortBy into failable versions using generic combinators, or do you need a different strategy?

Why Higher-Order Pure Functions Can't Be Lifted Automatically

It is tempting to look for a universal combinator like map or traverse to automatically convert (a -> b) -> c into (a -> Maybe b) -> Maybe c. However, pure higher-order functions like sortBy swallow the intermediate comparisons internally. They expect a concrete Ordering value on every step and have no built-in mechanism to short-circuit evaluation when a Nothing occurs.

Because standard sortBy is not written monadically, passing a comparison function that returns Maybe Ordering requires either rewriting the algorithm in a monadic context or using control flow effects.

Solution 1: Monadic Generalization (The Idiomatic Approach)

The standard pattern in Haskell for algorithms that might fail or perform side effects is to write a monadic version of the algorithm. By defining a sortByM function, you accept comparison functions with a return type of m Ordering (where m can be Maybe, Either e, or any Monad).

Here is how you can implement a monadic merge sort:

import Control.Monad (filterM)  sortByM :: Monad m => (a -> a -> m Ordering) -> [a] -> m [a] sortByM _ []  = return [] sortByM _ [x] = return [x] sortByM cmp xs = do   let (left, right) = splitAt (length xs `div` 2) xs   sortedLeft  <- sortByM cmp left   sortedRight <- sortByM cmp right   mergeM cmp sortedLeft sortedRight  mergeM :: Monad m => (a -> a -> m Ordering) -> [a] -> [a] -> m [a] mergeM _ [] ys = return ys mergeM _ xs [] = return xs mergeM cmp (x:xs) (y:ys) = do   ord <- cmp x y   case ord of     LT -> (x :) <$> mergeM cmp xs (y:ys)     _  -> (y :) <$> mergeM cmp (x:xs) ys

With sortByM available, obtaining failableSortBy becomes trivial because Maybe is an instance of Monad:

failableSortBy :: (a -> a -> Maybe Ordering) -> [a] -> Maybe [a] failableSortBy = sortByM

Solution 2: Short-Circuiting with Pure Combinators using Continuations

If you strictly want to reuse a non-monadic sorting algorithm without rewriting it, you can achieve short-circuiting using exceptions or continuations (e.g., Codensity or ExceptT with lazy evaluation), though this relies on pure exception handling mechanisms like catch in specialized contexts or custom AST evaluation.

A cleaner alternative without monadic algorithms is using list validation pre-processing, transforming the input list [a] into Maybe [b] where b is guaranteed to be totally ordered, but this shifts the orderability check out of the sort phase.

Summary & Recommendations

  • Direct lifting isn't possible: Pure higher-order functions cannot be automatically transformed into monadic variants without control-flow modifications.
  • Use Monadic Generalizations: The most robust and idiomatic Haskell solution is to define or use monadic variants of algorithms (e.g., sortByM, mapM, foldM).
  • Monad Transformers: By generalizing functions to Monad m => ... -> m b, you automatically support Maybe, Either, state, and IO scenarios without rewriting code.