Recursion Scheme Thoughts

recursion-schemes.md

Here's an example function to determine whether a set is strongly connected with respect to an adjacency function, implemented with direct recursion:

connected :: Ord a => (a -> [a]) -> Set a -> Bool
connected f s = 
    go (take 1 $ Set.elems s) s
  where
    go _ s | Set.null s = True
    go [] _             = False
    go (x:xx) s
        | Set.member x s = go (f x <> xx) (Set.delete x s)
        | otherwise      = go xx s

This is a simple example, but exhibits (a) two exit conditions and (b) more than "one thing" changing during the recursion.

Here's the same function, with the direct recursion refactored into recursion schemes:

connected :: Ord a => (a -> [a]) -> Set a -> Bool
connected adj s = hylo cata ana (take 1 $ Set.elems s, s)
  where
    cata (Cons (l,s) z)
        | Set.null s = True
        | null l     = False
        | otherwise  = z
    ana z@([],_) = (Cons z z)
    ana z@(x:xx,s)
        | Set.member x s = Cons z (adj x <> xx, Set.delete x s)
        | otherwise      = Cons z (xx,s)