Làm cách nào để viết hàm chiều dài không gian cố định trong Haskell?

Question

Việc thực hiện kinh điển của length :: [a] -> Int là:

length [] = 0 
length (x:xs) = 1 + length xs 

mà là rất đẹp nhưng bị chồng tràn vì nó sử dụng không gian tuyến tính.

Phiên bản đuôi-đệ quy:

length xs = length' xs 0 
    where length' [] n = n 
     length' (x:xs) n = length xs (n + 1) 

không bị vấn đề này, nhưng tôi không hiểu làm thế nào điều này có thể chạy trong không gian liên tục trong một ngôn ngữ lười biếng.

Không phải thời gian chạy tích lũy nhiều số (n + 1) khi di chuyển qua danh sách? Không nên chức năng này Haskell để tiêu thụ không gian O (n) và dẫn đến tràn ngăn xếp?

(nếu vấn đề, tôi đang sử dụng GHC)

Answer 1

Có, bạn đã gặp phải sự cố chung với các thông số tích lũy. Cách chữa trị thông thường là bắt buộc đánh giá nghiêm ngặt về tham số tích lũy; vì mục đích này, tôi thích nhà điều hành ứng dụng nghiêm ngặt $!. Nếu bạn không ép buộc độ nghiêm ngặt, trình tối ưu hóa của GHC có thể quyết định rằng chức năng này là nghiêm ngặt, nhưng có thể không. Chắc chắn nó không phải là một điều để dựa vào — đôi khi bạn muốn một tham số tích lũy được đánh giá lazily và O (N) không gian là tốt, cảm ơn bạn.

Làm cách nào để viết chức năng chiều dài không gian cố định trong Haskell?

Như đã đề cập ở trên, sử dụng toán tử ứng dụng nghiêm ngặt để buộc đánh giá của tham số tích lũy:

clength xs = length' xs 0 
    where length' []  n = n 
     length' (x:xs) n = length' xs $! (n + 1) 

Loại $! là (a -> b) -> a -> b, và nó buộc các đánh giá của a trước khi áp dụng hàm.

Answer 2

Một chức năng đuôi-đệ quy không cần phải duy trì một chồng, vì giá trị trả về bởi hàm được chỉ đơn giản là sẽ được giá trị trả về bởi các cuộc gọi đuôi. Vì vậy, thay vì tạo một khung ngăn xếp mới, khung hiện tại được tái sử dụng, với những người dân địa phương bị ghi đè bởi các giá trị mới được chuyển vào cuộc gọi đuôi. Vì vậy, mỗi n+1 được viết vào cùng một vị trí nơi cũ n và bạn có sử dụng không gian liên tục.

Chỉnh sửa - Trên thực tế, như bạn đã viết nó, bạn nói đúng, nó sẽ làm hỏng (n+1) giây và gây tràn. Dễ dàng kiểm tra, chỉ cần thử length [1..1000000] .. Bạn có thể khắc phục điều đó bằng cách buộc nó để đánh giá nó trước: length xs $! (n+1), sau đó sẽ hoạt động như tôi đã nói ở trên.

Answer 3

Chạy phiên bản thứ hai của bạn trong GHCi:

> length [1..1000000] 
*** Exception: stack overflow 

Vì vậy, để trả lời câu hỏi của bạn: Vâng, nó không bị vấn đề đó, cũng giống như bạn mong đợi.

Tuy nhiên, GHC thông minh hơn trình biên dịch trung bình; nếu bạn biên dịch với tối ưu hóa, nó sẽ sửa mã cho bạn và làm cho nó hoạt động trong không gian cố định.

Nói chung, có nhiều cách để buộc mức độ nghiêm ngặt tại các điểm cụ thể trong mã Haskell, ngăn chặn việc xây dựng các khối lồng nhau sâu. Một ví dụ thông thường là foldl vs foldl':

len1 = foldl (\x _ -> x + 1) 0 
len2 = foldl' (\x _ -> x + 1) 0 

Cả hai chức năng còn lại nếp gấp mà làm "tương tự" điều, ngoại trừ foldl đó là lười biếng trong khi foldl' là nghiêm ngặt. Kết quả là len1 chết với tràn ngăn xếp trong GHCi, trong khi len2 hoạt động chính xác.