Putting an early terminating left fold to work.

I'd like to go over a piece of code that I wrote a while ago to solve a simple problem: Find the first cube to have 5 permutations of its digits that are also cubes. It's a project euler problem. My solution:

class EarlyFoldable f where

    earlyFoldlc :: (a -> b -> Either c a) -> a -> c -> f b -> c

    earlyFoldl :: (a -> b -> Either a a) -> a -> f b -> a

    earlyFoldl h a f = earlyFoldlc h a a f

    {-# INLINE earlyFoldl #-}

instance EarlyFoldable [] where

    earlyFoldlc f a c [] = c

    earlyFoldlc f a c (b:bs) =

        case (f a b) of 

            Left c' -> c'

            Right a' -> earlyFoldlc f a' c bs

p62_cubes = scanl (+) 1 $ scanl (+) 7 $ scanl (+) 12 $ repeat 6

p62_make_key = undigitize . sortBy (flip compare) . digitize

p62_update_map n = M.insertWith (+) (p62_make_key n) 1

p62_early_update m n =

    case p62_update_map n m of

        m' | m' M.! (p62_make_key n) == 5 -> Left n

        m' -> Right m'

p62 = earlyFoldlc p62_early_update M.empty 0 p62_cubes.

Now, some explanation. I defined a type class for an early terminating fold, with the obvious instance for list. earlyFoldlc returns Either c a, where c is the return type, and a is an intermediate state: an accumulator. The definition of p62_cubes should be familiar from a previous post. p62_make_key simply makes an integer key out of an integer. (It sorts the values in descending order so that zeros aren't lost.) p62_update_map is a simple helper. This is a case where we can't use a standard left or right fold. We can't use a standard left fold because the list is infinitely long, and we can't use a right fold because we need to look at the accumulated value before deciding to return.