Понимание рекурсивных ленивых списков

Question

Я пытаюсь освоиться со следующим фрагментом из Haskell wiki:

primesPE = 2 : oddprimes 
    where 
    oddprimes = sieve [3,5..] 9 oddprimes 
    sieve (x:xs) q ps@ ~(p:t) 
     | x < q  = x : sieve xs q ps 
     | otherwise =  sieve (xs `minus` [q, q+2*p..]) (head t^2) t 

minus (x:xs) (y:ys) = case (compare x y) of 
    LT -> x : minus xs (y:ys) 
    EQ -> minus xs ys 
    GT -> minus (x:xs) ys 
minus xs _ = xs 

Я получаю сработавший на рекурсивном определении oddprimes и использование minus на бесконечных списки по функция, которая делает это рекурсивно.

Я думаю, что частично я смущен, потому что я не понимаю, как компилятор Haskell выполняет этот код. Как он не исчерпывает память? Я подозреваю, что ответ <magic> lazy evaluation </magic>, но я думаю, мне нужно более твердо понять, как это оценивается на практике, чтобы чувствовать себя комфортно.

Answer 1

За кулисами системы Haskell обычно представляют значения в памяти по виду структуры, называемому thunk. Подумайте о стуке как объект, который имеет два состояния:

1. Uncomputed
2. , вычисленный

uncomputed преобразователь содержит указатель на подпрограмму объектного кода, который вычисляет свой результат, и указатель на thunks, которые поставляют значения, необходимые для выполнения этого вычисления. (Если вы столкнулись с концепцией closures, то невыпущенный кусок является закрытием.)

Вычисленный кусок просто содержит исходное значение результата. Основная операция на ударных называется форсирование. Когда вы принудительно выгружаете неузнанный thunk, его подпрограмма вызывается с захваченными аргументами, thunk заменяется вычисленным значением результата (тем самым переключая его состояние на вычисленное), и это значение возвращается. Когда вы заставляете уже вычисленный thunk, вы просто получаете уже вычисленное значение.

Возможно, это проще, если писать в псевдокоде. Я буду делать что-то Java-МОГ:

class Thunk<A> { 
    private final Supplier<A> computation; 
    private boolean computed = false; 
    private A result; 

    Thunk(Supplier<A> computation) { 
     this.computation = computation; 
    } 

    public A force() { 
     if (!computed) { 
      result = computation.get(); 
      computed = true; 
     } 
     return result; 
    } 
} 

Это не совсем нравится то, что то, что я описал выше, но он ведет себя, как он.

Теперь давайте посмотрим на более простом примере, функция, которая строит повторяющийся список из одного элемента:

repeat :: a -> [a] 
repeat a = a : repeat a 

repeat функция компилируется с обработчиком объектного кода, который, в псевдо-коде, может выглядеть что-то вроде этого:

Thunk<List<A>> repeat(Thunk<A> a) { 
    return new Thunk<A>(() -> new Cons<A>(a, repeat(a))); 
} 

class Cons<A> extends List<A> { 
    Thunk<A> head; 
    Thunk<List<A>> tail; 
    // ... 
} 

Если вы не знакомы с Java 8, () -> new Cons<A>(a, repeat(a)) является лямбда.Это функция, которая принимает нулевые аргументы и, когда вызывается, создает пару. Рекурсивный вызов repeat - внутри lambda, поэтому вызов repeat не рекурсивно, он возвращает Thunk, который захватывает лямбду, не выполняя ее сразу. Когда этот thunk будет force d, только , то будет вызываться лямбда, который вызовет repeat, который сразу же вернет другой подобный бит.

В принципе, в Haskell код скомпилируется в оптимизированную низкоуровневую версию этого.

Answer 2

Ответ, действительно, просто ленивая оценка. Haskell ничего не оценивает, даже хвост списка, если он явно не обозначен как строгий, или если это требуется действием IO (и даже сами действия IO могут быть ленивыми, что иногда запутывает)

Так что, если вы оцениваете что-то вроде

head (1 : undefined) 

вы получите 1, несмотря на то, что есть неопределенная там, потому что хвост списка никогда не оценивается.