История изменений
Исправление quasimoto, (текущая версия) :
Метафорично, это да, зато новичкам понятно
Просто оно порой таки прибывает, но не убывает. Например, если немного обленить Int:
data {- newtype -} A = A {- ! -} Int deriving Show
A x & A y = A $ {- $! -} x + y
main = print $ foldl (&) (A 0) $ take 1000000000 $ let as = A 1 : as in as
то будет — http://i.imgur.com/FYGBue1.png. Вообще ленивость как таковая может создавать сколь угодно большие структуры из санков в памяти, но сам язык не строгий, то есть программы отображаются в семантические домены определённым образом (не так как в строгом языке — можно завязывать узлы и не виснуть, например), а лень — просто один из способов реализации (и не самый лучший, поэтому есть strictness analysis и рассматривалась optimistic evaluation).
И другой пример — левая и правая свёртка по строгому массиву:
data View = Nil | Cons Word8 ByteString
viewL :: ByteString -> View
viewL bs = if B.null bs then Nil else Cons (B.head bs) (B.tail bs)
viewR :: ByteString -> View
viewR bs = if B.null bs then Nil else Cons (B.last bs) (B.init bs)
fold :: (ByteString -> View) -> (t -> Word8 -> t) -> t -> ByteString -> t
fold v f = go where go a bs = case v bs of { Nil -> a; Cons x xs -> go (f a x) xs }
foldL :: (a -> Word8 -> a) -> a -> ByteString -> a
foldL = fold viewL
foldR :: (a -> Word8 -> a) -> a -> ByteString -> a
foldR = fold viewR
никаких украшений, даёт в итоге
M.$wgo_info:
testq %r9,%r9
jle _c22L
movzbl (%rsi,%r8,1),%eax
// ...
// e.g.
// addq %rax,%r14
// for (+)
incq %r8
decq %r9
jmp M.$wgo_info
_c22L:
для левой и
M.$wgo_info:
testq %r9,%r9
jle _c22Y
leaq -1(%r9),%rbx
movq %r8,%rax
addq %rbx,%rax
movzbl (%rsi,%rax,1),%eax
// ...
decq %r9
jmp M.$wgo_info
_c22Y:
для правой. За счёт того, что массив настоящий, head, tail, last и init — O(1), сделаны через простую индексацию и заинлайнены (то есть видны оптимизатору, в отличии от sum), так что в итоге левая и правая свёртки не особо отличаются — два цикла по куску памяти, просто разных сторон, а вся основная разница, собственно, в направлении обхода, как на картинках тут — http://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_as_structural....
А в случае ленивых списков разница уже есть — например, собирать (строгое) скалярное значение, типа sum, _выгодно_ левой свёрткой, строить другую ленивую структуру на основе — правой.
Исходная версия quasimoto, :
Метафорично, это да, зато новичкам понятно
Просто оно порой таки прибывает, но не убывает. Например, если немного обленить Int:
data {- newtype -} A = A {- ! -} Int deriving Show
A x & A y = A $ {- $! -} x + y
main = print $ foldl (&) (A 0) $ take 1000000000 $ let as = A 1 : as in as
то будет — http://i.imgur.com/FYGBue1.png. Вообще ленивость как таковая может создавать сколь угодно большие структуры из санков в памяти, но сам язык не строгий, то есть программы отображаются в семантические домены определённым образом (не так как в строгом языке — можно завязывать узлы и не виснуть, например), а лень — просто один из способов реализации (и не самый лучший, поэтому есть strictness analysis и рассматривалась optimistic evaluation).
И другой пример — левая и правая свёртка по строгому массиву:
data View = Nil | Cons Word8 ByteString
viewL :: ByteString -> View
viewL bs = if B.null bs then Nil else Cons (B.head bs) (B.tail bs)
viewR :: ByteString -> View
viewR bs = if B.null bs then Nil else Cons (B.last bs) (B.init bs)
fold :: (ByteString -> View) -> (t -> Word8 -> t) -> t -> ByteString -> t
fold v f = go where go a bs = case v bs of { Nil -> a; Cons x xs -> go (f a x) xs }
foldL :: (a -> Word8 -> a) -> a -> ByteString -> a
foldL = fold viewL
foldR :: (a -> Word8 -> a) -> a -> ByteString -> a
foldR = fold viewR
никаких украшений, даёт в итоге
M.$wgo_info:
testq %r9,%r9
jle _c22L
movzbl (%rsi,%r8,1),%eax
// ...
// e.g.
// addq %rax,%r14
// for (+)
incq %r8
decq %r9
jmp M.$wgo_info
_c22L:
для левой и
M.$wgo_info:
testq %r9,%r9
jle _c22Y
leaq -1(%r9),%rbx
movq %r8,%rax
// ...
movzbl (%rsi,%rax,1),%eax
addq %rax,%r14
decq %r9
jmp M.$wgo_info
_c22Y:
для правой. За счёт того, что массив настоящий, head, tail, last и init — O(1), сделаны через простую индексацию и заинлайнены (то есть видны оптимизатору, в отличии от sum), так что в итоге левая и правая свёртки не особо отличаются — два цикла по куску памяти, просто разных сторон, а вся основная разница, собственно, в направлении обхода, как на картинках тут — http://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_as_structural....
А в случае ленивых списков разница уже есть — например, собирать (строгое) скалярное значение, типа sum, _выгодно_ левой свёрткой, строить другую ленивую структуру на основе — правой.