Как компилятор Haskell обрабатывает оператор 'where'? - PullRequest
Новая
       23

Как компилятор Haskell обрабатывает оператор 'where'?

3 голосов
/ 27 августа 2010

В следующей функции мне интересно, достаточно ли умен компилятор, чтобы понять, что x останется постоянным, или он вычислит заголовок списка для каждого элемента в списке? (Я использую GHC) 

allSame :: Eq a => [a] -> Bool 
allSame xs = all (==x) xs  where x = head xs

Ответы [ 2 ]

11 голосов
/ 27 августа 2010

Семантика «где» в GHC заключается в том, что для «x» будет выделено одно замыкание, которое будет использоваться всеми пользователями.Будет сгенерировано новое замыкание для функции (== 'x'), и оптимизатор сгенерирует его, так что оно генерируется только один раз за обход.

Чтобы точно увидеть, какой код сгенерирован,проверьте ядро ​​(например, через ghc-core).GHC оптимизирует код так: 

M.allSame a eq xs =
    all
      (let 
         ds =
           case xs of 
             []   -> error "bad head"
             x : _-> x
            in
          \y -> x == y
         ) xs

Если производительность вызывает беспокойство, рассмотрите возможность использования векторов, так как отдельные обходы сливаются, удаляя рекурсию.

0 голосов
/ 27 августа 2010

Я думаю, что Haskell просто оценит то, что нужно: поэтому он ищет x и находит его в where -пункте. Тогда я думаю, что он вычисляет x один раз и делает all.

Если вы хотите проверить это, вы можете написать функцию myall, которая выполняет рекурсию, как в all (==x), но, по сути, просто печатает элемент сравнения. Таким образом, вы увидите, получаете ли вы каждый раз новый аргумент или каждый раз он остается одним и тем же.

Edit:

Вот небольшая функция для проверки этого: myall просто собирает первые аргументы и помещает их в список. 

myall x [] = [x]
myall x xs =  x:(myall x (tail xs))

test xs = myall (x) xs where x = head xs

Если вы позвоните test [1,2,3], вы увидите, что результат равен [1,1,1,1], то есть сначала x оценивается как 1, после этого myall оценивается.

...