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?

Brimstone

When you try usig 'loeb' using 'Maybe', you will find only two trivial ways to do it. Or you could try and define the Fibonacci series, [Integer]... – Hangnail

If the functor is also applicative, then by interchange law loeb g = x where x = g <*> pure x. Reminds us of fix f = x where x = f $ x. – Bred

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.

Trebizond

The Maybe a -> a is an interesting default-value-algebra and is isomorphic to the difference semigroup data Diff a = Diff (a -> a) a going from \(Diff a' a) -> maybe a a' to \f -> Diff (f . Just) (f Nothing) used to implement folds over non-empty lists.. I don't know if it's useful or interesting but would like to be shown otherwise – Kendrakendrah

Answer 2

You can use it for dynamic programming. The example that comes to mind is the Smith-Waterman algorithm.

import Data.Array
import Data.List
import Control.Monad

data Base = T | C | A | G deriving (Eq,Show)
data Diff = Sub Base Base | Id Base | Del Base | Ins Base deriving (Eq,Show)

loeb x = let go = fmap ($ go) x in go

s a b = if a == b then 1 else 0

smithWaterman a' b' = let
  [al,bl] = map length [a',b']
  [a,b] = zipWith (\l s -> array (1,s) $ zip [1..] l) [a',b'] [al,bl]
  h = loeb $ array ((0,0),(al,bl)) $
    [((x,0),const 0) | x <- [0 .. al]] ++
    [((0,y),const 0) | y <- [1 .. bl]] ++
    [((x,y),\h' -> maximum [
       0,
       (h' ! (x - 1,y - 1)) + s (a ! x) (b ! y),
       (h' ! (x - 1, y)) + 1,
       (h' ! (x, y - 1)) + 1
      ]
     ) | x <- [1 .. al], y <- [1 .. bl]]
  ml l (0,0) = l
  ml l (x,0) = ml (Del (a ! x): l) (x - 1, 0)
  ml l (0,y) = ml (Ins (b ! y): l) (0, y - 1)
  ml l (x,y) = let
    (p,e) = maximumBy ((`ap` snd) . (. fst) . (const .) . (. (h !)) . compare . (h !) . fst) [
      ((x - 1,y),Del (a ! x)),
      ((y, x - 1),Ins (b ! y)),
      ((y - 1, x - 1),if a ! x == b ! y then Id (a ! x) else Sub (a ! x) (b ! y))
     ]
    in ml (e : l) p
  in ml [] (al,bl)

Aware

Answer 3

Here is a live example where it is used for: Map String Float

http://tryplayg.herokuapp.com/try/spreadsheet.hs/edit

with loop detection and loop resolution.

This program calculates speed, time and space. Each one depends on the other two. Each cell has two values: his current entered value and the expression as a function of the other cell values/expressions. circularity is permitted.

The Cell recalculation code uses the famous loeb expression by Dan Piponi in the 2006. Until now by my knowledge there haven't been any materialization of this formula on a real working spreadsheet. this one is close to it. Since loeb enters in a infinite loop when circular expressions are used, the program counts the loops and reduces complexity by progressively substituting formulas by cell values until the expression has no loops

This program is configured for immediate recalculation on cell change, but that can be adapted to allow the modification of more than one cell before recalculation by triggering it by means of a button.

This is blog pos:

http://haskell-web.blogspot.com.es/2014/09/spreadsheet-like-program-in-browser.html

Dorolice