用箭頭

Question

通過Comparing list length

如果我想找到一個列表的列表最長的名單啓發比較列表長度，最簡單的方法可能是：

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

一個更有效的方法是以預先計算長度：

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

現在，我想進一步。對於正常情況可能效率不高，但是您能否使用箭頭解決這個問題？我的想法基本上是，同時列出所有列表，並繼續步進，直到超出除最長列表之外的每個列表的長度。

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

在前述（很做作）例如，您可能只需要採取通過每個列表中的兩個步驟，以確定該列表[1..2^1000]是最長的，從來沒有需要來確定所述列表的整個長度。我說得對，這可以用箭頭來完成嗎？如果是這樣，那麼怎麼樣？如果沒有，那麼爲什麼不呢，這種方法怎麼可能被實施呢？

Answer 1

想法關於這一點，還有一個更簡單的解決方案，它具有相同的性能特徵。我們可以使用具有延遲長度比較功能的maximumBy：

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

longest = maximumBy compareLength 

Answer 2

OK，因爲我寫的問題，我恍然大悟實現這個簡單的方法（不箭頭，噓！）

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

除了這有一個問題......它滴的第一部分的名單，並沒有恢復它！

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

需要更多的簿記：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) 

現在，它的工作原理。

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

但沒有箭頭。 :(如果可以用箭頭來完成，然後希望這個答案可以給你什麼地方開始。

Answer 3

這是最簡單的實現，我能想到的，沒有箭頭參與，雖然。

我把名單第一個元素是原始列表，第二個元素是剩餘尾部，如果我們只剩下一個列表，我們就完成了，否則我們嘗試把所有剩下的列表尾部，過濾掉那些空的列表。如果仍然存在，繼續前進，否則它們的長度都是相同的，我們會隨意選擇第一個。

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]