developer tip

수정 사항은 어떻게 사용하고 어떻게 작동합니까?

copycodes 2020. 9. 25. 07:59
반응형

수정 사항은 어떻게 사용하고 어떻게 작동합니까?


문서에 대해 약간 혼란스러워서 fix(지금해야 할 일을 이해한다고 생각하지만) 소스 코드를 살펴 보았습니다. 그로 인해 더 혼란스러워졌습니다.

fix :: (a -> a) -> a
fix f = let x = f x in x

고정 소수점을 정확히 반환하는 방법은 무엇입니까?

명령 줄에서 시도해보기로했습니다.

Prelude Data.Function> fix id
...

그리고 그것은 거기에 달려 있습니다. 이제 공정하게 말하면, 이것은 약간 느린 내 오래된 맥북에 있습니다. 그러나이 함수는 id에 전달 된 모든 것이 동일한 것을 되돌려주기 때문에 계산적 으로 너무 비쌀 수는 없습니다 (CPU 시간을 소모하지 않는다는 것은 말할 것도 없습니다). 내가 뭘 잘못하고 있죠?


당신은 잘못한 것이 없습니다. fix id무한 루프입니다.

이것이 fix함수의 최소 고정 점 반환 한다고 말할 때 우리 도메인 이론의 의미에서 의미합니다. 그래서 fix (\x -> 2*x-1)되어 있지 반환하려고 1하지만 때문에, 1그 함수의 고정 된 지점입니다, 그것은 아닌 이상 도메인 주문 하나.

도메인 순서를 한두 단락으로 설명 할 수 없으므로 위의 도메인 이론 링크를 참조하겠습니다. 읽기 쉽고 깨달음을주는 훌륭한 튜토리얼입니다. 나는 그것을 적극 추천합니다.

10,000 피트에서보기 fix의 경우 재귀 개념을 인코딩하는 고차 함수입니다 . 표현식이있는 경우 :

let x = 1:x in x

무한 목록이되는 결과는 다음을 [1,1..]사용하여 같은 말을 할 수 있습니다 fix.

fix (\x -> 1:x)

(또는 간단히 fix (1:)), 나에게 고정 된 지점 찾기라고하는 (1:)기능을 IOW는 값이 x되도록 x = 1:x처럼 우리는 위의 정의 .... 정의에서 알 수 있듯이, fix이 아이디어에 지나지 않습니다. 함수로 캡슐화 된 재귀입니다.

이것은 재귀의 진정한 일반 개념이기도 합니다. 다형성 재귀를 사용하는 함수를 포함하여 모든 재귀 함수를 이런 방식으로 작성할 수 있습니다 . 예를 들어 전형적인 피보나치 함수는 다음과 같습니다.

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

다음과 같이 쓸 수 있습니다 fix.

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

연습 :의 정의를 확장하여이 fix두 정의 fib가 동일 함 을 보여줍니다 .

그러나 완전한 이해를 위해 영역 이론에 대해 읽어보십시오. 정말 멋진 것입니다.


나는 이것을 전혀 이해한다고 주장하지 않지만 이것이 누군가에게 도움이된다면 ...

의 정의를 고려하십시오 fix. fix f = let x = f x in x. 마음 불허 부분이 있다는 것입니다 x으로 정의된다 f x. 그러나 잠시 생각해보십시오.

x = f x

x = fx이므로 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매개 변수 (?)의 전체 "값"에 대해 신경 쓰지 않고 해당 구조와 패턴을 일치시키고 재귀를 종료 할 수 있습니다.

물론 luqui가 설명하는 것처럼 무한 목록을 만드는 것과 같은 작업을 수행하고 싶지 않은 한.

TomMD의 계승 설명이 좋습니다. 수정의 유형 서명은 (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 (\f h -> if (pred h) then f (mutate h) else h)) q

WTF, you say! Well, yes, but there are a few really useful points here. First of all, your first fix argument should usually be a function which is the 'recurse' case and the second argument is the data on which to act. Here is the same code as a named function:

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

If you're still confused then perhaps factorial will be an easier example:

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

Notice the evaluation:

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

Oh, did you just see that? That x became a function inside our then branch.

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 -->

In the above you need to remember x = f x, hence the two arguments of x 2 at the end instead of just 2.

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

And I'll stop here!


How I understand it is, it finds a value for the function, such that it outputs the same thing you give it. The catch is, it will always choose undefined (or an infinite loop, in haskell, undefined and infinite loops are the same) or whatever has the most undefineds in it. For example, with id,

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

As you can see, undefined is a fixed point, so fix will pick that. If you instead do (\x->1:x).

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

So fix can't pick undefined. To make it a bit more connected to infinite loops.

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

Again, a slight difference. So what is the fixed point? Let us try 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

It is the same! Since this is the only fixed point, fix must settle on it. Sorry fix, no infinite loops or undefined for you.

참고URL : https://stackoverflow.com/questions/4787421/how-do-i-use-fix-and-how-does-it-work

반응형