Haskell: Слияние списков, где оно нужно?

Допустим, у нас есть следующее:

l = map f (map g [1..100])

И мы хотим сделать:

head l

Итак, мы получаем:

head (map f (map g [1..100]))

Теперь мы должны получить первый элемент этого mapопределяется примерно так:

map f l = f (head l) : (map f (tail l))

Итак, мы получаем:

f (head (map g [1..100]))

А затем снова применяется:

f (g (head [1..100]))

Что приводит к

f (g 1)

Промежуточные списки не формируются, просто из-за лени.

Верен ли этот анализ? И с такими простыми структурами, как эта:

foldl' ... $ map f1 $ map f2 $ createlist

всегда ли промежуточные списки создан, даже без "слияния списков"? (думаю лень исключить т подшивать банально).


Единственное место, где я вижу причину для хранения списка, это если бы мы это сделали:

l' = [1..100]
l = map f (map g l')

Где мы могли бы захотеть сохранить l', если он используется в другом месте. Однако в приведенном выше случае l'для компилятора должно быть довольно тривиально понять, что быстрее просто пересчитать приведенный выше список, чем сохранить его.

6
задан Don Stewart 8 June 2012 в 12:15
поделиться