Haskell 中的定点组合器

发布于 2024-12-15 14:43:26 字数 395 浏览 0 评论 0原文

给定定义，定点组合器并不总是产生正确的答案：

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 个参数的函数）的原因是什么？

原文

The fixed point combinator doesn't always produce the right answer given the definition:

fix f = f (fix f)

The following code does not terminate:

fix (\x->x*x) 0

Of course, fix can't always produce the right answer, but I was wondering, can this be improved?

Certainly for the above example, one can implement some fix that looks like

fix f x | f x == f (f x)  = f x
        | otherwise       = fix f (f x)

and gives the correct output.

What is the reason the above definition (or something even better, as this one only handle function with 1 parameter) is not used instead?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不奢求什么 2024-12-22 14:43:26

定点组合器找到函数的最小定义的定点，在您的情况下是 ⊥ （非终止确实是未定义的值）。

您可以检查，在您的情况下

(\x -> x * x) ⊥ = ⊥

，即 ⊥ 确实是 \x -> 的固定点x * x。

至于为什么fix这么定义：fix的要点是允许你使用匿名递归，为此您不需要更复杂的定义。

Fixed point combinator finds the least-defined fixed point of a function, which is ⊥ in your case (non-termination indeed is undefined value).

You can check, that in your case

(\x -> x * x) ⊥ = ⊥

i.e. ⊥ really is fixed point of \x -> x * x.

As for why is fix defined that way: the main point of fix is to allow you use anonymous recursion and for that you do not need more sophisticated definition.

回复收藏 0 原文

一场信仰旅途 2024-12-22 14:43:26

您的示例甚至没有进行类型检查：

Prelude> fix (\x->x*x) 0

<interactive>:1:11:
    No instance for (Num (a0 -> t0))
      arising from a use of `*'
    Possible fix: add an instance declaration for (Num (a0 -> t0))
    In the expression: x * x
    In the first argument of `fix', namely `(\ x -> x * x)'
    In the expression: fix (\ x -> x * x) 0

这给出了为什么它不能按您的预期工作的线索。匿名函数中的 x 应该是一个函数，而不是一个数字。正如 Vitus 所言，其原因在于，定点组合器是一种无需实际编写递归即可编写递归的方法。一般的想法是，像这样的递归定义

f x = if x == 0 then 1 else x * f (x-1)

可以写成

f    = fix (\f' x -> if x == 0  then 1 else x * f' (x-1))

您的示例

fix (\x->x*x) 0

表达式。

let x = x*x in x 0

，因此对应于没有意义的

Your example does not even typecheck:

Prelude> fix (\x->x*x) 0

<interactive>:1:11:
    No instance for (Num (a0 -> t0))
      arising from a use of `*'
    Possible fix: add an instance declaration for (Num (a0 -> t0))
    In the expression: x * x
    In the first argument of `fix', namely `(\ x -> x * x)'
    In the expression: fix (\ x -> x * x) 0

And that gives the clue as to why it doesn't work as you expect. The x in your anonymous function is supposed to be a function, not a number. The reason for this is, as Vitus suggests, that a fixpoint combinator is a way to write recursion without actually writing recursion. The general idea is that a recursive definition like

f x = if x == 0 then 1 else x * f (x-1)

can be written as

f    = fix (\f' x -> if x == 0  then 1 else x * f' (x-1))

Your example

fix (\x->x*x) 0

thus corresponds to the expression

let x = x*x in x 0

which makes no sense.

回复收藏 0 原文

坚持沉默 2024-12-22 14:43:26

我不完全有资格谈论什么是“定点组合器”，或者什么是“最小定点”，但是可以使用 fix 式的技术来近似某些功能。

将 Scala 示例第 4.4 节翻译为 Haskell：

sqrt' :: Double -> Double
sqrt' x = sqrtIter 1.0
  where sqrtIter guess | isGoodEnough guess = guess
                       | otherwise          = sqrtIter (improve guess)
        improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

该函数通过重复“改进”猜测，直到我们确定它“足够好”。这种模式可以被抽象：

myFix :: (a -> a)       -- "improve" the guess
      -> (a -> Bool)    -- determine if a guess is "good enough"
      -> a              -- starting guess
      -> a
fixApprox improve isGoodEnough startGuess = iter startGuess
  where iter guess | isGoodEnough guess = guess
                   | otherwise          = iter (improve guess)

sqrt'' :: Double -> Double
sqrt'' x = myFix improve isGoodEnough 1.0
  where improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

另请参见 Scala by Example 第 5.3 节。 fixApprox 可用于近似传入其中的 improve 函数的固定点。它在输入上重复调用improve，直到输出isGoodEnough。

事实上，您不仅可以使用 myFix 来获取近似值，还可以使用它来获取精确答案。

primeAfter :: Int -> Int
primeAfter n = myFix improve isPrime (succ n)
  where improve = succ
        isPrime x = null [z | z <- [2..pred x], x `rem` z == 0]

这是一种非常愚蠢的生成素数的方法，但它说明了这一点。嗯...现在我想知道...类似 myFix 的东西是否已经存在？停止...胡格尔时间！

诈骗 (a -> a) -> (a -> 布尔值) ->一个-> a，第一个命中是until。

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

好吧，你已经有了。事实证明，myFix = 翻转直到。

