самоссылка в функции Haskell - PullRequest
Новая
       49

самоссылка в функции Haskell

8 голосов
/ 16 июня 2011

Я изучаю Haskell и следующее выражение на Haskell Wiki действительно озадачил меня: 

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Я не могу понять, почему это работает.

Если я применяю стандартную логику каррирования (zipWith (+)) возвращает функцию, принимает список в качестве аргумента и, в свою очередь, возвращает другую функцию, которая принимает другой список в качестве аргумента и возвращает список (zipWith::(a -> b -> c) -> [a] -> [b] -> [c]). Таким образом, fibs является ссылкой на список (который еще не был оценен), а (tail fibs) является хвостом того же (неоцененного) списка. Когда мы пытаемся оценить (take 10 fibs), первые два элемента привязываются к 0 и 1. Другими словами fibs==[0,1,?,?...] и (tail fibs)==[1,?,?,?]. После завершения первого добавления fibs становится [0,1,0+1,?,..]. Аналогично, после второго добавления получаем [0,1,0+1,1+(0+1),?,?..]

  • Правильна ли моя логика?
  • Есть ли более простой способ объяснить это? (какие-либо идеи от людей, которые знают, что делает компилятор Haskell с этим кодом?) (ссылки и ссылки приветствуются)
  • Это правда, что этот тип кода работает только из-за ленивой оценки?
  • Какие оценки происходят, когда я делаю fibs !! 4?
  • Предполагается ли в этом коде, что zipWith обрабатывает элементы от первого до последнего? (Я думаю, что это не должно, но я не понимаю, почему нет)

РЕДАКТИРОВАТЬ2: Я только что нашел вопрос, заданный выше и хорошо ответил здесь Прошу прощения, если я впустую потратил время

РЕДАКТИРОВАТЬ: здесь более сложный для понимания случай (источник: Project Euler форумы ): 

filterAbort :: (a -> Bool) -> [a] -> [a]
filterAbort p (x:xs) = if p x then x : filterAbort p xs else []

main :: Int
main = primelist !! 10000
         where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ]

Обратите внимание, что all (\y -> x mod y /= 0)... Как ссылка на x здесь НЕ может вызвать бесконечную рекурсию?

1 Ответ

15 голосов
/ 16 июня 2011

Я прослежу оценку для вас: 

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

С: 

> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
> zipWith _ _      _      = []

> tail (_:xs)             =  xs
> tail []                 =  error "tail"

Итак: 

  fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
↪ fibs = 0 : 1 : ((+) 0 1 : zipWith (+) (tail fibs) (tail (tail fibs)))
↪ fibs = 0 : 1 : 1 : ((+) 1 1 : zipWith (+) (tail (tail fibs)) (taii (tail (tail fibs)))))    
↪ fibs = 0 : 1 : 1 : 2 : ((+) 1 2 : zipWith (+) (tail (tail (tail fibs))) (tail (taii (tail (tail fibs))))))
↪ fibs = 0 : 1 : 1 : 2 : 3 : ((+) 2 3 : zipWith (+) (tail (tail (tail (tail fibs)))) (tail (tail (taii (tail (tail fibs)))))))

И т. Д.Так что, если вы внесете в указатель эту структуру, она будет вынуждена выполнять оценку каждого шага, пока индекс не будет найден.

Почему это эффективно?Одно слово: совместное использование .

Когда вычисляется fibs, он увеличивается в куче, записывая значения, которые были на компьютере.Позже обратные ссылки на fibs позволяют повторно использовать все ранее вычисленные значения для fibs.Бесплатная памятка!

Как выглядит этот общий доступ в куче?

enter image description here

Когда вы запрашиваете объект в конце списка, Haskell вычисляетСледующее значение записывает его и перемещает эту собственную ссылку вниз по узлу.

Тот факт, что это прекращается, в значительной степени зависит от лени.

...