Comparando longitud de la lista con las flechas

Question

Inspirado por Comparing list length

Si quiero encontrar la lista más larga de una lista de listas, la forma más sencilla es probablemente:

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

Una manera más eficiente sería para precalcular las longitudes:

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

Ahora, quiero dar un paso más. Puede que no sea más eficiente para casos normales, pero ¿puedes resolverlo usando las flechas? Mi idea es, básicamente, recorrer todas las listas al mismo tiempo, y seguir caminando hasta que hayas sobrepasado la longitud de cada lista, excepto la más larga.

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

En lo anterior ejemplo (muy artificial), sólo se tendría que dar dos pasos a través de cada lista con el fin de determinar que la lista [1..2^1000] es la más larga, sin necesitar para determinar la longitud completa de dicha lista . ¿Tengo razón en que esto se puede hacer con flechas? Si es así, ¿cómo? Si no, ¿por qué no, y cómo podría implementarse este enfoque?

Answer 1

Pensamiento sobre esto un poco más, hay una solución mucho más simple que da las mismas características de rendimiento. Podemos simplemente usar maximumBy con una función de comparación de longitud perezosa:

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

longest = maximumBy compareLength 

Answer 2

bien, cuando estaba escribiendo la pregunta, se me ocurrió una forma sencilla de implementar este (sin flechas, boo!)

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

Excepto que esta tiene un problema ... que caiga la primera parte de la lista y no lo recupera!

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

necesita más contabilidad: 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) 

Ahora funciona.

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

Pero no hay flechas. :(Si se puede hacer con las flechas, a continuación, esperemos que esta respuesta se le dará un lugar para empezar.

Answer 3

Aquí es la aplicación más sencilla que podía pensar. No hay flechas involucrados, sin embargo.

guardo una lista de pares donde el primer elemento es la lista original, y el segundo es la cola restante. Si solo nos queda una lista, hemos terminado. De lo contrario, tratamos de tomar la cola de todas las listas restantes, filtrando las que están vacías. Si algunos todavía permanecen, sigue adelante. De lo contrario, todos son de la misma longitud y arbitrariamente elegirá la primera.

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]