약한 머리 보통 양식은 무엇입니까?

약한 머리 보통 양식은 무엇입니까?

---

어떻게합니까 약한 헤드 정규형 (WHNF) 평균? 무엇합니까 헤드 일반 양식 (HNF)과 정규형 (NF) 평균?

실제 하스켈 주 :

익숙한 seq 함수는 head normal 형식 (약어 HNF)에 대한 표현식을 평가합니다. 가장 바깥 쪽 생성자 ( "헤드")에 도달하면 중지됩니다. 이는 정규식 (NF)과 다르며식이 완전히 평가됩니다.

또한 Haskell 프로그래머가 약한 헤드 정상 형식 (WHNF)을 말하는 것을들을 수 있습니다. 일반 데이터의 경우 약한 헤드 정규 형식은 헤드 일반 형식과 동일합니다. 차이점은 기능에 대해서만 발생하며 여기에서 우리를 걱정하기에는 너무 모호합니다.

몇 가지 리소스와 정의 ( Haskell Wiki 및 Haskell Mail List 및 Free Dictionary )를 읽었 지만 얻지 못했습니다. 누군가 예를 들어 설명하거나 평신도 정의를 제공 할 수 있습니까?

나는 그것이 다음과 비슷할 것이라고 추측하고있다 :

WHNF = thunk : thunk

HNF = 0 : thunk 

NF = 0 : 1 : 2 : 3 : []

어떻게 seq및 ($!)WHNF 및 HNF 관련?

최신 정보

여전히 혼란 스러워요. 나는 HNF를 무시한다고 대답하는 답변을 알고 있습니다. 다양한 정의를 읽음으로써 WHNF와 HNF의 정규 데이터간에 차이가없는 것 같습니다. 그러나 기능과 관련하여 차이가있는 것처럼 보입니다. 차이가 없다면 왜 seq필요한가 foldl'?

혼돈의 또 다른 지점은 seqWHNF로 축소 되는 Haskell Wiki의 것이며, 다음 예제에는 아무런 영향을 미치지 않습니다. 그리고 나서 그들은 seq평가를 강요 하기 위해 사용해야한다고 말합니다 . 그것이 HNF에 강요되지 않습니까?

일반적인 초보자 스택 넘침 코드 :

myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)

seq와 약한 머리 정상형 (whnf)을 이해하는 사람들은 여기서 무엇이 잘못되었는지 즉시 이해할 수 있습니다. (acc + x, len + 1)은 이미 whnf에 있으므로 값을 whnf로 줄이는 seq는이 작업을 수행하지 않습니다. 이 코드는 원래 foldl 예제와 같이 썽크를 생성합니다. 튜플 안에있을뿐입니다. 해결책은 튜플의 구성 요소를 강제하는 것입니다.

myAverage = uncurry (/) . foldl' 
          (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)

- 유래에 하스켈 위키

---

간단한 용어로 설명하려고합니다. 다른 사람들이 지적했듯이, 머리 정상적인 형태는 Haskell에 적용되지 않으므로 여기서는 고려하지 않을 것입니다.

정상적인 형태

정상 형태의 표현은 완전히 평가되며, 하위 표현은 더 이상 평가 될 수 없습니다 (즉, 평가되지 않은 썽크를 포함하지 않음).

이러한 표현은 모두 정상적인 형태입니다.

42
(2, "hello")
\x -> (x + 1)

이 표현들은 정상적인 형태가 아닙니다 :

1 + 2                 -- we could evaluate this to 3
(\x -> x + 1) 2       -- we could apply the function
"he" ++ "llo"         -- we could apply the (++)
(1 + 1, 2 + 2)        -- we could evaluate 1 + 1 and 2 + 2

약한 머리 보통 형태

약한 머리 정규 형식의 표현은 가장 바깥 쪽 데이터 생성자 또는 람다 추상화 ( head ) 로 평가되었습니다 . 하위 표현 은 평가되거나 평가되지 않았을 수 있습니다 . 따라서, 모든 정규 형식 표현은 약한 머리 정규 형식이지만, 그 반대는 일반적으로 적용되지 않습니다.

표현이 약한 머리 정규 형식인지 여부를 확인하려면 식의 가장 바깥 쪽 부분 만 살펴 봐야합니다. 데이터 생성자 또는 람다 인 경우 머리가 약한 정상적인 형태입니다. 함수 응용 프로그램 인 경우 그렇지 않습니다.

이 표현들은 약한 머리 정상적인 형태입니다 :

(1 + 1, 2 + 2)       -- the outermost part is the data constructor (,)
\x -> 2 + 2          -- the outermost part is a lambda abstraction
'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)

언급 한 바와 같이, 위에 열거 된 모든 정규형 표현은 또한 약한 머리 정규형입니다.

