Почему карта не требует строгости, а zipWith делает?

Есть две строгие версии функции zipWith:

1) Действительно строго, элементы списков 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)

2) Не очень строгий, попытка заставить оценку другим способом.

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

Вопрос: почему эквивалентный код из 2-го примера с использованием map не делает функцию еще и строгой?


lazy-evaluation haskell strictness
person David Unric    schedule 28.06.2011    source источник
comment
Функция zipWith' заставит преобразовать любой элемент в l1 и l2 по мере обработки элементов, но преобразователь f e1 e2 не будет принудительно выполнен.   -  person augustss    schedule 28.06.2011

Ответы (2)


arrow_upward
15
arrow_downward

Распространенной ошибкой является использование

x `seq` x

Что точно эквивалентно

x

Отличное объяснение можно найти в сообщении Нила Митчелла о плохой строгости.

person jaspervdj    schedule 28.06.2011
comment
Интересно, но не соответствует тому, почему следующие версии не эквивалентны: zipWith''' f l1 l2 = [ f e1 e2 | (e1, e2) ‹- zip (sLst l1) (sLst l2) ] где sLst [] = [] sLst (x:xs) = x seq x : sLst xs и zipWith''' f l1 l2 = [ f e1 e2 | (e1, e2) ‹- zip (sLst l1) (sLst l2) ] где sLst [] = [] sLst (x:xs) = x : sLst xs - person David Unric; 28.06.2011
comment
Рекурсивное построение списка с x seq x : sLst xs делает его строгим, тогда как эквивалентный x : sLst xs не делает... - person David Unric; 28.06.2011
comment
Это не эквивалентно. Первая версия, которую вы написали, это seq x (x : sLst xs). Помните об ассоциативности. - person jaspervdj; 28.06.2011
comment
Забудьте об этом, моя ошибка из-за приоритета функций. Предыдущее выражение без скобок действительно означало x seq (x : sLst xs). - person David Unric; 28.06.2011

arrow_upward
3
arrow_downward

Вместо тавтологической map можно использовать эту функцию для форсирования списка:

evl []     = []
evl (x:xs) = x `seq` (x:evl xs)
-- Cannot figure out how to do this with fold.

Тогда строгое zipWith равно

zipWith''' f xs ys = zipWith f (evl xs) (evl ys)
person n. 1.8e9-where's-my-share m.    schedule 28.06.2011
comment
Это не будет работать для бесконечных списков, в отличие от версии Дона. - person jaspervdj; 28.06.2011
comment
Некоторое объяснение для таких новичков, как я, почему решение nm не работает для бесконечных списков? - person David Unric; 28.06.2011
comment
@jaspervdj: Кажется, он работает и с бесконечными списками (он заставляет элементы, а не корешок). - person n. 1.8e9-where's-my-share m.; 28.06.2011