하스켈에서 ++ 피하기

Question

this answer on CodeReview에서 asker와 answerer는 (++) 연산자에 대해 경멸감을 보입니다. 이것은 속도 때문입니다 (알고리즘을 O (n^2)에서 명시 적으로 실행시키는 원인이됩니까? n은 목록 iirc의 길이입니다)? Haskell이 시간 복잡성에 대해 추론하기 어렵다는 것이 알려져 있기 때문에 다른 테스트를 거치지 않았다면 이것은 사전 최적화입니까? 다른 사람들이 프로그램에서 (++) 연산자를 사용하지 않아야합니까?

Answer 1

에 따라 다릅니다.

이 표현식은 하나의리스트에리스트 목록을 연결하지만, 상기 이차 복잡도를 갖는 표현식을

foldl (++) [] list 

을 고려한다. 이것은 (++)의 구현이 전체 왼쪽 목록을 가로 지르고 올바른 순서로 각 요소를 오른쪽 목록 앞에 추가하기 때문에 발생합니다.

foldr (++) [] list 

이는 왼쪽 인자를 통과하고 오른쪽으로 앞에 추가 (++) 운영자의 구현에 기인한다 : 오른쪽 배를 사용

는

, 우리는 선형 복잡도를 얻을.

[1,2] ++ [3,4] ++ [5,6] 

번만 각리스트 요소를 통과

-- Example as created by foldr 
[1,2] ++ ([3,4] ++ [5,6]) 
== [1,2] ++ [3,4,5,6] 
== [1,2,3,4,5,6] -- all good, no element traversed more than once 

같다.

이제 괄호를 처음 두 목록으로 전환하는 것이 더 비쌉니다. 이제 일부 요소가 여러 번 통과하기 때문에 비효율적입니다.

-- Example as created by foldl 
([1,2] ++ [3,4]) ++ [5,6] 
== [1,2,3,4] ++ [5,6] 
== [1,2,3,4,5,6] -- the sublist [1,2] was traversed twice due to the ordering of the appends 

이러한 경우에는주의해야합니다.