我试图理解"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
在文章中有一个[]
函子和电子表格实现的示例,但对我来说有点陌生,就像电子表格本身一样(从未使用过它们(。
虽然我理解电子表格的事情,但我认为尽管有列表,但拥有更多示例对我和其他人有很大帮助。是否有任何Maybe
或其他函子的loeb
应用程序?
loeb
的主要来源(我认为(是Dan Piponi的博客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
的方式是x
的值,它需要一些上下文 - 一个完整的Functor
化值a x
- 才能计算。也许这种解释写得更清楚Reader (a x) x
,强调这只是一个延迟的x
值,等待产生a x
语境。
type Delay q x = q -> x
使用这些想法,我们可以loeb
描述如下。我们得到了一个包含一些Delay
ed 值的 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
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
值。
Chris Kuklewicz 的评论指出,用Maybe
作为你的函子,你可以做很多有趣的事情。这是因为所有超过Maybe
的延迟值都采用以下形式
maybe (default :: a) (f :: a -> a) :: Maybe a -> a
自loeb Nothing = Nothing
年以来,Maybe (Delay (Maybe a) a)
的所有有趣的价值观都应该Just (maybe default f)
.因此,归根结底,default
值甚至永远不会被使用---我们总是只有这个
loeb (Just (maybe default f)) == fix f
所以我们不妨直接写。
您可以将其用于动态编程。我想到的例子是史密斯-沃特曼算法。
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)
下面是一个用于以下用途的实时示例: 映射字符串浮点数
http://tryplayg.herokuapp.com/try/spreadsheet.hs/edit
具有环路检测和环路分辨率。
该程序计算速度,时间和空间。每个都依赖于其他两个。每个单元格有两个值:他当前输入的值和作为其他单元格值/表达式函数的表达式。 允许循环。
单元格重新计算代码使用了Dan Piponi在2006年著名的loeb表达式。据我所知,到目前为止,这个公式还没有在真正的工作电子表格上实现任何具体化。这个很接近它。由于在使用循环表达式时 loeb 进入无限循环,因此程序通过逐步用单元格值替换公式来计算循环并降低复杂性,直到表达式没有循环
该程序配置为在单元格更改时立即重新计算,但可以通过按钮触发它来调整以允许在重新计算之前修改多个单元格。
这是博客pos:
http://haskell-web.blogspot.com.es/2014/09/spreadsheet-like-program-in-browser.html