Объединение списков с использованием foldl ', foldr

Question

Я сейчас изучаю Haskell и сталкиваюсь со следующей проблемой:

Я хочу переписать функцию ++, используя foldl 'и foldr.Я сделал это с помощью foldr:

myConcat xs ys = foldr (:) ys xs

Я не могу сделать это с помощью foldl '.В RealWorldHaskell я читал, что foldr полезен для подобных вещей.Хорошо, но я не могу также написать эквивалент для ++ с использованием foldl?Может кто-нибудь показать мне, как я могу это сделать (если это можно сделать ... В книге ничего об этом не сказано) ...

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

Answer 1

Оператор : объединяет единственный элемент , его левый аргумент, со списком, его правый аргумент.

Параметры foldl,

• Функция складывания
• Начальное значение
• Список значений для перехода.

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

> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6]
[6,5,4,1,2,3]

Но это не то, что вы хотите. Вам придется решить это самостоятельно; Мне удалось создать обратную функцию, используя foldl, и вызвать ее как подпрограмму, но вы можете решить ее по-другому, если можете.

Answer 2

Я предполагаю, что ошибка, которую вы получаете, заключается в попытке просто переключить foldr на foldl':

myConcat xs ys = foldl' (:) ys xs

, что приводит к ошибке (используя мой реплик Hugs):

ERROR - Type error in application
*** Expression     : foldl' (:) xs ys
*** Term           : (:)
*** Type           : a -> [a] -> [a]
*** Does not match : [a] -> a -> [a]

Обратите внимание на две последние строки (предоставленный тип и ожидаемый тип), что позиции [a] и a находятся в противоположных позициях.Это означает, что нам нужна функция, подобная (:), но принимающая аргументы в обратном порядке.

В Haskell есть функция, которая делает это для нас: функция flip.По сути, flip эквивалентно

flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y

То есть flip принимает двоичную функцию в качестве аргумента и возвращает другую двоичную функцию, аргументы которой обращены («перевернуты») от оригинала.Таким образом, хотя (:) имеет тип a -> [a] -> [a], мы видим, что flip (:) имеет тип [a] -> a -> [a], что делает его идеальным кандидатом в качестве параметра foldl'.

Используя flip, мытеперь имеем этот код:

myConcat xs ys = foldl' (flip (:)) ys xs

Это результат того факта, что foldl' имеет тип (a -> b -> c) -> a -> [b] -> c

Запустив это с аргументами [1..5] и [6..10], мы получимрезультат [5,4,3,2,1,6,7,8,9,10], что почти то, что мы хотим.Единственная проблема в том, что первый список в результате оказывается обратным.Добавление простого вызова к reverse дает нам окончательное определение myConcat:

myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

---

Просмотр этого процесса показывает одну из приятных вещей, которая часто возникает при написании кода на Haskell: когдаВы сталкиваетесь с проблемой, вы можете решить ее один (маленький) шаг за раз.Это особенно верно, когда у вас уже есть одна работающая реализация, и вы просто пытаетесь написать другую.Важно отметить, что если вы измените одну часть реализации (в данном случае, изменив foldr на foldl'), то многие другие необходимые изменения просто выпадут из определений типов.Осталось лишь немного проблем исправления, которые можно легко найти, выполнив тестовые примеры или посмотрев на точную природу используемых функций.

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

Answer 3

Это не всегда возможно, так как foldr (как и ++) работает с бесконечными списками, а foldl - нет. Однако, foldl можно записать в терминах foldr: http://www.haskell.org/haskellwiki/Foldl_as_foldr

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

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a bs =
  foldl (\g b x -> g (f b x)) id bs a

Итак, из этого вы можете реализовать (++) в терминах foldl

Answer 4

data [] a = ... | a : [a]
(:) :: a -> [a] -> [a]

(:) Оператор по-разному обрабатывает левый и правый операнд.

a :: Char
b :: Char
c :: [Char]

a:[b] в порядке

a:b не в порядке

a:c в порядке.

поищите сигнатуру типа foldr (:) и foldl (:) вы найдете различные из них.

Answer 5

Вы можете сделать это, используя foldl, но это не будет эффективным по сравнению с реализацией на основе foldr

Пример использования foldl:

show $ (\xs ys -> foldl­ (\s e -> e:s ) ys (reve­rse xs)) [1,2]­ [3,4]