Обратные первые k элементов списка

Question

Я бы хотел эффективно изменить первые k элементов списка.

Это то, что я придумал:

reverseFirst :: Int -> [a] -> [a] -> [a] 
reverseFirst 0 xs rev  = rev ++ xs 
reverseFirst k (x:xs) rev = reverseFirst (k-1) xs (x:rev) 

reversed = reverseFirst 3 [1..5] mempty -- Result: [3,2,1,4,5] 

Это довольно хорошо, но (++) беспокоит меня. Или я должен рассмотреть возможность использования другой структуры данных? Я хочу сделать это много миллионов раз с короткими списками.

Answer 1

Давайте думать о обычной структуре reverse:

reverse = rev [] where 
    rev acc [] = acc 
    rev acc (x : xs) = rev (x : acc) xs 

Он начинается с пустым списком и галсами на элементы из передней части списка аргументов, пока это не сделано. Мы хотим сделать что-то подобное, за исключением того, что мы хотим привязать элементы к передней части части списка, которую мы не отменяем. Как мы можем это сделать, когда у нас нет , что еще не восстановленная часть?

Самый простой способ, которым я могу думать, чтобы избежать перемещения фронта списка два раза использовать лени:

reverseFirst :: Int -> [a] -> [a] 
reverseFirst k xs = dis where 
    (dis, dat) = rf dat k xs 

    rf acc 0 ys = (acc, ys) 
    rf acc n [] = (acc, []) 
    rf acc n (y : ys) = rf (y : acc) (n - 1) ys 

dat представляет часть списка, который остался один. Мы вычисляем его в той же вспомогательной функции rf, которая делает реверсирование, но мы также передаем ее на rf при первоначальном вызове. Это никогда не рассматривается в rf, поэтому все просто работает. Глядя на сгенерированное ядро ​​(с использованием ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures), мы предполагаем, что пары скомпилированы в незашифрованные пары, а Int s распакованы, поэтому все должно быть достаточно эффективным.

---

Профилирование предполагает, что эта реализация составляет около 1,3 раза быстрее, чем в списке разностных один, и выделяет около 65% больше памяти.

Answer 2

Хорошо, обычно я просто пишу splitAt 3 >>> first reverse >>> uncurry(++) для достижения цели.

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

reverseFirstN :: Int -> [a] -> [a] 
reverseFirstN = go id 
where go rev 0 xs = rev xs 
     go rev k (x:xs) = go ((x:).rev) (k-1) xs 

но, честно говоря, я не ожидал, что это будет намного быстрее, вы должны пройти первые п элементы так или иначе. Фактическая производительность будет зависеть от того, что компилятор может сработать.