이 꼬리 재귀 Haskell 함수가 왜 느린가?

Question

나는 정수 배열 A 을 입력으로 받아서 다른 배열 B = [A [0], A [0] + A [1], A [0] + A [1]을 생성하는 Haskell 함수를 구현하려고 시도했다. ] + A [2], ...]. Data.List의 scanl이 함수 (+)와 함께 사용될 수 있다는 것을 알고 있습니다. 내가 scanl의 소스 코드를보고 나서 두 번째 구현 (빠른 수행)을 썼습니다. 꼬리 재귀 적 임에도 불구하고 첫 번째 구현이 두 번째 구현과 비교해 왜 느린 지 알고 싶습니다. 위의 코드에 대한

-- This function works slow. 
ps s x [] = x 
ps s x y = ps s' x' y' 
      where 
       s' = s + head y 
       x' = x ++ [s'] 
       y' = tail y 

-- This function works fast. 
ps' s [] = [] 
ps' s y = [s'] ++ (ps' s' y') 
      where 
       s' = s + head y 
       y' = tail y 

일부 세부 정보 :

구현 1 : 그것은 '는이'배열입니다

ps 0 [] a 

으로 호출해야합니다.

구현 2 : 그것은 '는이'배열입니다

ps' 0 a 

으로 호출해야합니다.

Answer 1

++의 연결 방법이 변경되었습니다. 첫 번째 함수에서 ((([a0] ++ [a1]) ++ [a2]) ++ ...)을 계산하는 반면 두 번째 함수에서는 [a0] ++ ([a1] ++ ([a2] ++ ..))을 계산합니다. 목록의 시작 부분에 몇 가지 요소를 추가하는 것은 O(1)이며, 목록의 끝에 몇 개의 요소를 추가하는 것은 목록의 길이가 O(n)입니다. 이것은 전반적으로 선형 대 2 차 알고리즘으로 이어진다.

역순으로 목록을 작성한 다음 끝에 역순으로 또는 dlist와 같은 것을 사용하여 첫 번째 예를 수정할 수 있습니다. 그러나 두 번째는 여전히 대부분의 목적에 더 나을 것입니다. 꼬리 호출이 존재하고 Haskell에서 중요 할 수 있지만, Scheme이나 ML과 같은 엄격한 함수 언어에 익숙하다면, 언제 어떻게 사용하는지에 대한 직감이 완전히 잘못되었습니다.

두 번째 예제는 점진적이기 때문에 더 낫습니다. 소비자가 관심을 가질만한 데이터를 반환하기 시작합니다. double-reverse 또는 dlist 트릭을 사용하여 첫 번째 예제를 방금 수정 한 경우, 함수는 전체 목록을 탐색하여 반환합니다.

Answer 2

나는 당신의 기능을보다 쉽게 ​​보통

drop 1 . scanl (+) 0 

로 표현 될 수 있음을 언급하고 싶은, 자신의 재귀 계획을 작성 찬성 scanl 같은 미리 정의 된 콤비를 사용하는 것이 좋습니다; 가독성이 향상되고 불필요하게 성능을 낭비하지 않게됩니다.

그러나,이 경우, 모두 내 scanl 버전 원래는 ps 및 ps' 때로는 게으른 평가로 인한 오버 플로우 스택으로 이어질 수 있습니다 하스켈은 반드시 즉시 추가 사항을 평가하지 않습니다 (엄격 분석에 따라 다름).

당신이 이것을 볼 수있는 경우는 last (ps' 0 [1..100000000])입니다. 스택 오버플로가 발생합니다. 당신은 scanl 엄격하게 자신을 정의하여, 예를 들어, 즉시 추가을 평가하기 위해 하스켈을 강제로 그 문제를 해결할 수 있습니다 : 다음

myscanl :: (b -> a -> b) -> b -> [a] -> [b] 
myscanl f q []  = [] 
myscanl f q (x:xs) = q `seq` let q' = f q x in q' : myscanl f q' xs 

ps' = myscanl (+) 0 

, last (ps' [1..100000000]) 작품을 호출.