фиксированная точка для fix :: Eq a => (a -> a) -> a -> a

Question

Привет всем, я пытаюсь реализовать исправление функции высшего порядка, которое вычисляет привлекательную фиксированную точку произвольной функции f :: a -> a из начальной точки x.То есть фиксированная точка вида fᴷ(x) для заданных f и x.

-- CONTRACT
fix :: Eq a => (a -> a) -> a -> a
-- DEFINITION [TODO: Implement fix]
fix f x  = ?

Моя текущая попытка:

fix f x | f x == x = x
        | otherwise = fix f x
    where x = f x

Примечание. Ваша функция не прекратит работу, если функция не сходится от начальной точки .Может кто-то помочь мне, пожалуйста ?Я пытался, но ничего не получилось

Answer 1

Дайте другое имя для следующего шага итерации, например:

where x' = f x

(вместо where x = f x).Теперь просмотрите оставшуюся часть существующего кода и для каждого случая x спросите себя: имел ли я в виду x здесь или x'?

Answer 2

У вас уже есть ответы на то, как написать fix с нуля.Если вы хотите попробовать его, используя некоторые стандартные функции Haskell, я предлагаю вам взглянуть на функцию until.

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

Обратите внимание, тип until довольно похож на тот, который вам нужен.Требуется только один дополнительный аргумент вида a -> Bool.Выражение until p f x итеративно применяет f, начиная с начальной точки x, пока не будет выполнено некоторое условие p.И вы легко сможете написать fix в виде

fix = until p 

для некоторой функции p :: a -> Bool.Теперь вам просто нужно реализовать это условие остановки p, которое проверяет, является ли вычисленная вами точка y фиксированной точкой f, то есть если f y == y.

Answer 3

Распространенным заблуждением является то, что когда вы пишете x = ..., вы присваиваете значение в Haskell.В Haskell каждый не присваивает значение, один объявляет один.

Таким образом, это означает, что в основном вы создали переменную x в предложении where, которое не x в заголовке функции, поэтому что-то вроде:

fix :: Eq a => (a -> a) -> a -> a
fix f _ | f x == x = x
        | otherwise = fix f x
    where x = f x

Здесь вы таким образом определили x в терминах самого себя: x = f x, так чтоозначает, что если Haskell попытается оценить это, он начнет вычислять f(f(f(f(f(f(...)))))), но без каких-либо проверок, если достигнута фиксированная точка .

Таким образом, решение состоит в том, чтобы ввести новую переменную,например x2, и, таким образом, используйте это как:

fix :: Eq a => (a -> a) -> a -> a
fix f x | x == <b>x2</b> = x
        | otherwise = fix f <b>x2</b>
    where <b>x2</b> = f x

Так что здесь x2 является следующим x.Учитывая x == x2, мы возвращаем x (или x2), если нет, мы вычисляем фиксированную точку f и x2, поэтому мы продвинулись на один шаг в квесте " для фиксированной точки».