где пункты в списке понятий

Question

В чем разница между двумя следующими формулами?

cp [] = [[]] 
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss] 
---------------------------------------------- 
cp [] = [[]] 
cp (xs:xss) = [x:ys | x <- xs, ys <- yss] 
       where yss = cp xss 

Пример вывод: cp [[1,2,3],[4,5]] => [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]

В соответствии с мышления Функционально С Haskell (стр. 92), вторая версия «более эффективным определение ... [который] гарантирует, что ф X вычисляется только один раз ", хотя автор никогда не объясняет, почему. Я бы подумал, что они эквивалентны.

Answer 1

Эти два определения эквивалентны в том смысле, что они обозначают одно и то же значение, конечно.

Оперативно они отличаются поведением совместного использования при оценке по требованию. jcast уже объяснил почему, но я хочу добавить ярлык, который не требует явно обесцвечивания понимания списка. Правило: любое синтаксическое выражение в позиции, где оно может зависеть от переменной x, будет пересчитываться каждый раз, когда переменная x привязана к значению, даже если выражение фактически не зависит от x.

В вашем случае, в первом определении, x находится в области видимости в том месте, где появляется cp xss, поэтому cp xss будет повторно оценен для каждого элемента x из xs. Во втором определении cp xss появляется за пределами x, поэтому он будет вычислен только один раз.

Тогда обычные отказы применять, а именно:

• компилятор не обязан придерживаться операционной семантики вызова по необходимости оценки, только денотационной семантики. Таким образом, он может вычислять вещи в несколько раз (плавающие) или больше раз (плавающие), чем вы ожидали бы, основываясь на приведенном выше правиле.

• Это не так, что лучше использовать общий доступ. В этом случае, например, это, вероятно, не лучше, потому что размер cp xss растет так же быстро, как объем работы, который он потратил, чтобы вычислить его в первую очередь. В этой ситуации стоимость чтения значения из памяти может превышать стоимость пересчета значения (из-за иерархии кеша и GC).

Answer 2

Ну, наивная де-обсахаривания будет:

cp [] = [[]] 
cp (xs:xss) = concatMap (\x -> concatMap (\ ys -> [ x:ys ]) (cp xss)) xs 
---------------------------------------------- 
cp [] = [[]] 
cp (xs:xss) = let yss = cp xss in concatMap (\x -> concatMap (\ ys -> [ x:ys ]) yss) xs 

Как вы можете видеть, в первом варианте вызова cp xss находится внутри лямбда. Если оптимизатор не перемещает его, это означает, что он будет подвергаться повторной оценке каждый раз, когда вызывается функция \x -> concatMap (\ ys -> [ x:ys ]) (cp xss). Сбрасывая его, мы избегаем повторного вычисления.

В то же время GHC имеет пропуск оптимизации, чтобы плавать дорогостоящие вычисления из таких циклов, поэтому он может автоматически конвертировать первую версию во вторую. В вашей книге говорится, что вторая версия «гарантирует» для вычисления значения cp xss только один раз, потому что, если выражение дорогостоящее для вычисления, компиляторы, как правило, очень колеблются, чтобы встроить его (преобразование второй версии обратно в первую).