Комбинатор с фиксированной точкой в ​​Haskell

Question

Комбинатор с фиксированной точкой не всегда дает правильный ответ, учитывая определение:

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)

и дает правильный вывод.

По какой причине вышеприведенное определение (или что-то еще лучше, поскольку эта единственная функция обработки с одним параметром) не используется вместо этого?

Answer 1

Комбинатор с фиксированной точкой находит наименее определенную фиксированную точку функции, которая в вашем случае равна ((недопущение действительно является неопределенным значением).

Вы можете проверить, что в вашем случае

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

т.е. ⊥ действительно является фиксированной точкой \x -> x * x.

Что касается того, почему fix определено таким образом: основной смысл fix - позволить вам использовать анонимную рекурсию , и для этого вам не нужно более сложное определение.

Answer 2

Ваш пример даже не проверяет тип:

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 в вашей анонимной функции должна быть функцией, а не числом. Причина этого в том, что, как полагает Витус, комбинатор с фиксированной точкой - это способ написать рекурсию без фактической записи рекурсии. Общая идея заключается в том, что рекурсивное определение типа

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

что не имеет смысла.

Answer 3

Я не совсем квалифицирован, чтобы говорить о том, что такое «комбинатор с фиксированной точкой», или что такое «наименее фиксированная точка», но можно использовать метод fix -esque для приблизительного определенные функции.

Перевод 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 -> Bool) -> a -> a, самый первый удар - until.

until p f возвращает результат применения f до тех пор, пока не будет выполнено p.

Ну, вот и все. Оказывается, myFix = flip until.

Answer 4

Вы, вероятно, имели в виду 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]

Здесь у вас есть вся история выполнения, явно доступная для вашего анализа. Вы можете попытаться обнаружить фиксированную точку с помощью

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, потребует более тщательного изучения.

Answer 5

Вы не можете определить 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)