ленивая оценка в бесконечном списке - PullRequest
Новая
       10

ленивая оценка в бесконечном списке

0 голосов
/ 23 января 2019

Привет, у меня есть следующий код: 

let f n (xs) = if n < 0 then f (n-1) (n:xs) else xs
f (-3) [] !! 1

и я ожидаю, что он напечатает -4

Но он ничего не печатает и сохраняет расчет в фоновом режиме.

Что не так с моим кодом?

Ответы [ 2 ]

0 голосов
/ 23 января 2019

Итак, вот притворный целочисленный тип: 

data Int2 = ... -- 2 bit signed integers [-2, -1, 0, 1]
  deriving (Num, Ord, Eq, ...)

Давайте представим, что ваша функция была определена на Int2 значениях: 

f :: Int2 -> [Int2] -> [Int2]
f n (xs) = if n < 0 then f (n-1) (n:xs) else xs

Это позволяет довольно легко определить, как выглядит один шаг оценки для f n xs: 

f 1 xs = xs
f 0 xs = xs
f (-1) xs = f (-2) (-1 : xs)
f (-2) xs = f 1 (-2 : xs) -- because finite signed arithmetic wraps around

и оттуда мы можем вычислить полное значение f n []: 

f 1 [] = []
f 0 [] = []
f (-1) [] = f (-2) [-1] = f 1 [-2, -1] = [-2, -1]
f (-2) [] = f 1 [-2] = [-2]

Каждый вычислял значение, но обратите внимание, что потребовалось 3 шага оценки, прежде чем мы получили список из f (-1) [].

Теперь посмотрим, сможете ли вы определить, сколько шагов потребуется для вычисления f (-1) [], если он определен для 4-битных чисел. 8-бит? 32-битный? 64-битный? Что если бы он использовал Integer, который имеет без нижней границы?

Лень ни в коем случае не поможет вам, потому что нет частичного результата, только рекурсивный вызов. В этом разница между: 

lazyReplicate 0 _ = []
lazyReplicate n x = x : lazyReplicate (n - 1) x

и 

strictReplicate n x = helper [] n x where
  helper xs 0 _ = xs
  helper xs n x = helper (x : xs) n x
0 голосов
/ 23 января 2019

Давайте пройдемся по оценке: 

f (-3) []
f (-4) [-3]
f (-5) [-4, -3]
f (-6) [-5, -4, -3]
f (-7) [-6, -5, -4, -3]
...

Учитывая это, что вы ожидаете от f (-3) [] !! 1?Значение в индексе 1 меняет каждую итерацию, поэтому Haskell не может знать, что это такое, пока не достигнет нерекурсивного случая в n >= 0, что никогда не произойдет.

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

let f n = if n < 0 then n : f (n - 1) else []

> f (-3) !! 1
-4
...