What else can `loeb` function be used for?

Question

I am trying to understand "Löb and möb: strange loops in Haskell", but right now the meaning is sleaping away from me, I just don't see why it could be useful. Just to recall function loeb is defined as

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

or equivalently:

loeb x = go 
  where go = fmap (\z -> z go) x

In the article there is an example with [] functor and spreadsheets implementation, but it is bit foreign for me just as spreadsheets themselves (never used them).

While I'm understanding that spreadsheet thing, I think it would help a lot for me and others to have more examples, despite lists. Is there any application for loeb for Maybe or other functors?

Answer 1

The primary source (I think) for loeb is Dan Piponi's blog, A Neighborhood of Infinity. There he explains the whole concept in greater detail. I'll replicate a little bit of that as an answer and add some examples.

loeb implements a strange kind of lazy recursion

loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x

Let's imagine we have a type a, where Functor a, and an a-algebra (a function of type a x -> x). You might think of this as a way of computing a value from a structure of values. For instance, here are a few []-algebras:

length                ::          [Int] -> Int
(!! 3)                ::          [a]   -> a
const 3               :: Num a => [a]   -> a
\l -> l !! 2 + l !! 3 :: Num a => [a]   -> a

We can see that these a-algebras can use both values stored in the Functor and the structure of the Functor itself.

Another way to think of d :: a x -> x is as a value of x which requires some context–a whole Functorized value a x–in order to be computed. Perhaps this interpretation is more clearly written as Reader (a x) x, emphasizing that this is just a value of x which is delayed, awaiting the a x context to be produced.

type Delay q x = q -> x

Using these ideas we can describe loeb as follows. We're given a f-structure containing some Delayed values, where f is a Functor

Functor f, f (Delay q x)

Naturally, if we were given a q then we could convert this into a not delayed form. In fact, there's only one (non-cheating) function that does this polymorphically:

force :: Functor f => f (Delay q x) -> q -> f x
force f q = fmap ($ q) f

What loeb does is handle the extra tricky case where q is actually force f q, the very result of this function. If you're familiar with fix, this is exactly how we can produce this result.

loeb :: Functor a => a (Delay (a x) x) -> a x
loeb f = fix (force f)

---

So to make an example, we simply must build a structure containing Delayed values. One natural example of this is to use the list examples from before

> loeb [ length                  :: [Int] -> Int
       , const 3                 :: [Int] -> Int
       , const 5                 :: [Int] -> Int
       , (!! 2)                  :: [Int] -> Int
       , (\l -> l !! 2 + l !! 3) :: [Int] -> Int
       ]
[5, 3, 5, 5, 10]

Here we can see that the list is full of values delayed waiting on the result of evaluating the list. This computation can proceed exactly because there are no loops in data dependency, so the whole thing can just be determined lazily. For instance, const 3 and const 5 are both immediately available as values. length requires that we know the length of the list but none of the values contained so it also proceeds immediately on our fixed-length list. The interesting ones are the values delayed waiting on other values from inside our result list, but since (!! 2) only ends up depending on the third value of the result list, which is determined by const 5 and thus can be immediately available, the computation moves forward. The same idea happens with (\l -> l !! 2 + l !! 3).

---

So there you have it: loeb completes this strange kind of delayed value recursion. We can use it on any kind of Functor, though. All we need to do is to think of some useful Delayed values.

---

Chris Kuklewicz's comment notes that there's not a lot you could do interestingly with Maybe as your functor. That's because all of the delayed values over Maybe take the form

maybe (default :: a) (f :: a -> a) :: Maybe a -> a

and all of the interesting values of Maybe (Delay (Maybe a) a) ought to be Just (maybe default f) since loeb Nothing = Nothing. So at the end of the day, the default value never even gets used---we always just have that

loeb (Just (maybe default f)) == fix f

so we may as well write that directly.