Сравнение длины списка со стрелками - PullRequest
Новая
       10

Сравнение длины списка со стрелками

6 голосов
/ 11 октября 2011

Вдохновлен Длина списка сравнения

Если я хочу найти самый длинный список в списке списков, возможно, самый простой способ: 

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] самый длинный, без необходимости определять всю длину указанного списка. Прав ли я, что это можно сделать стрелками? Если так, то как? Если нет, то почему нет, и как можно реализовать этот подход?

Ответы [ 3 ]

4 голосов
/ 11 октября 2011

ОК, когда я писал вопрос, меня осенило простой способ реализовать это (без стрелок, бу!) 

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]

Но стрелок нет. :( Если это можно сделать с помощью стрелок, то, надеюсь, этот ответ поможет вам начать.

3 голосов
/ 12 октября 2011

Если подумать об этом еще, есть гораздо более простое решение, которое дает те же характеристики производительности.Мы можем просто использовать maximumBy с функцией сравнения ленивых длин: 

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

longest = maximumBy compareLength
3 голосов
/ 11 октября 2011

Вот самая простая реализация, которую я мог придумать.Хотя стрелок не задействовано.

Я держу список пар, где первый элемент - это оригинальный список, а второй - оставшийся хвост.Если у нас есть только один список, мы закончили.В противном случае мы пытаемся взять хвост всех оставшихся списков, отфильтровывая тех, кто пуст.Если некоторые еще остаются, продолжайте.В противном случае они имеют одинаковую длину, и мы произвольно выбираем первый. 

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