我正在尝试理解《Haskell 中的 Löb 和 möb：奇怪的循环》，但现在意义正逐渐远离我，我只是看不出它为什么有用。回顾一下，函数loeb的定义如下：
loeb :: Functor f => f (f a -> a) -> f a
loeb x = go where go = fmap ($ go) x
或者等价地：
loeb x = go
where go = fmap (\z -> z go) x
在这篇文章中，提到了使用[]函子和电子表格实现的示例，但对于我来说，这个概念有些陌生，就像电子表格本身一样（我从未使用过它们）。
尽管我正在理解电子表格的事情，但我认为除了列表之外，拥有更多的示例将对我和其他人有很大帮助。是否有适用于Maybe或其他函子的loeb的应用程序？
我认为loeb的主要来源是丹·皮波尼的博客《无限邻域》(A Neighborhood of Infinity)。在那里，他更详细地解释了整个概念。作为答案，我将复制其中一部分并添加一些示例。
loeb实现了一种奇怪的惰性递归。
loeb :: Functor a => a (a x -> x) -> a x
loeb x = fmap (\a -> a (loeb x)) x
假设我们有一个类型a，其中Functor a，以及一个a代数（一个类型为a x -> x的函数）。您可以将其视为从值结构中计算值的方法。例如，这里是一些[]代数：
length :: [Int] -> Int
(!! 3) :: [a] -> a
const 3 :: Num a => [a] -> a
\l -> l !! 2 + l !! 3 :: Num a => [a] -> a
我们可以看到这些 a-代数既可以使用存储在 Functor 中的值，也可以使用 Functor 本身的结构。
另一种理解 d :: a x -> x 的方式是将其视为需要某些上下文——整个 Functor 化的值 a x 才能计算得出的 x 值。也许更清晰的解释是 Reader (a x) x，强调这只是一个被延迟的 x 值，等待产生 a x 上下文。
type Delay q x = q -> x
使用这些思想，我们可以描述loeb如下。给定一个包含一些Delay延迟值的f-结构，其中f是一个Functor
Functor f, f (Delay q x)
当然，如果我们已经有了一个q，那么我们可以将其转换为非延迟形式。实际上，只有一个（非作弊的）函数可以通过多态实现此功能：
force :: Functor f => f (Delay q x) -> q -> f x
force f q = fmap ($ q) f
loeb的作用是处理额外棘手的情况，即q实际上是force f q，这个函数的结果。如果您熟悉fix，那么我们可以完全通过它来产生这个结果。
loeb :: Functor a => a (Delay (a x) x) -> a x
loeb f = fix (force f)
Delay值的结构。一个自然的例子是使用之前的列表示例。> 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]
在这里，我们可以看到列表中充满了延迟等待列表评估结果的值。由于数据依赖关系中没有循环，因此可以完全进行计算，因此整个计算可以懒惰地确定。例如，const 3和const 5作为值都是立即可用的。length需要我们知道列表的长度但不需要了解其中包含的任何值，因此它也会立即处理我们的固定长度列表。有趣的是，被延迟等待来自结果列表内其他值的值，但由于(!! 2)最终只取决于结果列表的第三个值，该值由const 5决定，因此可以立即使用，计算向前移动。相同的想法也发生在(\l -> l !! 2 + l !! 3)中。
所以，这就是： loeb完成了这种奇怪的延迟值递归。我们可以对任何类型的Functor使用它，只需要考虑一些有用的Delayed值即可。
Chris Kuklewicz的评论指出，如果将Maybe作为functor，那么你可以做的事情并不多。这是因为所有关于Maybe的延迟值都采用以下形式:
maybe (default :: a) (f :: a -> a) :: Maybe a -> a
而所有有趣的Maybe (Delay (Maybe a) a)值都应该是Just (maybe default f)，因为loeb Nothing = Nothing。 因此在一天结束时，default值甚至从未被使用---我们总是只有那个值。
loeb (Just (maybe default f)) == fix f
所以我们最好直接写出来。
Maybe a -> a 是一个有趣的默认值代数，它与差异半群 data Diff a = Diff (a -> a) a 同构。从 \(Diff a' a) -> maybe a a' 到 \f -> Diff (f . Just) (f Nothing)，用于实现对非空列表的折叠。我不知道它是否有用或有趣，但希望能被证明是这样的。 - Iceland_jack您可以将其用于动态规划。我想到的一个例子是Smith-Waterman算法。
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)
这是一个实时示例，用于：Map String Float
http://tryplayg.herokuapp.com/try/spreadsheet.hs/edit
带有循环检测和循环解决的程序。
该程序计算速度、时间和空间。每个值都依赖于其他两个值。每个单元格都有两个值：当前输入值和作为其他单元格值/表达式函数的表达式。允许循环性。
单元格重新计算代码使用了2006年Dan Piponi著名的loeb表达式。据我所知，迄今为止还没有在实际工作电子表格上实现这个公式的材料化。这个程序接近它。由于当使用循环表达式时，loeb会进入无限循环，因此程序通过逐步用单元格值替换公式来减少复杂性，并计算循环次数，直到表达式没有循环。
该程序配置为在单元格更改时立即重新计算，但可以通过触发按钮来适应在重新计算之前修改多个单元格。
这是博客文章：
http://haskell-web.blogspot.com.es/2014/09/spreadsheet-like-program-in-browser.html
loeb g = x where x = g <*> pure x。这让我们想起了fix f = x where x = f $ x。 - Will Ness