prefixes ls = zipWith take [1 .. length ls] (repeat ls)
이보다 더 좋은 방법이 있습니까? 직관적으로, 그것은 반전 또는 추가가 n 번 적용되어야하기 때문에 순전히 함수 언어로 O (n²) 이하의 알고리즘을 얻을 수 없다고 생각됩니다. 그래도 이걸 증명할 방법이 없다.목록의 모든 접두어를 생성하는 가장 효율적인 순수 알고리즘은 무엇입니까?
나는 당신이 옳다고 생각합니다. 모든 꼬리가 다르기 때문에 목록의 척추를 공유 할 수 없습니다. 따라서 접두어 목록을 완전히 평가 한 경우 전체 Θ (n) 공간이 필요하며 생성 시간은 Ω (n)입니다.
작성한 함수의 (느슨한 버전)은 Data.List에 inits으로 제공됩니다.
그래도 할 수있는 최적화가 있습니다. 이 방정식은 다음을 유지합니다.
map (foldl f z) . inits = scanl f z
및 scanl은 선형 시간으로 실행됩니다. 따라서 각 접두사에 대해 왼쪽 접기로하려는 작업을 구사할 수 있다면 접두사 목록 작성의 2 차적 복잡성을 피할 수 있습니다.
표현에 종속적이지 않습니까? 리스트를 연속 된 스토리지와 시작 및 종료 인덱스 (bytestrings과 유사)로 표현하면 스토리지를 공유 할 수 있으며 인덱스 목록을 작성하기 위해 한 번 트래버스해야합니다. 알고리즘은 변하지 않을 것입니다. 이 특정 사용 사례의 경우 snoc 목록 (바이너리 목록이지만 목록의 시작이 아니라 끝에서 중첩 됨)을 사용하면 하위 목록을 공유 할 수 있습니다.
+1 scanl에 대한 좋은 아이디어 –