Функция точки фиксации не находит мою точку фиксации

Чтобы понять функцию fix из Control.Monad.State, fix :: (a -> a) -> a, у меня есть этот небольшой код в modifyValue, который увеличивает целое число до 49, тогда функция всегда возвращает 50.

import Control.Monad.State
type StateVal = Int

modifyValue :: StateVal -> StateVal
modifyValue v | v < 50 = v + 1
modifyValue v = 50

simpleStateStep :: State StateVal ()
simpleStateStep = do
        s <- get
        put $ modifyValue s

main = do
    putStrLn $ show $ fix modifyValue

Однако, когда я запускаю этот код, вместо того, чтобы найти точку фиксации на 50, где последовательность сходится к 50 ... он утверждает *** Exception: <<loop>>

Понятно, что я что-то ошибаюсь, поскольку я не указываю начальное состояние для запуска последовательности, например, с 1, которое могло бы сгенерировать [2,3,4,..,49,50,50,50,50....]

Я неправильно использую функцию исправления? Есть что-то сделать, чтобы он нашел точку фиксации 50?


person Stephane Rolland    schedule 04.05.2016    source источник
comment
c.f. stackoverflow.com/q/4787421/356440   -  person Stephane Rolland    schedule 18.02.2017
comment
Формально fix возвращает наименее определенную фиксированную точку функции. 50 является фиксированной точкой, но undefined - тоже: modifyValue undefined дает undefined. И поскольку undefined менее определен, чем 50, возвращается именно это. fix полезен только для функций, не имеющих undefined в качестве фиксированной точки.   -  person melpomene    schedule 15.07.2019


Ответы (1)


ну fix определяется примерно так:

fix f = let x = f x in x

так что хорошо генерировать рекурсию для ленивых структур данных

fix (1:) == 1:1:1:1:....

который отлично работает, поскольку список ленив (так что take 10 $ fix (1:) отлично)

Это не очень хорошо для извлечения строгого значения из рекурсивной функции, подобной вашей.

Потому что, как только вы захотите распечатать / оценить его, вам нужно придумать значение, и это закончится бесконечным циклом.

Вам, вероятно, понадобится что-то вроде

fixEq f x = let x' = f x in if x' == x then x else fixEq f x'
person Random Dev    schedule 04.05.2016