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?