Confrontando lunghezza della lista con le frecce

Question

Ispirato da Comparing list length

Se voglio trovare la più lunga lista in una lista di liste, il modo più semplice è probabilmente:

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

Un modo più efficace sarebbe precaricare le lunghezze:

Ora, voglio fare un ulteriore passo avanti. Potrebbe non essere più efficiente per i casi normali, ma puoi risolvere questo utilizzando le frecce? La mia idea è fondamentalmente, scorrere tutti gli elenchi contemporaneamente e continuare a fare un passo avanti fino a quando non hai oltrepassato la lunghezza di ogni elenco tranne il più lungo.

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

Nel rinuncia esempio (molto artificiosa), si avrebbe solo a fare due passi attraverso ciascuna lista al fine di determinare che l'elenco [1..2^1000] è la più lunga, senza la necessità di determinare l'intera lunghezza di detto elenco . Ho ragione che questo può essere fatto con le frecce? Se è così, allora come? Se no, allora perché no, e come potrebbe essere implementato questo approccio?

Answer 1

Thinking più su questo, c'è una soluzione molto più semplice che offre le stesse caratteristiche prestazionali. Possiamo semplicemente utilizzare maximumBy con una funzione di confronto lenta lunghezza:

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

longest = maximumBy compareLength 

Answer 2

OK, mentre stavo scrivendo la questione, è venuto in mente un modo semplice per implementare questo (senza frecce, boo!)

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

Tranne questo ha un problema ... cade la prima parte della lista e non lo recupera!

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

ha bisogno di più la contabilità: 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) 

Ora funziona.

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

Ma nessuna freccia. :(Se si può fare con le frecce, quindi speriamo che questa risposta può dare un posto per iniziare.

Answer 3

Ecco l'implementazione più semplice mi veniva in mente. Non ci sono frecce coinvolti, però.

tengo un elenco di coppie in cui il primo elemento è l'elenco originale e il secondo è la coda rimanente.Se abbiamo solo una lista rimasta, abbiamo finito, altrimenti proviamo a prendere la coda di tutte le liste rimanenti, filtrando quelli che sono vuoti. Se alcuni ancora rimangono, andare avanti. In caso contrario, sono tutti della stessa lunghezza e abbiamo arbitrariamente scegliere il primo.

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]