Haskell中是否有固定点运算符？

Question

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

我认为这是一个非常普遍的概念，所以我想可能有内置函数可以实现这个功能。

因此，我想知道是否有内置函数可以实现这个功能或者更通用的方法？

基本上，我正在寻找这个：

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

我刚刚在谷歌搜索时遇到了困难，因为只有当我的搜索词包含fixed point或类似内容时，才会找到fix函数的参考信息。

- flawr

---

ghci 表示该函数的类型为 Eq a => (a -> a) -> a -> a。对于该签名，Hoogle 似乎没有返回有用的结果。 - Daenyth

最接近的是 until :: (a -> Bool) -> (a -> a) -> a -> a。until p f 产生应用 f 直到 p 成立的结果。似乎你可以使用它编写你的函数，但仍需要 Eq 约束。 - Daenyth

@Daenyth 谢谢，我不知道你可以这样使用hoogle =) 如果你把它作为答案添加，我会接受的。 - flawr

Answer 1

自己编写代码会比使用dropWhile更快。

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

- dfeuer

---

我知道有很多方法可以做到这一点，但我特别想要一个内置的方法，因为我认为它是一个非常常用的函数。 - flawr

@flawr，我认为这并不是特别常见的。until似乎最接近，但实际上为了这个目的使用它比它值得的麻烦多了。 - dfeuer

Answer 2

你的函数签名为Eq a => (a -> a) -> a -> a。

使用 hoogle 搜索该函数，我没有看到任何精确匹配。最接近的匹配是until。

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

base Prelude

until p f产生应用f直到p成立的结果。

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

- Daenyth

---

你可以使用until与pairs，但我认为手动完成整个过程更简单。 - dfeuer

请编写自己的 last . takeWhileDifferent 变体或类似的代码，例如 last . takeWhileDifferent . iterate f。takeWhileDifferent 的实现可以在以下链接中找到：https://github.com/ekmett/ad/blob/ac5e0c7091430d0c569ba893f78385ead70b918e/src/Numeric/AD/Internal/Combinators.hs#L51 - phadej

Answer 3

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

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

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

- Laikoni