Рекурсия по спискам в Хаскеле

Question

Например, у меня есть список вроде ['a', 'b', 'c', 'd', 'e'].
Я хочу сделать что-то вроде этого:
Сначала сделайте что-нибудь с первыми двумя элементами, f 'a' 'b'
Затем сделайте то же самое с возвращаемым значением f и следующего элемента в списке, result = f 'a' 'b', скажем, как f result 'c'. Затем f resultof (result 'c') 'd' и т. Д.
Как я могу сделать что-то подобное?

Answer 1

Сначала давайте рассмотрим ту функцию f, которая у вас есть. Он принимает некое накопленное значение, простое значение и объединяет их в результат. Итак, в сигнатуре типа мы скажем a для типа накопленного значения, v для типа значения и r для типа результата.

f :: a -> v -> r

Теперь мы хотим создать функцию свертывания, которая использует f и список значений.

someFold :: (a -> v -> r) -> [v] -> ?

Что он должен вернуть? Это должно дать что-то типа результирующего r, верно? Обратите внимание, что a и r на самом деле должны быть одного типа, так как мы продолжаем передавать результат f в его первый аргумент снова.

someFold :: (a -> v -> a) -> [v] -> a

Теперь чего-то не хватает. Как вы получаете самый первый a? Есть два способа посмотреть на это. Либо вы просто выбираете первое значение, в этом случае a того же типа, что и v, либо вы указываете базовое значение, поэтому a может фактически отличаться от v. Давайте пойдем с последним, так как это более интересно. Давайте также решим переместиться слева направо в этом списке. (Это то, что тебе нужно, верно?)

someFold :: (a -> v -> a) -> a -> [v] -> a

Итак ... как мы это реализуем? Это будет рекурсивно, поэтому давайте начнем с базовых случаев.

someFold f acc [] = acc

Если мы дойдем до конца списка, тогда мы накопили достаточно, верно? Это было просто. Так как насчет рекурсивного случая? Из того, что вы сказали, на каждом шаге мы должны применять f к «накопленному значению до сих пор» в качестве первого аргумента и «первому значению списка» в качестве второго. f acc x. Затем мы продолжаем складывать, используя , что , в качестве нашего нового «накопленного» значения.

someFold f acc (x:xs) = someFold f (f acc x) xs

Легко, правда? Но ... что если мы хотим сделать, как вы сказали, и запустить функцию, взяв первые два значения в списке? Тоже легко. Просто возьмите первый элемент и назовите его оригинальным «базовым» аккумулятором!

someFold1 :: (v -> v -> v) -> [v] -> v
someFold1 f (x:xs) = someFold f x xs

Обратите внимание, что поскольку a такого же типа, как и v для этого особого случая, функция someFold1 имеет очень забавную сигнатуру типа. Если вы поняли это объяснение, то поздравляю. Мы только что реализовали foldl и foldl1.

Prelude> foldl1 min "abcde" -- "abcde" is sugar for ['a','b','c','d','e']
'a'

В реальном коде вы должны использовать foldl' и друзей.

Answer 2

В этом случае проблема сгиба состоит в том, что он обычно обрабатывает элемент за раз.Вы можете попробовать вручную сложить фолд.

Предположим, у вас есть функция f, которая получает два элемента за раз, и накопитель (результат последней итерации),Тогда ваша функция выглядит следующим образом:

fold2 :: (a -> a -> b -> b) -> [a] -> b -> b
fold2 f accum (x:y:zs) = fold2 f (f x y) zs
fold2 _ accum []       = accum
fold2 _ _     _        = error "odd number of elements"

Попытайтесь понять это.fold2 сбривает два верхних элемента списка и подает их в f.Результат затем передается как новый аккумулятор в рекурсивный вызов.Это делается до тех пор, пока список не станет пустым.

Answer 3

Звучит как домашнее задание.Посмотрите на складки.