Funzione Haskell per verificare se Int è quadrato perfetto usando la lista infinita

Question

Puramente per piacere e pratica, sto provando a scrivere una semplice funzione Haskell per determinare se un numero intero è un quadrato perfetto. Ora so che ci sono altre soluzioni là fuori, ma mi chiedo se c'è un modo per farlo con una lista infinita. Ho iniziato con questo, ma per ragioni evidenti, non funziona (non si ferma mai!)

isSquare :: Integer -> Bool 
    isSquare n = sum[ 1 | x <- [1..], x*x == n] /= 0 

Inoltre, se mi permetto di aggiungere, qualcuno può notare come cercare una lista infinita per la prima istanza di qualcosa e poi STOP! ?

Answer 1

Circa la funzione di ricerca infinita:

C'è già una funzione che cerca una lista per un valore - elem.

Se si presuppone che l'elenco infinito è ordinato, potremmo scrivere una versione di elem che funziona su tale elenco. Questo può essere facilmente eseguito rifiutando innanzitutto qualsiasi elemento inferiore al valore di ricerca. Il primo valore non rifiutato deve essere uguale o maggiore dell'elemento di ricerca. Se uguale - restituire true, altrimenti return false utilizzo

infiniteElem1 :: (Ord a) => a -> [a] -> Bool 
infiniteElem1 x list = (== x) $ head $ dropWhile (< x) list 

Esempio:

> infiniteElem1 10 [1..] 
True 
> infiniteElem1 10 [1,3..] 
False 

C'è un problema anche se con infiniteElem1 però: Se utilizzato in un elenco finito, può generare un'eccezione se l'elemento non è stato trovato:

> infiniteElem1 100 [1,2,3] 
*** Exception: Prelude.head: empty list 

Questa è una ragione per la funzione head è meglio evitare.Una soluzione migliore è questa:

infiniteElem :: (Ord a) => a -> [a] -> Bool 
infiniteElem x list = case dropWhile (< x) list of 
    [] -> False 
    (v:_) -> v == x 

Ora funziona con un elenco ordinato finita così:

> infiniteElem 100 [1,2,3] 
False 

Con questo il problema diventa banale:

let isSquare n = n `infiniteElem` [ x * x | x <- [1..]] 

Answer 2

Sfortunatamente, l'utilizzo di Somma su una lista infinita non funzionerà. In particolare, come fai a sapere che ogni elemento futuro della lista sarà pari a zero? Non è possibile, quindi è necessario ottenere l'intera lista prima di calcolare la somma. Per una lista infinita, questo può richiedere un po 'di tempo.

Se si vuole veramente usare una lista infinita - gli elenchi infiniti sono divertenti, dopotutto - Suggerisco di costruire una lista infinita di numeri quadrati. Quindi verificare se n si trova in quell'elenco. Devi essere un po 'furbo su come lo fai per assicurarti che termini, ma lo lascerò come esercizio al lettore. (Amico, mi piace quella frase: P.)

È possibile trovare qualcosa da una lista infinita utilizzando una funzione come, prevedibile, find. Questo si fermerà non appena troverà qualcosa. Tuttavia, se non trova l'elemento, non si fermerà mai. Questo potrebbe non essere il comportamento che desideri. Non esiste un modo generale per aggirare questo problema, ma è possibile capire come risolverlo per qualsiasi problema particolare: ad esempio, se l'elenco è ordinato in ordine crescente, è possibile eseguire takeWhile (< limit) dove limit è il limite superiore della risposta possibile.

Answer 3

È possibile utilizzare takeWhile o dropWhile. Per esempio:

isSquare n = head (dropWhile (< n) squares) == n 
    where squares = [x*x | x <- [0..]] 

Answer 4

let isSquare n = elem n (takeWhile (<=n) [ x*x | x <- [1..]]) 
ghci> isSquare 25 
True 
ghci> isSquare 28 
False 

Answer 5

Solo per divertimento, ecco un'altra versione lista infinita:

isSquare n = isSquare' [1..] where 
    isSquare' infiniteList@(x:xs) 
    | x*x == n = True 
    | x*x > n = False 
    | otherwise = isSquare' xs