The compactness and efficiency of the code is quite impressive. The downside is that it's rather convoluted and difficult to understand.
Haskell types are very helpful, both when writing and reading code. Type declarations should not be limited to top-level functions. They can, and should, be added to local variables as well. Even though it's not very complicated, the purpose of
endpoints becomes much clearer when its type is explicitly stated:
endpoints :: [(a, b)] -> [Either a b]
endpoints = foldr (\(a, b) m -> (Left a):(Right b):m) 
It converts tuples into eithers. It's obvious from the type that it works almost like a map, which we can make more explicit by using
endpoints = concatMap (\(a,b) -> [Left a, Right b])
Another way in which types improve readability is that they hint at the semantics of a value.
Either is a very generic type, defining a newtype for interval endpoints might make things easier to understand.
Related code should usually be grouped together. The order, in which the local functions are defined, seems rather random. Reorganizing those functions could benefit readability.
(x:xs) a are shadowed in some functions. That's confusing and will cause compiler warnings when compiled with
-Wall. I'd suggest renaming the outer
This is just personal taste, but I'd also rename
fromEither (in analogy to
fromJust). This would make even more sense if a custom type was used (e.g.
Below is what I perceive as a cleaner version of this function. It doesn't have the nice compactness of the original code, but uses the same basic algorithm. The local functions are quite general and can easily be promoted to top level functions. Reusable code is usually to be preferred.
import Data.Function (on)
import Data.List (group, sortBy)
type Border a = Either a a
disjoint' :: (Ord a) => [(a, a)] -> [(a, a)]
disjoint' = concatMap consecutiveBordersToIntervals
. sortBy (compare `on` fromBorder)
intervalBorders :: [(a, a)] -> [Border a]
intervalBorders = concatMap $ \(x, y) -> [Left x, Right y]
groupBalancedBorders :: [Border a] -> [[Border a]]
groupBalancedBorders  = 
groupBalancedBorders xs = let (ys, zs) = spanBalancedBorders 0 xs
in ys : groupBalancedBorders zs
spanBalancedBorders :: Int -> [Border a] -> ([Border a], [Border a])
spanBalancedBorders _  = (, )
spanBalancedBorders balance (x:xs) =
let balance' = either (const $ balance + 1) (const $ balance - 1) x
in case balance' of
0 -> ([x],xs)
_ -> let (ys,zs) = spanBalancedBorders balance' xs in (x:ys,zs)
consecutiveBordersToIntervals :: (Eq a) => [Border a] -> [(a, a)]
(\xs -> zip xs (tail xs)) . dedupSortedList . map fromBorder
dedupSortedList :: (Eq a) => [a] -> [a]
dedupSortedList = map head . group
fromBorder :: Border a -> a
fromBorder = either id id
This is as fast as the original, but arguably easier to read. It also fixes a bug which caused empty intervals to be included.
>>> disjoint [(1,5), (5,10), (1,10)]
>>> disjoint' [(1,5), (5,10), (1,10)]
As a final note, one should be aware that the algorithm makes some implicit assumptions on the topology of the intervals in
a. It would break down when intervals were allowed to have start points which are greater than their endpoint (think modular arithmetic).