Haskell中有不动点运算符吗？

Question

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

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

所以我想知道是否有内置的或更通用的东西？

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

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

我在谷歌搜索时遇到了问题，因为我只在我的搜索词包含 fixed point 或类似内容时才找到对 fix 函数的引用。

Answer 1

自己写吧。直接版本将比使用 dropWhile.

的版本更快

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

Answer 2

您的函数具有签名 Eq a => (a -> a) -> a -> a。

Using hoogle to search for that，我没有看到任何完全匹配项。最接近的匹配项是 until

until :: (a -> Bool) -> (a -> a) -> a -> a

base Prelude

until p f yields the result of applying f until p holds.

您可能会使用它来编写您的函数，但因为您需要 /=，所以您需要 Eq 约束。

Answer 3

如果你正在寻找一个内置的，因为你想要一个没有任何辅助函数的简短表达式，我可以推荐

until=<<((==)=<<) :: Eq a => (a -> a) -> a -> a

可以说这看起来有点奇怪，但实际上它只是无点等价于until (\x -> f x == x) f，利用f (g x) x可以被(f=<<g) x表达两次的事实。

Is there a fixed point operator in Haskell?