haskell новичок: как избежать перерасчета детерминированной функции с теми же параметрами?

Question

Я новичок в haskell, поэтому я только начинаю понимать основные понятия.

У меня есть следующие функции, которые преобразуют список отсчетов в функцию дискретной плотности вероятности:

freq2prob l = [ (curr/(sum l))) | curr <- l ] 

К сожалению (sum l) вычисляется для каждого из l элементов, составляющих вычислительная сложность неоправданно высокими.

Каков самый лаконичный, элегантный, «haskellic» способ справиться с этим?

Answer 1

Это просто:

freq2prob l = [ curr/s | let s = sum l, curr <- l ] 

вы можете поставить его вне списка понимания, а также: freq2prob l = let s = sum l in [ curr/s | curr <- l ] (обратите внимание in). Это фактически то же вычисление.

Это происходит потому, что первый, по существу, переведены на

freq2prob :: (Fractional a) => [a] -> [a] 
freq2prob l = [ curr/s | let s = sum l, curr <- l ] 
= do 
    let s = sum l 
    curr <- l 
    return (curr/s) 
= let s=sum l in 
    l >>= (\curr -> [curr/s]) 
    -- concatMap (\curr -> [curr/s]) l 
    -- map (\curr -> curr/s) l 

и второй, очевидно, к тому же коду,

freq2prob l = let s = sum l in [ curr/s | curr <- l ] 
= let s = sum l in 
    do 
    curr <- l 
    return (curr/s) 
= let s=sum l in 
    l >>= (\curr -> [curr/s]) 

Answer 2

Мы можем использовать оператор LET или где положение для этого :

freq2prob l = let s = sum l in 
       [ curr/s | curr <- l ] 

или

freq2prob l = [ curr/s | curr <- l ] 
    where s = sum l 

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

freq2prob l = map (/sum l) l 

sum l в функции разделительного (/sum l) будет только оценивается один раз.

Это связано с тем, что при оценке map f xs компилятор не производит элементарной ошибки при создании нескольких копий функции f для оценки отдельно; это то, что будет указывать на все случаи, когда это необходимо.

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

ghci> sum [2..10000000] 
50000004999999 
(8.31 secs, 1533723640 bytes) 
ghci> sum [2..10000000] 
50000004999999 
(8.58 secs, 1816661888 bytes) 

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

ghci> map (* sum [2..10000000]) [1..10] 
[50000004999999,100000009999998,150000014999997,200000019999996,250000024999995,300000029999994,350000034999993,400000039999992,450000044999991,500000049999990] 
(8.30 secs, 1534499200 bytes) 

Так (в том числе небольшой дисперсии, потребовалось почти точно то же самое время, чтобы умножить десять чисел sum [2..10000000] использованием map чем умножения одного, Умножив десять пар. чисел почти не требуется. Поэтому ghci (интерпретатор, даже оптимизированный компилятор) не вводил несколько копий одного и того же вычисления.

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

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

ghci> map (\x -> sum [x..10000000]) [1..10] 
[50000005000000,50000004999999,50000004999997,50000004999994,50000004999990,50000004999985,50000004999979,50000004999972,50000004999964,50000004999955] 
(77.98 secs, 16796207024 bytes) 

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