我对文档感到有些困惑fix(虽然我认为我理解它现在应该做什么),所以我查看了源代码.这让我更加困惑:
fix :: (a -> a) -> a
fix f = let x = f x in x
这究竟是如何返回固定点的？
我决定在命令行试一试:
Prelude Data.Function> fix id
...
它挂在那里.现在公平地说,这是在我的旧Macbook上,这有点慢.但是,此功能也不能太过,因为任何东西传递给ID给出了同样的事情,回(更不用提,它的吃了没有CPU时间)计算昂贵.我究竟做错了什么？
在Ed Kmett的recursion-scheme包中,有三个声明:
newtype Fix f = Fix (f (Fix f))
newtype Mu f = Mu (forall a. (f a -> a) -> a)
data Nu f where
Nu :: (a -> f a) -> a -> Nu f
这三种数据类型有什么区别？
haskell recursive-datastructures recursion-schemes fixpoint-combinators
在Haskell中,这是一个固定点的简单(天真)定义
fix :: (a -> a) -> a
fix f = f (fix f)
但是,这是Haskell实际实现它的方式(效率更高)
fix f = let x = f x in x
我的问题是为什么第二个比第一个更有效？
我最近了解到Data.Function.fix,现在我想在任何地方应用它.例如,每当我看到递归函数时,我想" fix"它.所以基本上我的问题是我应该在何时何地使用它.
为了使它更具体:
1)假设我有以下代码用于分解n:
f n = f' n primes
where
f' n (p:ps) = ...
-- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
-- if n<=1: returns []
-- otherwise: returns [(n,1)]
如果我改写它fix,我会获得一些东西吗？失去什么？有可能,通过重写一个显式的递归到fix-version我会解决,反之亦然会创建一个堆栈溢出？
2)处理列表时,有几种解决方案:递归/修复,foldr/foldl/foldl',可能还有别的东西.关于何时使用每种方法,是否有任何一般指导/建议？例如,您是否会使用foldr无限的素数列表重写上面的代码？
可能还有其他重要问题没有在这里讨论.欢迎任何与使用相关的其他评论fix.
看一下GHC源代码,我可以看到修复的定义是:
fix :: (a -> a) -> a
fix f = let x = f x in x
在一个示例中,修复程序使用如下:
fix (\f x -> let x' = x+1 in x:f x')
这基本上产生了一个数字序列,它们增加1到无穷大.为了实现这一点,修复必须将它接收的函数作为它的第一个参数直接回到该函数.我不清楚上面列出的修复定义是如何做到的.
这个定义是我如何理解修复的工作原理:
fix :: (a -> a) -> a
fix f = f (fix f)
所以现在我有两个问题:
为了说清楚,我不是在谈论自由monad看起来很像一个应用于仿函数的固定点组合器,即Free f基本上是一个固定点f.(不是说这不好玩!)
我正在谈论的是固定点Free, Cofree :: (*->*) -> (*->*),即仿函数f,使得Free f同构于f自身.
背景:今天,坚定了我对自由的单子,而缺乏把握,我决定只写了他们的出来不同的简单仿函数,既为Free与对Cofree,看看有什么更好的知名[合作]单子他们会在同构.是什么吸引了我特别的是发现那Cofree Empty是同构的Empty(意思是,Const Void的任何类型映射到无人居住的仿函数).好吧,也许这只是愚蠢 - 我发现如果你把空垃圾放进去,你就会把空垃圾拿出来,是的! - 但是,嘿,这是类别理论,整个宇宙从看似琐碎的事物中崛起......对吧？
当前的问题是,如果Cofree有这样一个固定点,那又怎么样Free？嗯,它当然不能是Empty那不是一个单子.快速嫌疑人将附近的东西像Const ()或者Identity,但没有:
Free (Const ()) ~~ Either () ~~ Maybe
Free Identity ~~ (Nat,) ~~ Writer Nat
实际上,Free总是添加额外构造函数的事实表明,任何一个固定点的仿函数的结构必须已经是无限的.但似乎奇怪的是,如果Cofree有这样一个简单的定点,Free应该只有一个更复杂的定义点(就像FixFree a = …
根据定义,定点组合器并不总能产生正确的答案:
fix f = f (fix f)
以下代码不会终止:
fix (\x->x*x) 0
当然,fix不能总能产生正确的答案,但我很纳闷,这可以改进吗？
当然,对于上面的例子,可以实现一些看起来像的修复
fix f x | f x == f (f x) = f x
| otherwise = fix f (f x)
并给出正确的输出.
是什么原因导致上面的定义(或更好的东西,因为这个只有1个参数的句柄功能)不被使用？
我有一个函数,它根据迭代计算一个固定点:
equivalenceClosure :: (Ord a) => Relation a -> Relation a
equivalenceClosure = fst . List.head -- "guaranteed" to exist
. List.dropWhile (uncurry (/=)) -- removes pairs that are not equal
. U.List.pairwise (,) -- applies (,) to adjacent list elements
. iterate ( reflexivity
. symmetry
. transitivity
)
请注意,我们可以从这里抽象到:
findFixedPoint :: (a -> a) -> a -> a
findFixedPoint f = fst . List.head
. List.dropWhile (uncurry (/=)) -- dropWhile we have not reached the fixed point
. …>>>flip fix (0 :: Int) (\a b -> putStrLn "abc")
Output: "abc"
这是使用的简化版本flip fix.
我在一些youtube视频中看到了这种方式,可能来自Google技术谈话或其他一些谈话.
有人可以给我一些指针(不是一些内存地址,谢谢!)究竟fix是什么.我知道官方网站上的文档的一般定义.我已经在互联网上浏览了很多东西,但却找不到一个全面且易于理解的答案.
flip fix对我来说,这看起来像个谜.那个特定的函数调用实际发生了什么？
顺便说一下,我2个月前才选择了Haskell.而且我不擅长数学:(
这是完整的代码,由进行该演示的人共享,如果有人感兴趣:
(哦,这是解释游戏的维基链接mastermind 点击)
module Mastermind where
import Control.Monad
import Data.Function
import Data.List
import System.Random
data Score = Score
{ scoreRightPos :: Int
, scoreWrongPos :: Int
}
deriving (Eq, Show)
instance Read Score where
readsPrec _ r = [ (Score rp wp, t)
| (rp, s) <- readsPrec 11 r
, (wp, t) <- …我每次使用fix :: (a -> a) -> a时都会出现这种情况
((a -> b) -> a -> b) -> a -> b
一些a和b.实际上是否有一些应用程序将fix其类型参数未实例化为函数类型,而不是像琐碎的事情那样fix (const 0)？将签名保留为最一般的目的是什么？