Как установить строгость в понимании списка? - PullRequest
Новая
       79

Как установить строгость в понимании списка?

2 голосов
/ 26 июня 2011

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

zipWith' f l1 l2 = [ f e1 e2 | (!e1, !e2) <- zip l1 l2 ]

Любая идея?

IЯ пытался 

zipWith' f l1 l2 = [ e1 `seq` e2 `seq` f e1 e2 | (e1, e2) <- zip l1 l2 ]

, но, к сожалению, это не приводит к оценке WHNF.

Ответы [ 3 ]

6 голосов
/ 26 июня 2011

Вы можете механически переводить шаблоны взрыва в вызовы на seq следующий GHC руководство

Это: 

zipWith' f l1 l2 = [ f e1 e2 | (!e1, !e2) <- zip l1 l2 ]

Становится Слишком ленив: 

zipWith' f l1 l2 =
    [ f e1 e2
    | e <- zip l1 l2
    , let t = case e of (x,y) -> x `seq` y `seq` (x,y)
    , let e1 = fst t
    , let e2 = snd t
    ]

Что более кратко записано как (слишком ленив): 

zipWith' f l1 l2 =
    [ f e1 e2
    | e <- zip l1 l2
    , let (e1,e2) = case e of (x,y) -> x `seq` y `seq` (x,y)
    ]

Хотя я бы написал это как (неправильно, слишком лениво) 

zipWith' f l1 l2 = zipWith (\x y -> uncurry f (k x y)) l1 l2
    where
        k x y = x `seq` y `seq` (x, y)

Вы также можете переместить подсказку строгости в структуру данных: 

data P = P !Integer !Integer

zipWith' f l1 l2 = [ f e1 e2 | P e1 e2 <- zipWith P l1 l2 ]

или как: 

zipWith' f l1 l2 = [ f e1 e2 | (e1, e2) <- zipWith k l1 l2 ]
    where
        k x y = x `seq` y `seq` (x,y)
5 голосов
/ 27 июня 2011

Строгое, что нужно сделать строгим zipWith, - это оценить элементы списка в то время, когда принудительная ячейка принудительно установлена.Ваша функция этого не делает.Просто попробуйте 

main = print $ length $ zipWith' undefined [1..10] [1..100]

Случайность анализа строгости, когда вы используете (+), заставляет его работать.

Функция, которую вы хотите, выглядит примерно так: 

zipW f (x:xs) (y:ys) = let z = f x y in seq z (z : zipW f xs ys)
zipW _ _ _ = []

Вы не можете отделить производство cons-ячейки от производства значения, потому что первое должно форсировать второе.

3 голосов
/ 27 июня 2011

Чтобы объяснить пример оригинального плаката и некоторые из замеченных действий Дона.Используя (>> =) в качестве краткого concatMap, исходный пример преобразуется в: 

zip l1 l2 >>= \(!e1, !e2) -> [f e1 e2]

Второй пример: 

zip l1 l2 >>= \(e1, e2) -> [e1 `seq` e2 `seq` f e1 e2]

Но то, что в первой версии десугаридов фактически приводит к дальнейшемуэто: 

zip l1 l2 >>= \(e1, e2) -> e1 `seq` e2 `seq` [f e1 e2]

e1 и e2 становятся принудительными, когда concat в concatMap сглаживает эти одноэлементные списки, что обеспечивает поведение «заставь меня идти».

Хотя это не то, что нужнообычно считается "строгим" zipWith, это не случайность, что он работает для примера FIBS.

...