haskell - loeb函数还能用于什么？

我正在尝试理解"Löb and möb: strange loops in Haskell"，但是现在含义已经从我身上溜走了，我只是不明白为什么它可能有用。只是想起函数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

在本文中，有一个使用[]函子和电子表格实现的示例，但是对我而言，就像电子表格本身一样(从未使用过)，这有点陌生。

尽管我了解电子表格的内容，但我认为尽管列出了清单，但对我和其他人来说，有更多的例子将大有帮助。是否有loeb或其他函子的Maybe应用程序？

最佳答案

loeb的主要来源(我认为)是Dan Piponi's blog, 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 -algebra(a x -> x类型的函数)。您可能会认为这是从价值结构中计算价值的一种方式。例如，这是一些[] -algebras:

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

我们可以看到，这些a -algebras可以同时使用Functor中存储的值和Functor本身的结构。

另一种思考d :: a x -> x的方法是将x的值计算出来，该值需要一些上下文-整个Functor值a x的值。也许这种解释更清楚地写为Reader (a x) x，强调这只是x的值，该值被延迟，等待a x上下文产生。

type Delay q x = q -> x

利用这些想法，我们可以如下描述loeb。我们得到了一个f-结构，其中包含一些Delay ed值，其中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 ed值的结构。一个自然的例子是使用之前的列表例子

> 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上使用它。我们需要做的就是考虑一些有用的Delay ed值。

Chris Kuklewicz的评论指出，使用Maybe作为函子可以做很多有趣的事情。这是因为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

因此我们不妨直接写出来。