6

リストの長さを比較するに触発されました

リストのリストで最も長いリストを見つけたい場合、最も簡単な方法はおそらく次のとおりです。

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]]

前述の (非常に不自然な) 例では、各リストを 2 ステップ実行するだけで、そのリスト[1..2^1000]が最も長いかどうかを判断でき、リスト全体の長さを判断する必要はありません。これが矢印でできるというのは正しいですか？もしそうなら、どうやって？そうでない場合、その理由は何ですか? また、このアプローチをどのように実装できますか?

4

3 に答える 3

4

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]

でも矢はない。:(矢印で実行できる場合は、この回答が出発点になることを願っています。

于 2011-10-11T18:58:42.397 に答える
3

これについてもう少し考えてみると、同じパフォーマンス特性を提供するはるかに単純なソリューションがあります。maximumBy怠惰な長さ比較関数で使用できます。

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

longest = maximumBy compareLength
于 2011-10-11T20:59:17.117 に答える
3

これが私が考えることができる最も簡単な実装です。ただし、矢印は含まれていません。

最初の要素が元のリストで、2 番目の要素が残りの末尾であるペアのリストを保持します。リストが 1 つしか残っていない場合は、完了です。それ以外の場合は、残りのすべてのリストの末尾を取得して、空のリストを除外します。まだ残っている場合は、続けてください。それ以外の場合、それらはすべて同じ長さであり、最初のものを任意に選択します。

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]
于 2011-10-11T19:05:29.997 に答える