I'm not entirely qualified to talk about what the "fixpoint combinator" is, or what the "least fixed point" is, but it is possible to use a fix-esque technique to approximate certain functions.

Translating Scala by Example section 4.4 to Haskell:

sqrt' :: Double -> Double
sqrt' x = sqrtIter 1.0
  where sqrtIter guess | isGoodEnough guess = guess
                       | otherwise          = sqrtIter (improve guess)
        improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

This function works by repeatedly "improving" a guess until we determine that it is "good enough". This pattern can be abstracted:

myFix :: (a -> a)       -- "improve" the guess
      -> (a -> Bool)    -- determine if a guess is "good enough"
      -> a              -- starting guess
      -> a
fixApprox improve isGoodEnough startGuess = iter startGuess
  where iter guess | isGoodEnough guess = guess
                   | otherwise          = iter (improve guess)

sqrt'' :: Double -> Double
sqrt'' x = myFix improve isGoodEnough 1.0
  where improve guess = (guess + x / guess) / 2
        isGoodEnough guess = abs (guess * guess - x) < 0.001

See also Scala by Example section 5.3. fixApprox can be used to approximate the fixed point of the improve function passed into it. It repeatedly invokes improve on the input until the output isGoodEnough.

In fact, you can use myFix not only for approximations, but for exact answers as well.

primeAfter :: Int -> Int
primeAfter n = myFix improve isPrime (succ n)
  where improve = succ
        isPrime x = null [z | z <- [2..pred x], x `rem` z == 0]

This is a pretty dumb way to generate primes, but it illustrates the point. Hm...now I wonder...does something like myFix already exist? Stop...Hoogle time!

Hoogling (a -> a) -> (a -> Bool) -> a -> a, the very first hit is until.

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

Well there you have it. As it turns out, myFix = flip until.

回复收藏 0 原文

献世佛 2024-12-22 14:43:26

您可能指的是迭代：

*Main> take 8 $ iterate (^2) (0.0 ::Float)
[0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> take 8 $ iterate (^2) (0.001 ::Float)
[1.0e-3,1.0000001e-6,1.0000002e-12,1.0000004e-24,0.0,0.0,0.0,0.0]

*Main> take 8 $ iterate (^2) (0.999 ::Float)
[0.999,0.99800104,0.9960061,0.9920281,0.9841198,0.96849173,0.93797624,0.8797994]
*Main> take 8 $ iterate (^2) (1.0 ::Float)
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> take 8 $ iterate (^2) (1.001 ::Float)
[1.001,1.002001,1.0040061,1.0080284,1.0161213,1.0325024,1.0660613,1.1364866]

这里您拥有明确可用于分析的所有执行历史记录。检测固定点

fixed f from = snd . head 
                   . until ((< 1e-16).abs.uncurry (-).head) tail 
               $ _S zip tail history
  where history = iterate f from
        _S f g x = f x (g x)

您可以尝试使用然后

*Main> fixed (^2) (0.999 :: Float)
0.0

，但是尝试fixed (^2) (1.001 :: Float)将无限循环，因此您需要开发单独的测试收敛性，即使如此，检测像 1.0 这样的排斥固定点也需要更详细的研究。

You probably meant iterate:

*Main> take 8 $ iterate (^2) (0.0 ::Float)
[0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
*Main> take 8 $ iterate (^2) (0.001 ::Float)
[1.0e-3,1.0000001e-6,1.0000002e-12,1.0000004e-24,0.0,0.0,0.0,0.0]

*Main> take 8 $ iterate (^2) (0.999 ::Float)
[0.999,0.99800104,0.9960061,0.9920281,0.9841198,0.96849173,0.93797624,0.8797994]
*Main> take 8 $ iterate (^2) (1.0 ::Float)
[1.0,1.0,1.0,1.0,1.0,1.0,1.0,1.0]
*Main> take 8 $ iterate (^2) (1.001 ::Float)
[1.001,1.002001,1.0040061,1.0080284,1.0161213,1.0325024,1.0660613,1.1364866]

Here you have all the execution history explicitly available for your analysis. You can attempt to detect the fixed point with

fixed f from = snd . head 
                   . until ((< 1e-16).abs.uncurry (-).head) tail 
               $ _S zip tail history
  where history = iterate f from
        _S f g x = f x (g x)

and then

*Main> fixed (^2) (0.999 :: Float)
0.0

but trying fixed (^2) (1.001 :: Float) will loop indefinitely, so you'd need to develop separate testing for convergence, and even then detection of repellent fixed points like 1.0 will need more elaborate investigation.

回复收藏 0 原文

关于从前 2024-12-22 14:43:26

您无法按照您提到的方式定义 fix ，因为 f x 甚至可能无法比较。例如，考虑下面的例子：

myFix f x | f x == f (f x)  = f x
          | otherwise       = myFix f (f x)

addG f a b =
  if a == 0 then
    b
  else
    f (a - 1) (b + 1)

add = fix addG -- Works as expected.
-- addM = myFix addG (Compile error)

You can't define fix the way you've mentioned since f x may not even be comparable. For instance, consider the example below:

myFix f x | f x == f (f x)  = f x
          | otherwise       = myFix f (f x)

addG f a b =
  if a == 0 then
    b
  else
    f (a - 1) (b + 1)

add = fix addG -- Works as expected.
-- addM = myFix addG (Compile error)

回复收藏 0 原文

~没有更多了~