Строгий список оценки в GHCi - PullRequest
Новая
       73

Строгий список оценки в GHCi

3 голосов
/ 13 апреля 2020

Рассмотрим программу: 

l = [0..10]
l' = map (+1) [0..10]

Запуск ее с GHCi и ввод :sprint l и :sprint l' покажет, что оба списка не оценены. Однако после запуска length l и length l', а затем снова с использованием sprint: 

l = [0,1,2,3,4,5,6,7,8,9,10]

и 

l' = [_,_,_,_,_,_,_,_,_,_,_]

я провел аналогичные эксперименты и попытался связать переменные со списками в GHCi с let, однако, только в случае l (как указано выше в верхнем уровне программы) список всегда полностью вычисляется.

Однако все эти поведения указывают на функцию оптимизации Мне было интересно, есть ли более сложный ответ (стратегия) «под капотом».

1 Ответ

2 голосов
/ 13 апреля 2020

Элементы исходного списка [0..10] были оценены в обоих случаях. Что осталось без оценки в случае l', так это результаты применения (+1) к элементам списка. Напротив, вот что происходит, если мы отображаем функцию строго : 

GHCi> import Control.Monad
GHCi> l'' = (+1) <$!> [0 :: Integer ..10]
GHCi> :sprint l''
l'' = _
GHCi> length l''
11
GHCi> :sprint l''
l'' = [1,2,3,4,5,6,7,8,9,10,11]

(обратите внимание, что я специализирую целочисленные литералы, так что отсутствие ограничения мономорфизма в GHCi Подсказка не приводит к результатам, отличным от того, что вы получаете при загрузке кода из файла.)

Стоит отметить, что enumFromTo для Integer (то, к чему сводится использование диапазона) , как реализовано base , оценивает элементы, чтобы узнать, когда прекратить их генерирование. То есть не length заставляет элементы списка, как мы надеемся, взглянув на его определение : 

length                  :: [a] -> Int
length xs               = lenAcc xs 0

lenAcc          :: [a] -> Int -> Int
lenAcc []     n = n
lenAcc (_:ys) n = lenAcc ys (n+1)

Чтобы лучше понять, как length ведет себя здесь, мы могли бы попытаться повторить ваш эксперимент со списком, созданным с использованием replicate (который, как и length, не смотрит на элементы) для не полностью оцененного значения: 

GHCi> n = 2 * (7 :: Integer)  -- let-bindings are lazy.
GHCi> :sprint n
n = _
GHCi> l''' = replicate 3 n
GHCi> :sprint l'''
l''' = _
GHCi> length l'''
3
GHCi> :sprint l'''
l''' = [_,_,_]
...