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

Ответ 1

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

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

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

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

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

Ответ 2

В вашем примере нет даже 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

И это дает понять, почему он не работает так, как вы ожидаете. 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

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

Ответ 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 в разделе 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 уже существует? Остановитесь... Время Google!

Hoogling (a -> a) -> (a -> Bool) -> a -> a, самый первый удар - until.

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

Хорошо, у вас это есть. Как оказалось, myFix = flip until.

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

Ответ 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)