haskell newbie : 동일한 매개 변수를 사용하여 결정적 함수의 재 계산을 피하는 방법은 무엇입니까?

Question

저는 초보자이기 때문에 기초 개념을 이해하기 시작했습니다.

freq2prob l = [ (curr/(sum l))) | curr <- l ] 

불행하게도 (sum l)는 계산 복잡도가 불필요하게 높은 만드는 l 각 요소에 대해 계산된다

나는 이산 확률 밀도 함수를 계산의 목록을 변환 다음과 같은 기능을 가지고있다.

가장 간결하고 세련된 "하스켈 식"방법은 무엇입니까?

Answer 1

그것은 간단하다 :

이

freq2prob l = [ curr/s | let s = sum l, curr <- l ] 

당신은뿐만 아니라 지능형리스트 외부로 넣을 수 있습니다 : freq2prob l = let s = sum l in [ curr/s | curr <- l ] (차리는 in). 이것은 사실상 동일한 계산입니다. 첫 번째는 본질적으로 동일한 코드로, 분명히,

freq2prob :: (Fractional a) => [a] -> [a] 
freq2prob l = [ curr/s | let s = sum l, curr <- l ] 
= do 
    let s = sum l 
    curr <- l 
    return (curr/s) 
= let s=sum l in 
    l >>= (\curr -> [curr/s]) 
    -- concatMap (\curr -> [curr/s]) l 
    -- map (\curr -> curr/s) l 

로 번역 두 번째되기 때문이다

,

freq2prob l = let s = sum l in [ curr/s | curr <- l ] 
= let s = sum l in 
    do 
    curr <- l 
    return (curr/s) 
= let s=sum l in 
    l >>= (\curr -> [curr/s]) 

Answer 2

우리는하자 문 또는 어디에 사용할 수 있습니다 이것에 대한 절 :

freq2prob l = let s = sum l in 
       [ curr/s | curr <- l ] 

또는

각 요소에 같은 일을하고 있기 때문에

freq2prob l = [ curr/s | curr <- l ] 
    where s = sum l 

있지만, 지능형리스트보다 더 높은 주문 기능을 사용하는 것이 더 관용적 것 : 분할 기능에

freq2prob l = map (/sum l) l 

sum l(/sum l) 유일한 것 한번 평가했다.

map f xs을 평가할 때 컴파일러는 함수 f의 여러 복사본을 개별적으로 평가할 때 실수로 실수를하지 않기 때문입니다. 그것은 필요한 곳마다 지적 될 썽크입니다.

간단하고 둔탁한 테스트로 ghci에서 동일한 기능을 반복적으로 사용하거나 조금씩 다른 기능을 사용하는 것이 눈에 띄게 빨라지는지 여부에 대해 조악한 타이밍 통계를 조사 할 수 있습니다. 우선은 합계의 결과는 일반적으로 ghci에 캐시되어 있는지 확인할 수 있습니다 :

ghci> sum [2..10000000] 
50000004999999 
(8.31 secs, 1533723640 bytes) 
ghci> sum [2..10000000] 
50000004999999 
(8.58 secs, 1816661888 bytes) 

그래서 당신은 캐시되지 않은 볼 수 있으며, 이러한 원유 통계에 약간의 편차가 있음. 이제 같은 복잡한 일에 의해 때마다 곱하자 : 그래서

ghci> map (* sum [2..10000000]) [1..10] 
[50000004999999,100000009999998,150000014999997,200000019999996,250000024999995,300000029999994,350000034999993,400000039999992,450000044999991,500000049999990] 
(8.30 secs, 1534499200 bytes) 

(약간의 편차를 포함하여, 그것을 하나 하나를 곱보다 map를 사용 sum [2..10000000]에 의해 거의 정확하게 열 수를 곱하는 같은 시간이 걸렸 열 쌍을 곱. ghci (인터프리터, 심지어 최적화 컴파일러조차도)는 같은 계산을 여러 개 복사하지 않았습니다.

ghci가 영리한 이유는 순수한 함수 프로그래밍의 멋진 기능인 게으른 평가가 필요 이상으로 작동하지 않기 때문입니다. 대부분의 프로그래밍 언어에서는 결과를 변수에 저장하는 대신 오랜 기간 동안 계산을 통과하여 최적화하는 것이 어려울 것입니다.

이제는 약간 다른 계산을 할 때마다 비교해 보겠습니다. 우리가 예상 한대로 지금 우리가 다른 일을마다 할을 요구하고 있기 때문에, 약 10 배 긴 했다

ghci> map (\x -> sum [x..10000000]) [1..10] 
[50000005000000,50000004999999,50000004999997,50000004999994,50000004999990,50000004999985,50000004999979,50000004999972,50000004999964,50000004999955] 
(77.98 secs, 16796207024 bytes) 

음. 이 값은 각 숫자에 대해 일시 중지되었음을 확인할 수 있습니다. 계산할 비용이 많이 드는 숫자를 변경하지 않은 경우에는 한 번만 평가되고 첫 번째 숫자 앞에 멈춤이 있고 나머지는 빠르게 나타납니다.