用箭头

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]