하스켈 게으른 평가

Question

나는 다음과 같은 하스켈 코드를 인수 빌드 할 얼마나 많은 [('a',0), ('b',1), ]는 것입니다 압축 된 목록의

'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj" 

와

find_first_occurrence :: (Eq a) => a -> [a] -> Int 
find_first_occurrence elem list = (snd . head) [x | x <- zip list [0..], fst x == elem] 

를 호출 할 경우?

는 UPDATE :

나는

find_first_occurrence 10 [1..] 

를 실행하려고하고 거의 즉시 9를 반환, 그래서 나는 적어도 간단한 경우에 게으른 평가를 사용합니까 것 같아요? 응답도 "즉시"계산됩니다.

let f n = 100 - n 
find_first_occurrence 10 (map f [1..]) 

Answer 1

모두입니다.

StackOverflow를 사용하면 짧은 답변을 게시 할 수 없으므로 찾고있는 것이없는 경우 전체 목록을 살펴 보는 것보다 적은 작업으로 도망 갈 수 있습니다.

편집 : 질문은 이제 더 흥미로운 것을 묻습니다. 짧은 대답은 우리가 목록을 작성할 것입니다 :

('a',0):('b',1):('c',2):('d',3):('X',4):<thunk> 

(사실,이 대답은 조금도 미묘한 귀하의 유형 서명 그래서 모든, 기본적으로 모든 작업에서 엄격한입니다 단형 반환 형식 Int을 사용합니다. 위의 튜플에있는 숫자는 완전히 평가 될 것입니다. 그러나 Num의 구현이 있습니다. 더 많은 덩어리가있는 것을 얻을 수 있습니다.)

Answer 2

짧은 답변 : 검색하는 요소에만 빌드됩니다 에 대한. 이것은 최악의 경우에만 조건을 만족하는 요소가 없을 때 전체 목록을 작성해야 함을 의미합니다.

긴 대답 : 나를 예 한 쌍의 이유를 설명하자, 우편 무한리스트를해야

ghci> head [a | (a,b) <- zip [1..] [1..], a > 10] 
11 

이 경우, 그러나 게으름은 (11,11)까지를 구축 할 하스켈 수 있습니다 : 당신으로 실행은 발산하지 않지만 실제로 우리에게 정확한 답을줍니다. 전체 압축 목록이 구축되지 않기 때문에, 하스켈 분명히 심지어 요소가 div 1 0는 전에 그래서 때, 목록에 발생하는 각 표현식을 평가하지 않습니다

ghci> find_first_occurrence 1 [0, 0, 1 `div` 0, 1] 
*** Exception: divide by zero 
ghci> find_first_occurrence 1 [0, 1, 1 `div` 0, 0] 
1 
it :: Int 
(0.02 secs, 1577136 bytes) 

: 이제

은 나에게 또 다른 문제를 살펴 보자 함수는 예외를 발생시키지 않고 올바르게 평가됩니다. 0으로 나누기가 발생하지 않았습니다.

Answer 3

여기에 undefined을 소개하면 쉽게 이러한 질문에 대답 할 수 있습니다. 우리의 경우는 우리의 입력을 변경하기에 충분하다 :

find_first_occurrence 'X' ("abcdX" ++ undefined) 

당신은 그것이 심지어 발견되는 'X'를 넘어 보이지 않는 즉, 결과를 생성하는 것을 볼 수 있습니다 (그렇지 않으면 예외를 던진 것).물론 원래 목록을 보지 않고도 압축 된 목록을 작성할 수는 없습니다. 전면에 'X'를하지 않은해야 두 번째 발현 :

> let find_first_occurrence elem list = (snd . head) [x | x <- map (\i -> trace (show i) i) $ zip list [0..], fst x == elem] 
> find_first_occurrence 'X' "abcdXkjdkljklfjdlfksjdljjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj" 

인쇄

('a',0) 
('b',1) 
('c',2) 
('d',3) 
('X',4) 
4