Haskell сгиб по левому краю без применения ленивых вычислений - PullRequest
Новая
       42

Haskell сгиб по левому краю без применения ленивых вычислений

0 голосов
/ 13 января 2020

Насколько я понимаю, Haskell использует ленивую оценку, которая позволяет оценивать операции, например, с бесконечными списками за конечное время.

В качестве теста я определил следующую функцию 

X Boolean
Y Int

f(X,Y) = (Y == 3) OR X

Следовательно, сложение влево применительно к бесконечному списку целых чисел [1..] с False в качестве начального значения и функцией, определенной выше, должно возвращать True, потому что когда оно достигнет n=3, оценивая f(n==3,False) вернет True, и, следовательно, этот True будет распространяться через функцию.

Я реализовал эту функцию в Haskell код 

myfunc :: Bool -> Int -> Bool
myfunc True _ = True
myfunc _ n
  | (n == 3)  = True
  | otherwise = False

и опробовал ее в cli 

foldl myfunc False [1..]

Команда перестает отвечать на запросы, предполагая, что она выполняет бесконечные вычисления. Почему Haskell не извлекает пользу из ленивой оценки здесь?

1 Ответ

6 голосов
/ 13 января 2020

Потому что foldl всегда должен проходить список аргументов в целом , прежде чем начать сокращать его до конечного результата; и foldl' перебирает список аргументов в целом , сокращая его до конечного результата: 

foldl f z [x1, x2, ..., xn]  ==           foldl f (f z x1) [x2, ..., xn]

foldl' f z [x1, x2, ..., xn]  ==  z `seq` foldl' f (f z x1) [x2, ..., xn]

-- thus,

foldl f z1 [x1, x2, ..., xn]  ==  f (...(f (f z1 x1) x2)...) xn

foldl' f z1 [x1, x2, ..., xn]  ==  z1 `seq` (let z2 = f z1 x1  in
                                    z2 `seq` (let z3 = f z2 x2  in
                                     z3 `seq` (... `seq` (f zn xn)...)))

Вы хотели иметь возможность остановить обход, который выполняется с помощью вправо сворачивание с нестрогой сокращающей функцией: 

present y xs  =  foldr myfunc False xs 
  where
  myfunc x r  =  y == x || r

Поскольку myfunc не является строгим во втором аргументе, foldr myfunc исследует список xs в слева направо порядок, 

foldr myfunc False (x:xs)  =  myfunc x (foldr myfunc False xs)
                           =  y == x || foldr myfunc False xs
...