하스켈 (formidably long) palindrome check

Question

나는 악명 높은 H-99 problems의 도중에서 일하고 있는데, 나는 problem #6 (목록이 회문인지 아닌지 확인)을하고있다. 나는 대부분의 솔루션이 합리적으로 짧은 목록에서 합리적으로 잘 작동 함을 이해합니다. 이제 어떻게

let ll = [1..10000000] ++ [10000000, 10000000-1..1] ++ [7] 

내가 (순진 아마도) 등을 테스트하기 위해 노력하는 매우 긴 목록은 예를 들면, 회문 경우 기능 테스트 작성합니다

isPalindrome [] = True 
isPalindrome [_] = True 
isPalindrome [x,y] = x==y 
isPalindrome (x:xs) = isPalindrome [x,last xs] && (isPalindrome $ init xs) 

I isPalindrome [x,last xs]이 False으로 평가되면 &&의 비싼 오른 쪽은 평가되지 않는다고 가정합니다.

나는 위의 프로파일 여기가 산출 내용은 다음과 같습니다

는

Mon Jun 30 18:33 2014 Time and Allocation Profiling Report (Final) 

    h99 +RTS -p -RTS 

total time =  1.29 secs (1292 ticks @ 1000 us, 1 processor) 
total alloc = 2,720,050,200 bytes (excludes profiling overheads) 

COST CENTRE MODULE %time %alloc 

main   Main  95.6 100.0 
isPalindrome Main  4.4 0.0 

                  individual  inherited 
COST CENTRE  MODULE     no.  entries %time %alloc %time %alloc 

MAIN   MAIN      43   0 0.0 0.0 100.0 100.0 
CAF   Main      85   0 0.0 0.0 100.0 100.0 
    main   Main      86   1 95.6 100.0 100.0 100.0 
    isPalindrome Main      87   2 4.4 0.0  4.4 0.0 
CAF   GHC.Conc.Signal   84   0 0.0 0.0  0.0 0.0 
CAF   GHC.IO.Encoding   77   0 0.0 0.0  0.0 0.0 
CAF   GHC.IO.Encoding.Iconv 75   0 0.0 0.0  0.0 0.0 
CAF   GHC.IO.Handle.FD   68   0 0.0 0.0  0.0 0.0 
CAF   GHC.Show     63   0 0.0 0.0  0.0 0.0 

있는 나는 문제가 전체 xs을 계산하는 데 필요한 수 last xs에 있음을 추론. 그렇다면 해결 방법이 있습니까? 또는 구현은 욕심이 입니까?

감사합니다.

Answer 1

추측에 따라 last xs이 문제입니다. 목록의 길이가 선형 시간이 걸리므로 전체 목록이 즉시 생성됩니다 (일반적으로 하스켈 목록과 마찬가지로 [a..b]은 게으름). 따라서 귀하의 isPalindrome 함수는 총 2 차 시간이됩니다.

순진한 구현을 위해서는 오른쪽 점근선 동작 (선형)이지만 상대적으로 높은 상수 계수가있는 xs == reverse xs으로 시작하여 reverse이 도착할 때 메모리의 목록 전체가 두 개가됩니다. 목록의 끝으로 이동하여 결과를 생성하기 시작합니다.

아마도 length을보고 나서 중간 지점에서 목록을 분할하거나 한 번에 더 똑똑한 방법을 사용하여 다소 개선 할 수 있습니다.

그러나 실제로는 더 나은 동작을 위해 데이터 구조를 전환해야한다고 생각합니다. Data.Deque 또는 Data.Sequence과 같은 것을 볼 수 있습니다.

Answer 2

당신이 생각하기에 그것은 last xs이라고 생각합니다. 제안 : 재귀를 수행하기 전에 중간 지점 *에서 문자열을 분할하고 후반을 반대로하십시오. 그런 다음 재발 할 때마다 두 문자열의 첫 문자를 비교합니다. * 홀수 길이의 문자열 인 경우 두 문자열 모두 중간 문자를 포함해야합니다.

Answer 3

흥미로운 회문 기능의 무리 this reddit thread에 제안했다 :

palindrome = liftM2 (==) reverse id 

실용적

나이브

palindrome list = reverse list == list 

Pointfree을

palindrome = (==) <$> reverse <*> id 

모나 딕

palindrome = reverse >>= (==)