이 표현들은 약한 머리 정상적인 형태가 아닙니다 :

1 + 2                -- the outermost part here is an application of (+)
(\x -> x + 1) 2      -- the outermost part is an application of (\x -> x + 1)
"he" ++ "llo"        -- the outermost part is an application of (++)

스택 오버플로

약한 머리 정규형으로 표현을 평가하려면 먼저 다른 표현을 WHNF로 평가해야합니다. 예를 들어 1 + (2 + 3)WHNF 로 평가 하려면 먼저 평가해야합니다 2 + 3. 단일 표현식을 평가하면 이러한 중첩 평가가 너무 많이 발생하면 스택 오버플로가 발생합니다.

이는 많은 부분이 평가 될 때까지 데이터 생성 자나 람다를 생성하지 않는 큰 식을 작성할 때 발생합니다. 이들은 종종 이런 종류의 사용으로 인해 발생합니다 foldl.

foldl (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl (+) (0 + 1) [2, 3, 4, 5, 6]
 = foldl (+) ((0 + 1) + 2) [3, 4, 5, 6]
 = foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6]
 = foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6]
 = foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6]
 = foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) []
 = (((((0 + 1) + 2) + 3) + 4) + 5) + 6
 = ((((1 + 2) + 3) + 4) + 5) + 6
 = (((3 + 3) + 4) + 5) + 6
 = ((6 + 4) + 5) + 6
 = (10 + 5) + 6
 = 15 + 6
 = 21

그것이 머리가 약한 정상 형태로 표현되기 전에 어떻게 깊이 들어가야하는지 주목하십시오.

왜 하스켈이 미리 내면의 표현을 줄이지 않습니까? 그것은 하스켈의 게으름 때문입니다. 일반적으로 모든 하위 표현식이 필요하다고 가정 할 수 없으므로 외부에서 표현식을 평가합니다.

(GHC에는 하위 분석기가 항상 필요한 일부 상황을 감지하여 미리 평가할 수있는 엄격 성 분석기가 있습니다. 그러나 최적화 일 뿐이므로 오버플로를 막기 위해 의존해서는 안됩니다.)

반면에 이런 종류의 표현은 완전히 안전합니다.

data List a = Cons a (List a) | Nil
foldr Cons Nil [1, 2, 3, 4, 5, 6]
 = Cons 1 (foldr Cons Nil [2, 3, 4, 5, 6])  -- Cons is a constructor, stop. 

모든 하위 표현식을 평가해야한다는 것을 알 때 이러한 큰 표현식을 작성하지 않으려면 내부 부분을 미리 평가해야합니다.

seq

seq식을 강제로 평가하는 데 사용되는 특수 함수입니다. 그 의미는 약한 머리 정상 형태로 평가 seq x y될 때마다 y약한 머리 정상 형태로 평가됨을 의미합니다 x.

의 정의에 사용 된 다른 위치는 foldl'의 엄격한 변형입니다 foldl.

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

반복 할 때마다 foldl'누산기가 WHNF로 강제 설정됩니다. 따라서 큰 식을 작성하지 않으므로 스택 오버플로를 피할 수 있습니다.

foldl' (+) 0 [1, 2, 3, 4, 5, 6]
 = foldl' (+) 1 [2, 3, 4, 5, 6]
 = foldl' (+) 3 [3, 4, 5, 6]
 = foldl' (+) 6 [4, 5, 6]
 = foldl' (+) 10 [5, 6]
 = foldl' (+) 15 [6]
 = foldl' (+) 21 []
 = 21                           -- 21 is a data constructor, stop.

그러나 HaskellWiki의 예에서 언급했듯이, 어큐뮬레이터는 WHNF로만 평가되므로 모든 경우에 도움이되지는 않습니다. 단지 튜플 생성자의 평가, 강제하지 않도록 예에서, 누산기는 튜플 acc또는 len.

f (acc, len) x = (acc + x, len + 1)

foldl' f (0, 0) [1, 2, 3]
 = foldl' f (0 + 1, 0 + 1) [2, 3]
 = foldl' f ((0 + 1) + 2, (0 + 1) + 1) [3]
 = foldl' f (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) []
 = (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1)  -- tuple constructor, stop.

이를 피하려면 튜플 생성자를 평가할 때 accand의 평가를 강제로 수행해야합니다 len. 우리는 이것을 사용하여 이것을한다 seq.

f' (acc, len) x = let acc' = acc + x
                      len' = len + 1
                  in  acc' `seq` len' `seq` (acc', len')

foldl' f' (0, 0) [1, 2, 3]
 = foldl' f' (1, 1) [2, 3]
 = foldl' f' (3, 2) [3]
 = foldl' f' (6, 3) []
 = (6, 3)                    -- tuple constructor, stop.

