Как я могу использовать fix, и как это работает?

я не утверждаю, что понимаю это вообще, но если это кому-то поможет...потом ура.

рассмотрим определение fix. fix f = let x = f x in x. Умопомрачительная часть заключается в том, что x определяется как f x. Но подумайте об этом на минутку.

x = f x

так как x = f x, то мы можем подставить значение x на правой стороне, верно? Поэтому...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

так что фокус в том, чтобы закончить,f нужно сгенерировать вид структуры, так что позже f может ли шаблон соответствовать этой структуре и завершить рекурсию, фактически не заботясь о полном "значении" своего параметра (?)

если, конечно, вы не хотите сделать что-то вроде создания бесконечного списка, как проиллюстрировал лукви.

факторное объяснение Томмда хорошо. Подпись типа ремонта составляет (a -> a) -> a. Подпись типа для (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) и (b -> b) -> b -> b иными словами, (b -> b) -> (b -> b). Так что можно сказать, что a = (b -> b). Таким образом, исправить принимает нашу функцию, которая a -> a, или действительно, (b -> b) -> (b -> b), и вернет результат типа a иными словами, b -> b, другими словами, другая функция!

Подождите, я думал, что он должен был вернуть фиксированную точку...это не функция. Ну это так, вроде (так как функции-это данные). Вы можете себе представить, что это дало нам окончательную функцию для нахождения факториала. Мы дали ему функцию, которая не знает, как рекурсировать (следовательно, один из параметров к ней является функцией, используемой рекурсивно), и fix научил ее повторить.

помните, как я сказал, что f должен генерировать какую-то структуру, чтобы позже f может ли шаблон совпадать и завершаться? Ну, это не совсем так, я думаю. TomMD проиллюстрировал, как мы можем расширить x чтобы применить функцию и шаг к базовому случаю. Для своей функции он использовал if / then, и это то, что вызывает прекращение. После повторных замен,in часть всего определения fix в конечном итоге перестает определяться в терминах x и это когда он вычислим и полон.

вам нужен способ для завершения точки фиксации. Расширение вашего примера очевидно, что он не закончит:

fix id
--> let x = id x in x
--> id x
--> id (id x)
--> id (id (id x))
--> ...

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

(fix (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, вы говорите! Ну, да, но здесь есть несколько действительно полезных моментов. Прежде всего, ваш первый fix аргумент должен быть функцией, которая в случае 'рекурсия' и второй аргумент-это данные, по которым действовать. Вот тот же код, что и именованная функция:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

если вы все еще смущены, то, возможно, факториал будет более простым примером:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

обратите внимание на оценки:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

О, ты видел это? Это x стал функцией внутри нашего then филиала.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

выше вы должны помнить x = f x, отсюда два аргумента x 2 в конце вместо просто 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

и я остановлюсь здесь!

одно четкое определение вы могли бы повторно изобрели исправить тоже!

как я понимаю, он находит значение для функции, так что он выводит то же самое, что вы ему даете. Уловка заключается в том, что он всегда будет выбирать неопределенный (или бесконечный цикл, в haskell, неопределенные и бесконечные циклы одинаковы) или то, что имеет в нем самые неопределенные. Например, с id,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

как вы можете видеть, undefined является фиксированной точкой, поэтому fix вернусь к этому. Если вы вместо этого делаете (\x - >1: x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

так fix не могу выбрать неопределенным. Чтобы сделать его немного более связанным с бесконечными циклами.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

опять же, небольшая разница. Так что же такое фиксированная точка? Давайте попробуем repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

это то же самое! Так как это единственная неподвижная точка,fix должен остановиться на нем. Извините fix, никаких бесконечных циклов или неопределенных для вас.