Как использовать foldr для добавления переменных друг к другу в списке? - PullRequest
Новая
       52

Как использовать foldr для добавления переменных друг к другу в списке?

0 голосов
/ 31 марта 2020

Когда задан список [x0, x1, x2, . . . , xn−1], функция должна вернуть список [y0, y1, y2, . . . , yn−1], где y0 = x0, y1 = x0 + x1, ...

Так что, если бы вы имели [1,2,3] в качестве ввода, вы бы получили [1,3,6] в качестве вывода

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

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : foldr (/y -> y (+) x) 0 (scan xs)

Мой начальный Решение (которое работает) использует функцию map. 

scan :: [Integer] -> [Integer]
scan [] = []
scan [x] = [x]

scan (x:xs) = x : map (+x) (scan xs)

1 Ответ

4 голосов
/ 31 марта 2020

РЕДАКТИРОВАТЬ , я добавил этот первый раздел, чтобы лучше рассмотреть ваши две реализации.

Во-первых, обращаясь к вашей проблеме с вашей реализацией, используя foldr, вот несколько замечаний:

  1. Лямбды начинаются с бэкслы sh в Haskell, а не в виде sh. Это связано с тем, что обратные слэши выглядят как лямбда-греческая буква (λ).

  2. Функции, названные с использованием только специальных символов, например +, по умолчанию являются инфиксными. Если вы используете парены вокруг них, он превращает их в префиксные функции: 

$> (+) 1 5
$> 6
Функция, переданная в foldr, принимает два аргумента, тогда как вы предоставляете только один в своей лямбде. Если вы действительно хотите игнорировать второй, вы можете использовать _ вместо привязки его к переменной (\x _ -> x).

Я думаю, что вы спускаетесь в кроличью нору с этой реализацией. См. Обсуждение ниже, чтобы узнать, как правильно решить эту проблему.

Примечание : Возможно реализовать map с использованием foldr ( source ), это один из способов, которым вы могли бы использовать foldr в вашей рабочей (второй) реализации.

Реализация этого с foldr не оптимальна, так как она сворачивается, как следует из названия, справа : 

foldr1 (+) [1..5]
--is equivalent to:
(1+(2+(3+(4+5))))

Как видите, операция суммирования выполняется, начиная с конца списка, а это не то, что вы ищете. Чтобы это сработало, вам придется «обмануть» и дважды перевернуть список, один раз перед тем, как сложить его, и один раз после: 

scan = tail . reverse . foldr step [0] . reverse where
  step e acc@(a:_) = (e + a) : acc

Вы можете сделать это лучше, используя левую складку, которая складывается из left: 

foldl1 (+) [1..5]
--is equivalent to:
((((1+2)+3)+4)+5)

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

scan' :: [Integer] -> [Integer]
scan' = tail . reverse . foldl step [0] where
  step acc@(a:_) e = (e + a) : acc

Это все еще не очень хорошо, так как reverse добавляет дополнительные вычисления. Поэтому идеальным решением было бы использовать scanl1, который в качестве бонуса не требует от вас указывать начальное значение ([0] в приведенных выше примерах): 

scan'' :: [Integer] -> [Integer]
scan'' = scanl1 (+)

scanl1 реализован в терминах scanl, который определяется примерно так: 

scanl f init list = init : (case list of
                      []   -> []
                      x:xs -> scanl f (f init x) xs)

Поэтому вы можете просто сделать: 

$> scanl1 (+) [1..3]
$> [1,3,6]

В качестве заключительного замечания ваша функция scan неоправданно специализируется на Integer, поскольку для нее требуется только ограничение Num: 

scan :: Num a => [a] -> [a]

Это может даже привести к увеличению производительности, но на этом мои способности заканчиваются, поэтому я не буду go дальше:)

...