인덱스가있는 시그마 표기법

Question

나는 시그마 표기법을 필요로하는 문제를 해결하려고 노력해 왔지만, 적어도 하스켈에서 시그마 표기법을 구현할 때마다 그 표제 변수를 사용하지 않는다. 기능. 내가 복제하려고했는데 특별한 공식은 다음과 같습니다

그것은 N에서 0을 후행의 수를 계산하는 데 사용!하지만 내가 가진 것 중에 최고는 것 :

sigma :: (Enum a, Num b) => a -> a -> (a -> b) -> b 
sigma i k fn = sum . map fn $ [i..k] 

zeros :: Int -> Int 
zeros n = sigma 1 n (???) 

나는 또한 일반적인 시그마 함수를 만들려고하는데, 그 함수는 f에있는 인덱스 변수와 함께 작동한다. 이 방법이 효과가 있지만 100의 경우에는 -11 뒤에 0이옵니다. 과다?

zeros :: Int -> Int 
zeros n = sigma 1 n (\i -> n `div` 5^i) 
     where sigma i k fn = sum $ map fn [i..k] 

P. 컴파일 타임을 제한하는 인 브라우저 IDE에 관한 것. (속도 카운트)

Answer 1

문제가 유형 불일치로 인한 것입니다. 마지막으로 truncate을 수행하고 나누기, 지수 및 합계에 분수 산술을 사용하고 끝 부분에서 결과를 자릅니다.

당신에 대해 걱정할 필요가 여기

zeros :: Integral a => a -> a 
zeros n = truncate $ sigma 1 n (\i -> fromIntegral n/5^i) 

세부 사항은 Num b => b에 Integral a => a에서 n를 변환 fromIntegral n이다는 ^ 운영자는 Integral a => a 인수를 허용 :이 때문에, 당신은 단지 zeros n = sigma 1 n something보다 조금 더 필요합니다 지수가 있으므로 변환 할 필요가 없습니다. truncate은 Integral으로 다시 변환됩니다. 우리는이 서명을 더욱 일반적으로 만들 수 있고 우리가 입력 한 다른 Integral을 반환 할 수 있습니다. 그러나 이것은 실제적으로 유용하지는 않습니다.

그래서 지금 우리가 할 수있는 입력 중 하나 Int 또는 Integer, 당신은 100! 요소 목록을 심하게 먹을려고하고있다 (당신이 100!을 언급 한 이후)이 함수에 입력해야하지만 경고 얼마나 큰 숫자의에 따라 최대 RAM 및 CPU 시간. 당신이 정말로 많은 수의 후행 0을 계산하고자하는 경우, 아마 많게 쉬울 것 같이 문자열로 변환

:

zeros :: (Show a, Integral a) => a -> Int 
zeros = length . takeWhile (== '0') . reverse . show 

Answer 2

sigma i k fn = sum $ map fn [i..k] 
zeros n = sigma 1 n (\i -> fromIntegral n/5**(fromIntegral i)) 

하스켈은 정수와 부동 소수점 사이를 자동으로 변환하지 않습니다. 그래서 fromIntegral이 필요합니다.