还有什么可以`loeb`功能用于？

Question

我试图理解"Löb和möb: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或其他函子？

Answer 1

主要来源(我认为)loeb是Dan Piponi的博客,A Infinity of Infinity.他在那里更详细地解释了整个概念.我将复制一点作为答案并添加一些示例.

loeb 实现了一种奇怪的懒惰递归

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

让我们假设我们有一个类型a,where Functor a和a-algebra(类型的函数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-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包含一些Delayed值的结构,其中f是aFunctor

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)

举个例子,我们只需构建一个包含Delayed值的结构.一个自然的例子是使用之前的列表示例

> 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作为你的算子,你可以做很多有趣的事情.这是因为所有延迟值都Maybe采用了这种形式

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

从那以后Maybe (Delay (Maybe a) a)应该是所有有趣的价值观.因此,在一天结束时,价值甚至都没有被使用 - 我们总是拥有它Just (maybe default f)loeb Nothing = Nothingdefault

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

所以我们不妨直接写下来.