История изменений
Исправление quasimoto, (текущая версия) :
Эта константа очевидно у моего кода как минимум на порядок ниже.
Вот этого не пойму. Одним циклом:
1! = 1
2! = 2
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
3 умножения. Двумя:
1! = 1
2! = 2
3! = 3 * 2
4! = 4 * 3 * 2
5! = 5 * 4 * 3 * 2
6 умножений.
рекурсивными конечно можно, но зачем этот оверхед?
Его быть не должно, поэтому там где делают рекурсивными добавляют ещё TCO.
можно узнать, как тут «линейно» получилось?
Если не считать нижеследующей поправки про умножение для больших чисел не за O(1) (ghc использует gmp)? Абстрактно линейно от входа. Вход же поток - как ещё тут что-то может работать кроме как не линейной его обработкой?
[1..] это ленивый генератор:
nats from = go from where go n = n : go (n + 1)
-- take 10 $ nats 5
-- => [5,6,7,8,9,10,11,12,13,14]
-- ,-----.
-- $@ v |
-- / \ -> : |
-- go n / \ |
-- n $@--^
-- /
-- @
-- / \
-- @ 1
-- / \
-- + n
в энергичном языке такой код бы привёл к зависанию и быстрому поеданию кучи и стека. Ленивый язык работает иначе - там где не хватает явной строгости или анализа строгости он работает на основе редукций таких вот графов и отображению таких редукций на машинные инструкции.
Аналогично scanl это отображение ленивого генератора:
pp z (x:xs) = z : pp (z * x) xs
-- take 10 $ pp 1 $ nats 2
-- => [1,2,6,24,120,720,5040,40320,362880,3628800]
-- ,-----.
-- v |
-- $@ : |
-- / \ / \ |
-- / \ -> z $@--^
-- @ : / \
-- / \ / \ @ xs
-- pp z x xs / \
-- @ x
-- / \
-- * z
mapM_ относится уже к IO, которое должно как-то заставлять ленивый язык работать, и, в конечном итоге, превращается в tail-call алгоритм (то есть как раз цикл) вычерпывающий значения из этого ленивого преобразователя ленивого генератора и печатающий их. В STG это выглядит примерно так:
main3 ... [xs ...]
case xs of _ { -- case
...
y : ys ->
let { -- let
str = showInteger y
} in case hPutStr2 stdout str ... of _ { -- case
... -> main3 ys ... -- TC? yes.
}
}
main2 ...
case main1 of _ {
...
x : xs -> scanl (*) x xs of zs {
... -> main3 zs ...
}
}
main1 ...
enumDeltaInteger 1 1
Исходная версия quasimoto, :
Эта константа очевидно у моего кода как минимум на порядок ниже.
Вот этого не пойму. Одним циклом:
1! = 1
2! = 2
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
3 умножения. Двумя:
1! = 1
2! = 2
3! = 3 * 2
4! = 4 * 3 * 2
5! = 5 * 4 * 3 * 2
6 умножений.
рекурсивными конечно можно, но зачем этот оверхед?
Его быть не должно, поэтому там где делают рекурсивными добавляют ещё TCO.
можно узнать, как тут «линейно» получилось?
Если не считать нижеследующей поправки про умножение для больших чисел не за O(1) (ghc использует gmp)? Абстрактно линейно от входа. Вход же поток - как ещё тут что-то может работать кроме как не линейной его обработкой?
[1..] это ленивый генератор:
nats from = go from where go n = n : go (n + 1)
-- take 10 $ nats 5
-- => [5,6,7,8,9,10,11,12,13,14]
-- ,-----.
-- $@ v |
-- / \ -> : |
-- go n / \ |
-- n $@--^
-- /
-- @
-- / \
-- @ 1
-- / \
-- + n
в энергичном языке такой код бы привёл к зависанию и быстрому поеданию кучи и стека. Ленивый язык работает иначе - там где не хватает явной строгости или анализа строгости он работает на основе редукций таких вот графов и отображению таких редукций на машинные инструкции.
Аналогично scanl это отображение ленивого генератора:
pp z (x:xs) = z : pp (z * x) xs
-- take 10 $ pp 1 $ nats 2
-- => [1,2,6,24,120,720,5040,40320,362880,3628800]
-- ,-----.
-- v |
-- $@ : |
-- / \ / \ |
-- / \ -> z $@--^
-- @ : / \
-- / \ / \ @ xs
-- pp z x xs / \
-- @ x
-- / \
-- * z
mapM_ относится уже к IO, которое должно как-то заставлять ленивый язык работать, и, в конечном итоге, превращается в tail-call алгоритм вычерпывающий значения из этого ленивого преобразователя ленивого генератора и печатающий их. В STG это выглядит примерно так:
main3 ... [xs ...]
case xs of _ { -- case
...
y : ys ->
let { -- let
str = showInteger y
} in case hPutStr2 stdout str ... of _ { -- case
... -> main3 ys ... -- TC? yes.
}
}
main2 ...
case main1 of _ {
...
x : xs -> scanl (*) x xs of zs {
... -> main3 zs ...
}
}
main1 ...
enumDeltaInteger 1 1