Я попытался понять это элегантное решение сам, поэтому я попытался вывести типы и оценку самостоятельно. Итак, нам нужно написать функцию:
zip xs ys = foldr step done xs ys
Здесь нам нужно вывести step и done, какими бы они ни были. Напомним тип foldr, созданный для списков:
foldr :: (a -> state -> state) -> state -> [a] -> state
Однако наш вызов foldr должен быть реализован как-то так, как показано ниже, потому что мы должны принять не один, а два аргумента списка:
foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]
Поскольку -> является правоассоциативным , это эквивалентно:
foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])
Наш ([b] -> [(a,b)]) соответствует переменной типа state в исходной сигнатуре типа foldr, поэтому мы должны заменить каждое вхождение state на нее:
foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
-> ([b] -> [(a,b)])
-> [a]
-> ([b] -> [(a,b)])
Это означает, что аргументы, которые мы передаем foldr, должны иметь следующие типы:
step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]
Напомним, что foldr (+) 0 [1,2,3] расширяется до:
1 + (2 + (3 + 0))
Поэтому, если xs = [1,2,3] и ys = [4,5,6,7], наш foldr вызов расширится до:
1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]
Это означает, что наша конструкция 1 `step` (2 `step` (3 `step` done)) должна создать рекурсивную функцию, которая будет проходить через [4,5,6,7] и архивировать элементы. (Имейте в виду, что если один из исходных списков длиннее, лишние значения отбрасываются). Итак, наша конструкция должна иметь тип [b] -> [(a,b)].
3 `step` done - это наш базовый случай, где done - начальное значение, например 0 в foldr (+) 0 [1..3]. Мы не хотим ничего архивировать после 3, потому что 3 является окончательным значением xs, поэтому мы должны прекратить рекурсию. Как прекратить рекурсию по списку в базовом случае? Вы возвращаете пустой список []. Но вспомните done тип подписи:
done :: [b] -> [(a,b)]
Поэтому мы не можем вернуть просто [], мы должны вернуть функцию, которая игнорировала бы все, что она получает. Поэтому используйте const:
done = const [] -- this is equivalent to done = \_ -> []
Теперь давайте начнем выяснять, каким должно быть step. Он объединяет значение типа a с функцией типа [b] -> [(a,b)] и возвращает функцию типа [b] -> [(a,b)].
В 3 `step` done мы знаем, что значение результата, которое позже попадет в наш сжатый список, должно быть (3,6) (зная из оригинальных xs и ys). Поэтому 3 `step` done необходимо оценить в:
\(y:ys) -> (3,y) : done ys
Помните, что мы должны возвращать функцию, внутри которой мы каким-то образом заархивируем элементы. Приведенный выше код имеет смысл и проверки типов.
Теперь, когда мы предположили, как именно step должен оценивать, давайте продолжим оценку. Вот как выглядят все этапы сокращения в нашей оценке foldr:
3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)
Оценка дает начало этой реализации шага (обратите внимание, что мы учитываем ys раннее исчерпание элементов путем возврата пустого списка):
step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys
Таким образом, полная функция zip реализована следующим образом:
zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
where done = const []
step x f [] = []
step x f (y:ys) = (x,y) : f ys
PS: Если вас вдохновляет элегантность сгибов, прочитайте Написание фолдла с использованием foldr , а затем Грэма Хаттона * Учебник об универсальности и выразительности сгиба .