---

게으름 에 대한 Haskell Wikibooks 설명의 Thunks 및 Weak Head Normal Form 섹션에서는 이 유용한 설명과 함께 WHNF에 대해 매우 잘 설명합니다.

단계적으로 값 (4, [1, 2])를 평가합니다. 첫 번째 단계는 완전히 평가되지 않습니다. 모든 후속 양식은 WHNF이며 마지막 양식은 일반 양식입니다.

---

Haskell 프로그램은 표현식 이며 평가 를 수행하여 실행됩니다 .

표현식을 평가하려면 모든 함수 애플리케이션을 해당 정의로 바꾸십시오. 이 순서는별로 중요하지 않지만 여전히 중요합니다. 가장 바깥 쪽 응용 프로그램으로 시작하여 왼쪽에서 오른쪽으로 진행하십시오. 이것을 게으른 평가 라고 합니다.

예:

   take 1 (1:2:3:[])
=> { apply take }
   1 : take (1-1) (2:3:[])
=> { apply (-)  }
   1 : take 0 (2:3:[])
=> { apply take }
   1 : []

더 이상 교체 할 기능 애플리케이션이 없으면 평가가 중지됩니다. 결과는 정규 형식 (또는 축소 정규 형식 RNF)입니다. 식을 평가하는 순서에 관계없이 항상 동일한 정규 형식으로 끝납니다 (단, 평가가 종료 된 경우에만).

지연 평가에 대한 설명이 약간 다릅니다. 즉, 약한 머리 정상 형태 로만 모든 것을 평가해야한다고 말합니다 . WHNF에 표현이있는 세 가지 경우가 있습니다.

• 생성자 : constructor expression_1 expression_2 ...
• (+) 2or 와 같은 인수가 너무 적은 내장 함수sqrt
• 람다 표현 : \x -> expression

다시 말해, 표현식의 헤드 (즉, 가장 바깥 쪽 함수 애플리케이션)는 더 이상 평가 될 수 없지만 함수 인수는 평가되지 않은 표현식을 포함 할 수 있습니다.

WHNF의 예 :

3 : take 2 [2,3,4]   -- outermost function is a constructor (:)
(3+1) : [4..]        -- ditto
\x -> 4+5            -- lambda expression

---

노트

1. WHNF의 "헤드"는 목록의 헤드가 아니라 가장 바깥 쪽 기능 응용 프로그램을 나타냅니다.
2. 때때로 사람들은 평가되지 않은 표현을 "썽크"라고 부르지 만, 그것을 이해하는 좋은 방법이라고 생각하지 않습니다.
3. HNF ( Head Normal Form )는 Haskell과 관련이 없습니다. 람다 표현의 본문도 어느 정도 평가된다는 점에서 WHNF와 다릅니다.

---

예를 들어 좋은 설명은 http://foldoc.org/Weak+Head+Normal+Form Head 일반 형식 에서 제공되며 함수 추상화 내부의 표현식 비트도 단순화하는 반면, "약한"헤드 정규 형식은 함수 추상화에서 중지됩니다. .

다음과 같은 경우 소스에서 :

\ x -> ((\ y -> y+x) 2)

가능한 응용 프로그램이 아직 평가할 수없는 함수에 갇혀 있기 때문에 약한 헤드 정규 형식이지만 헤드 정규 형식이 아닙니다.

실제 헤드 정규 형식은 효율적으로 구현하기가 어렵습니다. 함수 내부를 파고들 필요가 있습니다. 따라서 약한 헤드 정규 형식의 장점은 여전히 ​​불투명 한 유형으로 함수를 구현할 수 있으므로 컴파일 된 언어 및 최적화와 더 호환됩니다.

---

WHNF는 람다 본문을 평가하지 않기 때문에

WHNF = \a -> thunk
HNF = \a -> a + c

seq 첫 번째 인수가 WHNF에 있기를 원하므로

let a = \b c d e -> (\f -> b + c + d + e + f) b
    b = a 2
in seq b (b 5)

~에 평가하다

\d e -> (\f -> 2 + 5 + d + e + f) 2

대신 HNF를 사용하는 것

\d e -> 2 + 5 + d + e + 2

---

기본적으로 일종의 썽크가 있다고 가정합니다 t.

이제 t함수를 제외하고 동일한 WHNF 또는 NHF 로 평가 하려면 다음과 같은 것을 얻습니다.

t1 : t2어디에 t1그리고 t2멍청이입니다. 이 경우 t1귀하의 0(또는 0추가적인 언 박싱 을 제공하지 않은 썽크 )

seq및 $!evalute WHNF. 참고

f $! x = seq x (f x)

참고 URL : https://stackoverflow.com/questions/6872898/what-is-weak-head-normal-form