Перезапись функции zipWith с помощью использования списка

Question

Я переписал функцию zipWith с помощью рекурсии, и теперь я пытаюсь переписать ее, используя понимание списка. Я столкнулся с несколькими ошибками привязки, и я знаю, что моя вторая строка неверна. Это функция у меня есть, что работает как zipWith с помощью рекурсии:

zipW :: (a -> b -> c) -> [a] -> [b] -> [c] 
zipW _ [] _ = [] 
zipW _ _ [] = [] 
zipW f (x:xs) (y:ys) = f x y : zipW f xs ys 

И это моя попытка переписать его в списке понимание:

zipW2 :: (a -> b -> c) -> [a] -> [b] -> [c] 
zipW2 f xs ys = [f x y | (x, y) <- zipW2 f xs ys] 

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

Answer 1

Вам потребуется Parallel List Comprehensions расширение:

{-# LANGUAGE ParallelListComp #-} 

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c] 
zipWith' f xs ys = [f x y | x <- xs | y <- ys] 

Answer 2

Оригинального zipWith имеет три случая:

1. , когда первый список пуст
2. когда второй список пуст
3. когда ни один список не заполнен

Третий случай рекурсивно вызывает zipWith на хвосты аргументов, что снова анализирует случай.

В вашем определении у вас есть только один случай - понимание списка, поэтому любые рекурсивные вызовы вернутся к этому. И без анализа ситуации, вы могли бы зациклятся здесь:

>>> let myZipWith f xs ys = [ f x y | (x,y) <- myZipWith f xs ys ] 
>>> myZipWith (,) [] [] 
^CInterrupted. 

Кроме того, поскольку вы используете f в рекурсивном вызове, но требуете, чтобы рекурсивные выходного быть парой, вы размещение неявного требования, чтобы произвести f x y пара:

>>> :t myZipWith 
myZipWith :: (t2 -> t3 -> (t2, t3)) -> t -> t1 -> [(t2, t3)] 

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

Вы можете use behzad.nouri's solution of enabling the ParallelListComp language extension:

>>> :set -XParallelListComp 
>>> let myZipWith f xs ys = [ f x y | x <- xs | y <- ys ] 
>>> myZipWith (+) [1,2,4] [0,10,20] 
[1,12,24] 

ParallelListComp делает второй (и более поздние) вертикальные символы трубы (|) в правовой синтаксисе списка понимания, переступая через эти списки параллельно (зип-подобный) с более ранними списками ,

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

>>> let notZipWith f xs ys = [ f x y | x <- xs, y <- ys ] 
>>> notZipWith (+) [1,2,4] [0,10,20] 
[1,11,21,2,12,22,4,14,24] 

Using the ParallelListComp extension is really just syntatical sugar for the original zipWith, так что вы можете рассмотреть это обман.

Вы также можете полагаться только на оригинальном zip:

>>> let myZipWith f xs ys = [ f x y | (x,y) <- zip xs ys ] 
>>> myZipWith (+) [1,2,4] [0,10,20] 
[1,12,24] 

Но поскольку zip определяется как zipWith (,), что, вероятно, обман тоже.

Другим способом вы могли бы пойти, чтобы использовать индексы:

>>> let myZipWith f xs ys = [ f x y | i <- [0..min (length xs) (length ys) - 1], let x = xs !! i, let y = ys !! i ] 
>>> myZipWith (+) [1,2,4] [0,10,20] 
[1,12,24] 

Но это будет чудовищно неэффективно, поскольку !! является операция линейного времени, что делает myZipWith квадратичными, а zipWith линейна:

>>> :set +s 
>>> last $ myZipWith (+) (replicate 10000000 1) (replicate 10000000 2) 
3 
(4.80 secs, 3282337752 bytes) 
>>> last $ zipWith (+) (replicate 10000000 1) (replicate 10000000 2) 
3 
(0.40 secs, 2161935928 bytes) 

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