내 기능이 무한 목록에서 작동하지 않는 이유는 무엇입니까?

Question

haskell을 배우고 conseq크기 n의 연속 요소 목록을 반환하는 함수 를 구현하려고합니다 .

conseq :: Int -> [Int] -> [[Int]]
conseq n x 
      | n == length(x) = [x]
      | n > length(x) = [x]
      | otherwise = [take n x] ++ (conseq n (drop 1 x))

이것은 올바르게 작동합니다.

> take 5 $ conseq 2 [1..10]  
[[1,2],[2,3],[3,4],[4,5],[5,6]]

그러나 [1..]대신을 전달 [1..10]하면 프로그램이 무한 루프에 빠집니다.

내가 이해했듯이 haskell은 게으른 평가를 가지고 있으므로 여전히 동일한 결과를 얻을 수 있어야합니까? 그렇 length습니까? 길이가보다 커지면 처음 두 조건이 거짓으로 평가되지 n않습니까?

내가 무엇을 오해 했습니까?

Answer 1

사용 length이 좋은 생각이 아닌 주된 이유 중 하나 는 무한 목록에서 평가해야 할 때 무한 루프에 갇히기 때문입니다.

그러나 좋은 소식은 length. 또한 시간 복잡성을 악화시킬 것입니다. 두 개의 열거 자로 작업 할 수 있습니다. 하나는 다른 하나보다 n-1 자리 앞서 있습니다. 이 열거자가 목록의 끝에 도달하면 첫 번째 열거 자에 여전히 n-1 개의 요소 가 있음을 알고 있으므로 값 생성을 중지 할 수 있습니다.

conseq :: Int -> [a] -> [[a]]
conseq n ys = go (drop (n-1) ys) ys
    where go [] _ = []
          go (_:as) ba@(~(_:bs)) = take n ba : go as bs

이것은 우리에게 다음을 제공합니다 :

Prelude> conseq 3 [1 ..]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10],[9,10,11],[10,11,12],[11,12,13],[12,13,14],[13,14,15],[14,15,16],[15,16,17],[16,17,18],[17,18,19],[18,19,20],[19,20,21],[20,21,22],[21,22,23],[22,23,24],[23,24,25],[24,25,26],[25,26,27],…
Prelude> conseq 3 [1 .. 4]
[[1,2,3],[2,3,4]]

Answer 2

당신의 함수가 제일 먼저 계산입니다 length(x)그것이 반환할지 여부를 알 수 있도록, [x], [x], 또는[take n x] ++ (conseq n (drop 1 x))

length목록의 모든 요소 수를 계산합니다. 무한 목록의 길이를 요청하면 계산이 끝나지 않습니다.