Löb with error handling

loeb.md

Löb with error handling

löb is a well-known function in Haskell for implementing spreadsheet-like behaviors and tying the knot. It is defined as:

loeb :: Functor f => f (f a -> a) -> f a
loeb fs = xs
  where xs = fmap ($ xs) fs

As an example, we may use loeb to implement a spreadsheet:

λ> loeb [ (+ 1) . (!! 1)
        , (!! 3)
        , (+) <$> (!! 0) <*> (!! 1)
        , const (3 :: Int)
        ]
[4,3,7,3]

or to tie a knot:

λ> take 10 . head $ loeb [ ('a' :) . map succ . (!! 0) ]
"abcdefghij"

However, there is also absolutely nothing that prevents us to access an out-of-range index:

λ> loeb [ ('a' :) . map succ . (!! 1) ]
["a*** Exception: Prelude.!!: index too large

Ideally, we would like to avoid partial functions like (!!) and have each function return a Maybe in order to handle lookup failures. Therefore, our loeb will be specialized to:

loeb :: [[Maybe a] -> Maybe a] -> [Maybe a]

With the goal in mind, we proceed to write a naïve version like:

(#) :: [a] -> Int -> Maybe a
(x:_)  # 0 = Just x
(_:xs) # n = xs # (n - 1)
[]     # _ = Nothing
-- xs # n = xs ^? ix n

foo :: Int -> [Maybe String]
foo n = loeb
  [ \(mss :: [Maybe String]) ->
        do ms :: Maybe String <- mss # n
           s <- ms
           return $ 'a' : map succ s
  ]

Now, foo returns Nothing when we try to access an out-of-range element:

λ> foo 1
Nothing

So far so good! Next, let's try to tie a knot:

λ> foo 0
[

The evaluation does not terminate! What's wrong?

The culprit here is that: When we try to bind s from ms with s <- ms, we need to evaluate ms to WHNF to check if the constructor is Just or Nothing. However, in this case ms happens to be exactly what we are defining in the do block here, so this results in an infinite loop!

So, is it a dead end here? Fortunately, the answer is no. We can cheat by slightly altering the definition of foo to:

foo' :: Int -> Maybe [String]
foo' n = sequence $ loeb
  [ \mss -> do ms <- mss # n
               let Just s = ms
               return $ 'a' : map succ s
  ]

Here we directly assume that ms is just a Just. The pattern binding in let is lazy and therefore does not attempt to evaluate ms into WHNF. This breaks the infinite loop.

But wait, what if ms is actually a Nothing? Doesn't it just throw an exception in that case? How is this safe?

The trick here is that instead of returning a [Maybe String], we turn the list inside-out into a Maybe [String] with sequence. If ms is actually a Nothing, it follows that at least one element in the list returned by loeb is a Nothing, and sequence xs where Nothing `elem` xs will be simply Nothing! Conversely, users of foo' will only be able to retrieve a Just xs when all elements in mss are not Nothing. This guarantees that the irrefutable pattern in let Just s = ms used here is actually impossible to fail!

λ> take 10 . head <$> foo' 0
Just "abcdefghij"
λ> foo' 1
Nothing

Still, the question remains: Is it possible to write foo that does not use clever hacks like this one under the hood?

import Control.Monad.Trans.Maybe

loeb :: Functor f => f (f a -> a) -> f a
loeb x = go where go = fmap ($ go) x

(#) :: [Maybe a] -> Int -> Maybe a
(#) (x:_)  0 = x
(#) (_:xs) n =  (#) xs (n - 1)
(#) []     n = Nothing

*Main Control.Applicative> loeb [ (# 1), (# 3), (liftA2 (+)) <$> (# 0) <*> (# 1), const (Just (3 :: Int)) ]
[Just 3,Just 3,Just 6,Just 3]
*Main Control.Applicative> loeb [ (# 1), (# 4), (liftA2 (+)) <$> (# 0) <*> (# 1), const (Just (3 :: Int)) ]
[Nothing,Nothing,Nothing,Just 3]