What else can `loeb` function be used for?
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)
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 Functor
ized 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 Delay
ed 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 Delay
ed 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 Delay
ed 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.