Стратегия оценки

Ответ 1

С расширениями языка мы можем создавать ситуации, когда f x необходимо оцениваться повторно:

{-# LANGUAGE GADTs, Rank2Types #-}
module MultiEvG where

data BI where
    B :: (Bounded b, Integral b) => b -> BI

foo :: [BI] -> [Integer]
foo xs = let f :: (Integral c, Bounded c) => c -> c
             f x = maxBound - x
             g :: (forall a. (Integral a, Bounded a) => a) -> BI -> Integer
             g m (B y) = toInteger (m + y)
             x :: (Integral i) => i
             x = 3
         in map (g (f x)) xs

Суть состоит в том, чтобы иметь f x полиморфный даже в качестве аргумента g, и мы должны создать ситуацию, когда тип (ы), в котором он нужен, не может быть предсказан (мой первый удар использовал Either a b вместо BI, но при оптимизации это, конечно, привело только к двум оценкам f x не более).

Полиморфное выражение должно оцениваться по крайней мере один раз для каждого типа, в котором он используется. Это одна из причин ограничения мономорфизма. Однако, когда диапазон типов, в котором он может понадобиться, ограничен, возможно запоминать значения для каждого типа, и в некоторых случаях GHC делает это (требуется оптимизация, и я ожидаю, что количество типов не должно быть слишком большой). Здесь мы сталкиваемся с тем, что является в основном неоднородным списком, поэтому в каждом вызове g (f x) он может понадобиться для произвольного типа, удовлетворяющего ограничениям, поэтому вычисление не может быть снято вне map (технически компилятор мог бы по-прежнему создавайте кеш значений по каждому используемому типу, поэтому он будет оцениваться только один раз для каждого типа, но GHC не имеет, по всей вероятности, это не стоило бы проблем).

• Мономорфные выражения нужно оценивать только один раз, их можно разделить. Независимо от того, выполняются ли они до реализации; по чистоте, это не изменяет семантику программы. Если выражение привязано к имени, на практике вы можете полагаться на его совместное использование, поскольку это легко и очевидно, что хочет программист. Если он не связан с именем, это вопрос оптимизации. С генератором байткода или без оптимизаций выражение часто будет оцениваться повторно, но при повторной оценке оптимизации будет указывать на ошибку компилятора.
• Полиморфные выражения должны оцениваться по крайней мере один раз для каждого типа, в котором они используются, но с оптимизацией, когда GHC может видеть, что он может использоваться несколько раз в одном типе, он будет (обычно) по-прежнему использоваться для этого типа при более широком вычислении.

Нижняя строка: всегда скомпилируйте с оптимизацией, помогите компилятору путем привязки выражений, которые вы хотите использовать для имени, и дайте мономорфные сигнатуры типов, где это возможно.

Ответ 2

Ваши примеры действительно совсем разные.

В первом примере аргумент для сопоставления g (f x) и передается один раз в map, скорее всего, как частично примененная функция. Если g (f x), когда применяется к аргументу внутри map, оценивается его первый аргумент, то это будет сделано только один раз, а затем thunk (f x) будет обновлен с результатом.

Следовательно, в вашем первом примере f x будет оцениваться не более 1 раза.

Второй пример требует более глубокого анализа, прежде чем компилятор сможет прийти к выводу, что (f x) всегда является константой в выражении лямбда. Возможно, он никогда не будет оптимизировать его вообще, потому что он может знать, что след не совсем кошерный. Таким образом, это может оцениваться 4 раза при трассировке и 4 раза или 1 раз, когда не отслеживается.

Ответ 3

Это действительно зависит от оптимизации GHC, как вы могли сказать.

Самое лучшее, что нужно сделать, это изучить ядро ​​GHC, которое вы получите после оптимизации программы. Я бы посмотрел на сгенерированное ядро ​​и выяснил, имел ли f x свой собственный оператор let вне map или нет.

Если вы хотите быть уверенным, вы должны включить f x в свою собственную переменную, назначенную в let, но на самом деле нет гарантированного способа понять это, кроме чтения через Core.

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

Ответ 4

В GHC без оптимизации тело функции оценивается каждый раз, когда вызывается функция. ( "Вызов" означает, что функция применяется к аргументам и результат оценивается.) В следующем примере f x находится внутри функции, поэтому он будет выполняться каждый раз при вызове функции. (GHC может оптимизировать это выражение, как описано в FAQ [1].)

let f x = trace "!" $ zip x x
    x = "abc"
in map (\i -> lookup i (f x)) "abcd" 

Однако, если мы переместим f x из функции, он будет выполняться только один раз.

let f x = trace "!" $ zip x x
    x = "abc"
in map ((\f_x i -> lookup i f_x) (f x)) "abcd" 

Это можно более легко переписать как

let f x = trace "!" $ zip x x
    x = "abc"
    g f_x i = lookup i f_x
in map (g (f x)) "abcd" 

Общее правило заключается в том, что каждый раз, когда к аргументу применяется функция, создается новая "копия" тела функции. Функция-приложение - единственное, что может вызвать повторное выполнение выражения. Однако следует предупредить, что некоторые функции и вызовы функций не похожи на функции синтаксически.

[1] http://www.haskell.org/haskellwiki/GHC/FAQ#Subexpression_Elimination