Вопрос: Список процессов Haskell справа налево, сохраняя порядок происхождения


Необходимо увеличивать каждый второй элемент, начиная с правого в списке Haskell, но сохраняя порядок происхождения (например, reverse это не случай). Например:

 f [1, 2, 3] --  [1, 3, 3]

 f [1, 2, 3, 4] -- [2, 2, 4, 4]

Я пробовал что-то вроде следующего:

fc ([]) = []
fc (x:[]) = [x]
fc (x:[y]) = [x+1,y]
fc( x:xs ) = fc [x] : ( fc xs ) -- this line is wrong

постскриптум Очевидно, что я мог бы перевернуть (но предпочитаю понимать оригинальную задачу) в списке дважды и применить что-то вроде:

helper (x:y:tail) = [x, y+1] ++ tail
fc x = reverse (helper (reverse x) )

4


источник


Ответы:


Это можно сделать эффективно, используя левая складка :

inc :: Num a => [a] -> [a]
inc xs = foldl go (\_ _ acc -> acc) xs id (+ 1) []
    where go run x f g acc = run g f (f x: acc)

Заметьте, что даже подумал, что это левая складка, список построен с использованием минусов (:) оператор; и он будет выполняться линейно, а не квадратично (аналогичная конструкция, как в разностные списки ).

\> inc [1, 2, 3]
[1,3,3]
\> inc [1, 2, 3, 4]
[2,2,4,4]

Он также может быть обобщен на чередующиеся функции, отличные от id а также (+ 1),


2



Типичным способом обработки списка Haskell справа налево было бы обратить вспять его. Поскольку вы хотите иметь исходный порядок для результата, вы просто просто измените обратное:

f1 = reverse . zipWith (+) (cycle [0,1]) . reverse

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

f2 = snd . g
  where
  g []     = (False, [])
  g (x:xs) = let (addOne, xs') = g xs
                 x' = if addOne then x + 1 else x
             in (not addOne, x':xs')

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

import Data.List (mapAccumR)
f2' = snd . mapAccumR g False
  where
  g addOne x = (not addOne, if addOne then x + 1 else x)

4



Я думаю, что более чистая спецификация для того, что вы хотите, состоит в том, что вы увеличиваете даже показатели, если длина четная и нечетная, указывает, что длина нечетная. Например, при индексировании с нуля список длин 3 привел к увеличению индекса 1. Один из способов сделать это - с очевидным двухпроходным решением:

f xs = zipWith (+) (cycle sol) xs
 where sol = map fromEnum [even len, odd len] 
       len = length xs

Это можно сделать за один проход (не полагаясь на правила слияния компилятора), «привязывая узел». Например (с использованием ручного рекурсивного стиля как средства связи).

f2 xs = let (isEven, result) = go isEven xs in result
 where
  go _ []     = (True,     [])
  go e (x:xs) = let (ne,rest) = go (not e) xs
                in (not ne, x+fromEnum e : rest)

4



Мне нравится решение Томаса. Однако, я думаю, простой foldr здесь достаточно.

process = snd . foldr (\x (b,xs) -> (not b, x + fromEnum b:xs)) (False,[])

0