danh sách So sánh chiều dài với mũi tên

Question

Lấy cảm hứng từ Comparing list length

Nếu tôi muốn tìm danh sách dài nhất trong một danh sách liệt kê, cách đơn giản nhất có lẽ là:

longestList :: [[a]] -> [a] 
longestList = maximumBy (comparing length) 

Một cách hiệu quả hơn sẽ để tính toán trước độ dài:

longest :: [[a]] -> [a] 
longest xss = snd $ maximumBy (comparing fst) [(length xs, xs) | xs <- xss] 

Bây giờ, tôi muốn tiến thêm một bước nữa. Nó có thể không hiệu quả hơn đối với các trường hợp thông thường, nhưng bạn có thể giải quyết này bằng cách sử dụng các mũi tên không? Ý tưởng của tôi là cơ bản, bước qua tất cả các danh sách cùng một lúc, và tiếp tục bước cho đến khi bạn đã overstepped chiều dài của tất cả các danh sách ngoại trừ dài nhất.

longest [[1],[1],[1..2^1000],[1],[1]] 

Trong forgoing (rất giả tạo) Ví dụ, bạn sẽ chỉ phải mất hai bước qua từng danh sách để xác định rằng danh sách [1..2^1000] là dài nhất, mà không bao giờ cần phải xác định toàn bộ chiều dài của danh sách nói . Tôi có đúng là điều này có thể được thực hiện với các mũi tên không? Nếu có thì làm sao? Nếu không, thì tại sao không, và cách tiếp cận này có thể được thực hiện như thế nào?

Answer 1

Suy nghĩ về điều này một số chi tiết, có một giải pháp đơn giản hơn nhiều mang đến các đặc tính hiệu suất giống nhau. Chúng tôi chỉ có thể sử dụng maximumBy với chức năng so sánh độ dài lười biếng:

compareLength [] [] = EQ 
compareLength _ [] = GT 
compareLength [] _ = LT 
compareLength (_:xs) (_:ys) = compareLength xs ys 

longest = maximumBy compareLength 

Answer 2

OK, như tôi đã viết câu hỏi, nó chợt nhận ra tôi một cách đơn giản để thực hiện điều này (không có mũi tên, boo!)

longest [] = error "it's ambiguous" 
longest [xs] = xs 
longest xss = longest . filter (not . null) . map (drop 1) $ xss 

Trừ này có một vấn đề ... nó giảm phần đầu tiên của danh sách và không phục hồi nó!

> take 3 $ longest [[1],[1],[1..2^1000],[1]] 
[2,3,4] 

nhu cầu kế toán hơn: P

longest xs = longest' $ map (\x -> (x,x)) xs 

longest' [] = error "it's ambiguous" 
longest' [xs] = fst xs 
longest' xss = longest . filter (not . null . snd) . map (sndMap (drop 1)) $ xss 

sndMap f (x,y) = (x, f y) 

Bây giờ nó hoạt động.

> take 3 $ longest [[1],[1],[1..2^1000],[1]] 
[1,2,3] 

Nhưng không có mũi tên. :(Nếu nó có thể được thực hiện với mũi tên, sau đó hy vọng câu trả lời này có thể cung cấp cho bạn một nơi nào đó để bắt đầu.

Answer 3

Đây là việc thực hiện đơn giản nhất mà tôi có thể nghĩ đến. Không mũi tên tham gia, mặc dù.

tôi giữ một danh sách các trong đó phần tử đầu tiên là danh sách gốc, và phần tử thứ hai là đuôi còn lại, nếu chúng ta chỉ còn lại một danh sách, thì chúng ta sẽ lấy đuôi của tất cả các danh sách còn lại, lọc ra những người trống. Nếu một số vẫn còn, hãy tiếp tục. Nếu không, chúng có cùng độ dài và chúng ta tùy ý chọn cái đầu tiên.

longest [] = error "longest: empty list" 
longest xss = go [(xs, xs) | xs <- xss] 
    where go [(xs, _)] = xs 
     go xss | null xss' = fst . head $ xss 
       | otherwise = go xss' 
       where xss' = [(xs, ys) | (xs, (_:ys)) <- xss]