5

介绍

固定点是函数的参数，它会原样返回：f x == x. 一个例子是(\x -> x^2) 1 == 1——这里的不动点是 1。

有吸引力的不动点是那些可以从某个起点通过迭代找到的不动点。例如，(\x -> x^2) 0.5将收敛到 0，因此 0 是该函数的一个有吸引力的不动点。

幸运的是，可以通过从该点迭代函数来从合适的非固定点逼近（并且在某些情况下，甚至在许多步骤中达到）有吸引力的固定点。其他时候，迭代会发散，所以首先应该有一个证据证明一个固定点会吸引迭代过程。对于某些函数，证明是常识。

编码

我整理了一些可以巧妙地完成任务的现有技术。然后我开始将同样的想法扩展到一元函数，但没有成功。这是我现在拥有的代码：

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 a => [a] -> [a]
converge = convergeBy (==)

-- \ r a = \x -> (x + a / x) / 2
-- \ -- ^ A method of computing square roots due to Isaac Newton.
-- \ take 8 $ iterate (r 2) 1
-- [1.0,1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899,
-- 1.414213562373095,1.414213562373095,1.414213562373095]
-- \ converge $ iterate (r 2) 1
-- [1.0,1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899,1.414213562373095]

-- | Find a fixed point of a function. May present a non-terminating function
--   if applied carelessly!
fixp :: Eq a => (a -> a) -> a -> a
fixp f = last . converge . iterate f

-- \ fixp (r 2) 1
-- 1.414213562373095

-- | Non-overloaded counterpart to `converge`.
convergeBy :: (a -> a -> Bool) -> [a] -> [a]
convergeBy _ [ ] = [ ]
convergeBy _ [x] = [x]
convergeBy eq (x: xs@(y: _))
    | x `eq` y = [x]
    | otherwise = x : convergeBy eq xs

-- \ convergeBy (\x y -> abs (x - y) < 0.001) $ iterate (r 2) 1
-- [1.0,1.5,1.4166666666666665,1.4142156862745097]

-- | Non-overloaded counterpart to `fixp`.
fixpBy :: (a -> a -> Bool) -> (a -> a) -> a -> a
fixpBy eq f = last . convergeBy eq . iterate f

-- \ fixpBy (\x y -> abs (x - y) < 0.001) (r 2) 1
-- 1.4142156862745097

-- | Find a fixed point of a monadic function. May present a non-terminating
--   function if applied carelessly!
--   TODO
fixpM :: (Eq a, Monad m) => (m a -> m a) -> m a -> m a
fixpM f = last . _ . iterate f

（它可能被加载到repl。有例子可以在评论中运行，以供说明。）

问题

_上面的定义中有一个fixpM。这是一个类型的函数[m a] -> [m a]，原则上应该与上面的函数相同converge，但有点提升。我开始怀疑它不能写。

我确实为以下内容编写了另一个专门的代码fixpM：

fixpM :: (Eq a, Monad m) => (a -> m a) -> a -> m a
fixpM f x = do
    y <- f x
    if x == y
        then return x
        else fixpM f y

-- \ fixpM (\x -> (".", x^2)) 0.5
-- ("............",0.0)

（再次，在评论中找到了一个示例运行。）

-- 但它是一个完全不同的算法，而不是我们开始使用的纯函数的扩展/概括。特别是，我们没有通过提供inits最多第一次重复的列表的阶段。

我们不能扩展纯算法来处理一元函数吗？

为什么会这样？

我很欣赏一个解释如何证明不可能或以常规方式构建解决方案的理论的提示，但这也许只是我在忙于输入闲置问题时遗漏的琐事，在这种情况下，一个简单的反例将打败我。

PS我知道这是一个有点微不足道的练习。尽管如此，我还是想一劳永逸地完成它。

PS 2正如@nm (retaining iterate) 所建议的，对纯变体的更好近似如下所示：

fixpM :: (Eq a, Monad m) => (m a -> m a) -> m a -> m a
fixpM f = collapse . iterate f
  where
    collapse (mx: mxs @(my: _)) = do
        x <- mx
        y <- my
        if x == y
            then return x
            else collapse mxs

通过使用iterate，它关于 monad 的行为是不同的，因为在连续近似之间保留了效果。在性能方面，这些功能具有相同的复杂性。

PS 3对@nm 提供的想法的更完整的诠释，据我所知，与纯变体一对一地对算法进行了编码：

fixpM :: (Eq a, Monad m) => (m a -> m a) -> m a -> m a
fixpM f = lastM . convergeM . iterate (f >>= \x -> return x )

convergeM :: (Monad m, Eq a) => [m a] -> m [a]
convergeM = convergeByM (==)

convergeByM :: (Monad m, Eq a) => (a -> a -> Bool) -> [m a] -> m [a]
convergeByM _ [ ] = return [ ]
convergeByM _ [mx] = mx >>= \x -> return [x]
convergeByM eq xs = do
    case xs of
        [ ] -> return [ ]
        [mx] -> mx >>= \x -> return [x]
        (mx: mxs @(my: _)) -> do
            x <- mx
            y <- my
            if x `eq` y
                then return [x]
                else do
                    xs <- convergeM mxs
                    return (x:xs)

lastM :: Monad m => m [a] -> m a
lastM mxs = mxs >>= \xs -> case xs of
    [] -> error "Fix.lastM: No last element!"
    xs -> return . head . reverse $ xs

不幸的是，它恰好是相当长的。更重要的是，这两种解决方案在 monad 的影响方面都具有相同的不太理想的行为：所有影响都保留在连续近似之间。

4

0 回答 0