Бесконечная петля в haskell

Question

Итак, я пишу программу для создания списка простых чисел в haskell. Я создаю две функции, приведенные ниже:

{- 
Given a list of prime numbers, this function will 
add the next prime number to the list. So, given the 
list [2, 3], it will return [2, 3, 5] 
-} 
nextPrime xs = xs ++ [lastVal + nextCounts] 
    where 
     lastVal  = (head . reverse) $ xs 
     isNextPrime y = 0 `elem` (map (y `mod`) xs) 
     nextVals  = (map isNextPrime [lastVal, lastVal+1 ..]) 
     nextCounts = length $ takeWhile (\x -> x) nextVals 


allPrimes xs = allPrimes np 
    where 
     np = nextPrime xs 

Теперь функция nextPrime выполняет то, что она должна делать. Однако, когда я звоню на allPrimes, как показано ниже:

take 5 $ allPrimes [2,3] 

Программа переходит в бесконечный цикл. Я думал, что Haskells «ленивые» функции должны были заботиться обо всем этом? Что мне не хватает?

Answer 1

Если вы начнете оценивать выражение на бумаге, вы можете понять, почему здесь не помогает лень. Начните с выражением:

take 5 $ allPrimes [2,3] 

Во-первых, попытка оценить выражение allPrimes:

allPrimes [2, 3] 

, который становится

allPrimes np 
    where 
     np = nextPrime [2, 3] 

положить вещи из пункта where в выражение и становится

allPrimes (nextPrime [2, 3]) 

Теперь оценить nextPrime [2, 3] (вы можете сделать это в ghci, поскольку эта функция работает) и получить [2, 3, 5], который можно заменить в предыдущем выражении, и она становится

allPrimes [2, 3, 5] 

повторяют выше и становится

allPrimes [2, 3, 5, 7] 

и есть ваша проблема! allPrimes никогда не оценивался до каких-либо значений, он оценивается как allPrimes, применяемый к более длинным и длинным спискам. Для того, чтобы увидеть, где лень делает работу, попытайтесь оценить на бумаге функцию как zip из Prelude:

zip :: [a] -> [b] -> [(a,b)] 
zip (a:as) (b:bs) = (a,b) : zip as bs 

zip [1, 2, 3] ['a', 'b', 'c'] 

a становится 1, as становится [2, 3], b становится 'a', bs становится ['b', 'c'] так что вы получите

(1, 'a') : zip [2, 3] ['b', 'c'] 

Разница здесь в том, что есть список с значением, тогда остальная часть списка является выражение. В вашей функции allPrimes вы просто продолжаете получать больше выражений.

Для получения дополнительной информации, смотрите в Слабое Head нормальной форме однако, если вы новичок в Haskell я рекомендую вам освоиться с синтаксисом и с основами «Мышление в Haskell», прежде чем начать смотреть на вещи, как WHNF.

Answer 2

Я прочитал ответ Дрю хорошее объяснение того, что происходит не так, но для быстрой демонстрации для того, как сделать эту работу,

nextPrime xs = xs ++ [lastVal + nextCounts] 
    where 
    lastVal  = (head . reverse) $ xs 
    isNextPrime y = 0 `elem` (map (y `mod`) xs) 
    --^Style note, this name is super misleading, since it returns 
    -- false when the number is prime :) 
    nextVals  = (map isNextPrime [lastVal, lastVal+1 ..]) 
    nextCounts = length $ takeWhile (\x -> x) nextVals 


allPrimes xs = last np : allPrimes np 
    where np = nextPrime xs 

Теперь мы построения списка, как мы идем, и haskell ленив, поэтому он может захватить последний элемент np перед оценкой allPrimes np. Другими словами, head (a : infiniteLoop) - это a, а не бесконечный цикл.

Однако это действительно неэффективно. Списки объединены в Haskell, поэтому last - O(n), в отличие от O(1) - в чем-то вроде Python. И ++ также является дорогостоящим, O(n) для длины первого списка.

Вместо

nextPrime xs = lastVal + nextCounts 
    where lastVal  = head xs 
     isNextPrime = 0 `elem` map (y `rem`) xs 
     nextVals = map isNextPrime [lastVal ..] 
     nextCount = length $ takeWhile id nextVals 

allPrimes xs = p : allPrimes (p:xs) 
    where p = nextPrime xs 

Таким образом мы сохраняем список обращенного, чтобы избежать этих дорогостоящих обходов. Мы можем также упростить nextPrime

import Data.Maybe 
nextPrime xs = fromJust nextPrime 
    where isPrime y = not $ 0 `elem` map (rem y) xs 
     nextPrime = find isPrime [head xs ..] 

Где мы просто найти список для первого элемента, который является главным и добавить его в наш список. Обычно fromJust плохо, если бы не было следующих простых чисел, мы получили бы ошибку. Но поскольку мы математически знаем, что всегда будет следующий премьер, это безопасно.

В конце концов, код выглядит

import Data.Maybe 
import Data.List 
nextPrime xs = fromJust nextPrime 
    where isPrime y = 0 `notElem` map (rem y) xs 
     nextPrime = find isPrime [head xs ..] 
allPrimes xs = p : allPrimes (p:xs) 
    where p = nextPrime xs 

Чтобы оценить его, вызовите allPrimes [2].

---

Еще чище способ сделать это будет иметь функцию, которая возвращает isPrime ли число простым или нет. А затем просто иметь

allPrimes = filter isPrime [1..] 

Но я оставлю это любопытно читателю.

Answer 3

Как указал Дрю, ваша функция allPrimes не приносит пользы от ленивости, так как у нас никогда не бывает того, что она рассчитывает. Это потому, что список, который мы хотим заглянуть, является аргументом allPrimes, а не возвращаемым значением.

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

Ну, поскольку allPrimes является повторным применением себя снова и снова, нам просто нужна функция, которая предоставляет промежуточные значения. И у нас есть один!

iterate f a == [a, f (f a),...] 

Так с итерацией и nextPrime, мы могли бы построить следующую (довольно странно) функцию:

-- nextPrime renamed as nextPrimeList 
infiniteListofListofPrimes = iterate nextPrimeList [2,3] 
primeN n = (infiniteListofListofPrimes !! n) !! n 
takeN n = take n (infiniteListofListofPrimes !! n) 

Мы генерирующие наши простые числа, но это не выглядит большим. Мы предпочли бы [primes], а не избыточным [[some primes]].

Следующим шагом является построение списка на WHNF:

elem1:elem2:aux 
where aux = newvalue:aux 

Где aux рассчитает новое_значение и оставить все на месте для следующего.

Для этого нужно nextPrime прилипание к генерированию один новый премьер:

nextPrime xs = lastVal + nextCounts 

и найти aux, которые могут построить listOfPrimes навсегда.

Я пришел с этим:

infiniteListofPrimes = 2:3:aux 2 
     where aux n = nextPrime (take n infiniteListofPrimes):(aux (n+1))