标签: fixed-point-iteration

根据定义,定点组合器并不总能产生正确的答案:

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个参数的句柄功能)不被使用？

我最近发现了如何 以某种迂回的方式在 Java 中模拟高阶类型，如下所示

interface H<F, T> { }

这里H编码一个高阶类型，它采用类型参数，F该类型参数本身采用参数T。

现在这让我想知道，我们可以用它来实现一些更高级的构造吗？例如，Haskell 中的 Fix 等函子的不动点及其相应的变形？

这是一个函数,用C表示:

uint32_t f(uint32_t x) {
    return (x * 0x156) ^ 0xfca802c7;
}

然后我遇到了一个挑战:如何找到所有固定点？

我知道我们可以测试每个uint32_t值来解决这个问题,但是我仍然想知道是否有另一种更优雅的方式 - 特别是当uint32_t变为uint64_t并且(0x156, 0xfca802c7)是一对任意值时.

我怎样才能解决这个等式

x ³ + x - 1 = 0

使用定点迭代？

我可以在网上找到任何定点迭代代码(特别是在Python中)吗？

我需要找到下面定义给出的帐篷地图函数的固定点和吸引子:

    xt =  (3/2) * xt-1      when 0 <= x <= (2/3)

    and

    xt = 3* (1-xt-1)        when (2/3) <= x <= 1

我正在使用下面的MATLAB代码生成一个蛛网图(如下面的代码所示),看看我是否可以深入了解这个特定的帐篷地图功能.正如你所看到的那样,我首先设置t = 1(和x(1)= 0.2001),但是有很多可能的地方可以开始.如果不测试每个起点,如何确定固定点/吸引子？

clear
close all

% Initial condition 0.2001, must be symbolic.
nmax=200;
t=sym(zeros(1,nmax));t1=sym(zeros(1,nmax));t2=sym(zeros(1,nmax));
t(1)=sym(2001/10000);
mu=2;
halfm=(2/3) *nmax;
axis([0 1 0 1]);
for n=2:nmax
    if (double(t(n-1)))>0 && (double(t(n-1)))<=2/3         % 0 <= x <= (2/3)
            t(n)=sym((3/2)*t(n-1));                        % x(t) = (3/2) * x(t-1)
        else
            if (double(t(n-1)))<1                          % else (2/3) <= x <= …

我正在寻找一个库,它将计算一组变量arity运算符下的集合的固定点/闭包.例如,

fixwith [(+)] [1]

对于整数应该计算所有N(自然1..).我试着去写它,但有些东西是缺乏的.它效率不高,我觉得我对多功能的处理并不是最优雅的.此外,是否可以使用内置fix函数而不是手动递归来编写？

class OperatorN ? ? | ? -> ? where
    wrap_op :: ? -> (Int, [?] -> ?)

instance OperatorN ? (() -> ?) where
    wrap_op f = (0, \[] -> f ())

instance OperatorN ? (? -> ?) where
    wrap_op f = (1, \[x] -> f x)

instance OperatorN ? ((?, ?) -> ?) where
    wrap_op f = (2, \[x, y] -> f (x, y))

instance OperatorN ? ((?, ?, ?) …

我有一个带有以下签名的函数：

simCon :: [Constraint] -> Maybe [Constraint]

我想编写一个方法，以防simCon返回Just [Constraint]，我想将它们反馈回simCon并重新运行该方法，并继续这样做，直到输入与输出相同为止。

如果什么都没有，我想终止算法。

如果输入和输出都是相同的类型，我有一些可以工作的东西

fixed :: Eq a => (a -> a) -> a -> a
fixed f a 
  | a == a' = a
  | otherwise = fixed f a'
  where a' = f a

但这是行不通的，因为我现在返回Maybe。有人可以建议一种方法来编写类似的函数，但要返回Maybe吗？

我最近注意到我经常编写函数，这些函数只是迭代另一个函数，f直到它到达一个固定点（这样f x == x）

我认为这是一个非常笼统的概念，所以我认为可能有一个内置的。

所以我想知道是否有一个内置的，或者更一般的东西？

所以我基本上是在寻找这个：

fixedpoint f x= head . dropWhile(\y->y /= f y) $ iterate f x

我只是在谷歌搜索时遇到了麻烦，因为我只fix在我的搜索词包含fixed point或类似的东西时才找到对该函数的引用。

介绍

固定点是一个函数的参数,它将返回不变:f x == x.一个例子是(\x -> x^2) 1 == 1- 这里固定点是1.

有吸引力的固定点是那些可以通过从某个起点迭代找到的固定点.例如,(\x -> x^2) 0.5会收敛到0,因此0是该函数的有吸引力的固定点.

幸运的是,通过从该点迭代函数,可以从合适的非固定点接近(并且在某些情况下,甚至在那么多步骤中达到)有吸引力的固定点.其他时候,迭代会发散,所以首先应该有一个证据表明固定点会吸引迭代过程.对于某些功能,证明是常识.

代码

我已经整理了一些能够整齐地完成任务的现有技术.然后我开始将相同的想法扩展到monadic函数,但没有运气.这是我现在的代码:

module Fix where

-- | Take elements from a list until met two equal adjacent elements. Of those,
--   take only the first one, then be done with it.
--
--   This function is intended to operate on infinite lists, but it will still
--   work on finite ones.
converge :: Eq …

下面的程序生成<<loop>>GHC。

...明显地。事后看来。

发生这种情况是因为walk正在计算一个不动点，但有多个可能的不动点。当列表推导式到达图形遍历的末尾时，它“询问” 的下一个元素answer；但这正是它已经在尝试计算的。我想我认为程序会到达，呃，列表的末尾，然后停止。

我不得不承认，我对这个漂亮的代码有点感伤，希望我能让它工作。

• 我应该怎么做？

• 我如何预测“打结”（指的是表示如何计算值的表达式中的值）是一个坏主意？

import Data.Set(Set)
import qualified Data.Set

-- Like `Data.List.nub`, remove duplicate elements from a list,
-- but treat some values as already having been seen.
nub :: Set Integer -> [Integer] -> [Integer]
nub _ [] = []
nub seen (x:xs) =
  if Data.Set.member x seen
  then nub seen xs
  else x : nub (Data.Set.insert x seen) xs

-- A directed graph where the vertices are integers.
successors …