Интеркалировать с использованием сгиба

Question

Может кто-нибудь объяснить мне, как написать функцию intercalate, используя fold? Кроме того, я слышал о foldr или foldl; какой из них наиболее подходит для использования в этом контексте?

Вот моя попытка с рекурсией:

intercalate :: [a] -> [[a]] -> [a]
intercalate s [] = []
intercalate s [x] = x
intercalate s (x:xs) = x ++ s ++ (intercalate s xs)

Answer 1

Использование foldr1:

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldr1 (\a acc -> a ++ x ++ acc) xs

Это будет вставлять значения из вправо с x между каждым элементом. (Хотя он делает это лениво . - Вся сгиб не оценивается, пока не понадобится.)

И foldr1, и foldr похожи в том, что они сгибаются справа. Разница заключается в том, что первый не требует от нас предоставления окончательного срока, а последний требует предоставления последнего срока. Это требует от нас сопоставления с образцом для пустого списка, в противном случае возникнет исключение.

Действительно, foldl1 также может выполнять интеркаляцию. Однако это настоятельно не рекомендуется , так как левый сгиб будет с нетерпением потреблять ввод.

intercalate' :: [a] -> [[a]] -> [a]
intercalate' _ [] = []
intercalate' x xs = foldl1 (\acc a -> acc ++ x ++ a) xs

---

Чтобы еще раз подчеркнуть предпочтение правой складки, рассмотрим следующую композицию:

take 10 . intercalate' [0] $ repeat [1..3]

Выглядит безобидно. Но использование foldl1 будет охотно использовать бесконечный список, не останавливая процесс.

Тем не менее, использование foldr1 будет оценивать лениво и даст правильный результат [1,2,3,0,1,2,3,0,1,2]. (intercalate' будет временно оценивать [1..3] ++ [0] ++ (foldr (...) [0] [elem1 ... elemN]) до того, как take 10 запросит ведущие термины и оценит сгиб.)

Слава Будет .

Полезное чтение:
foldl против foldr поведения с бесконечными списками

Answer 2

Давайте вспомним о подписи foldl:

foldl :: (b -> a -> b) -> b -> t a -> b

Простое переписывание того, что вы написали:

intercalate :: [a] -> [[a]] -> [a]
intercalate s [] = []
intercalate s [x] = x
intercalate s (x:xs) = foldl (\acc y -> acc ++ s ++ y) x xs