Gibt es eine Möglichkeit, unendliche und endliche Listen zu trennen?

Question

Zum Beispiel schreibe ich eine Funktion für Listen und ich mag

Länge Funktion verwenden

foo :: [a] -> Bool 
foo xs = length xs == 100 

Wie kann man diese Funktion mit unendlichen Listen oder nicht verwendet werden, verstehen kann?

Oder sollte ich denke immer über unendliche Listen und verwenden Sie so etwas wie dieses

foo :: [a] -> Bool 
foo xs = length (take 101 xs) == 100 

statt Länge direkt zu verwenden?

Was passiert, wenn Haskell würde FiniteList Art haben, so lang und foo wäre

length :: FiniteList a -> Int 
foo :: FiniteList a -> Bool 

Answer 1

length die gesamte Liste durchläuft, sondern um zu bestimmen, ob eine Liste eine bestimmte Länge hat n Sie nur auf den ersten achten müssen n Elemente.

Ihre Idee, take zu verwenden, funktioniert. Alternativ können Sie eine lengthIs Funktion wie folgt schreiben:

-- assume n >= 0 
lengthIs 0 [] = True 
lengthIs 0 _ = False 
lengthIs n [] = False 
lengthIs n (x:xs) = lengthIs (n-1) xs 

Sie können die gleiche Idee verwenden, um die lengthIsAtLeast und lengthIsAtMost Varianten zu schreiben.

Answer 2

Zum Bearbeiten: Ich antworte hauptsächlich auf die Frage in Ihrem Titel und nicht auf die Besonderheiten Ihres speziellen Beispiels (für die ErikRs Antwort ausgezeichnet ist).

Sehr viele Funktionen (wie length selbst) auf Listen sind nur für endliche Listen sinnvoll. Wenn die Funktion, die Sie schreiben, nur für endliche Listen sinnvoll ist, machen Sie dies in der Dokumentation deutlich (wenn sie nicht offensichtlich ist). Es gibt keine Möglichkeit, die Einschränkung zu erzwingen, da das Halting-Problem nicht lösbar ist. Es gibt einfach keinen Algorithmus, um zu bestimmen, vor der Zeit, ob das Verständnis

takeWhile f [1..] 

(wo f auf ganze Zahlen ein Prädikat ist) eine endliche oder eine unendliche Liste.

Answer 3

ErikR und John Coleman haben bereits beantwortet die wichtigsten Teile Ihrer Frage aber würde Ich mag etwas zusätzlich hinweisen:

Es ist am besten Ihre Funktionen in einer Art und Weise zu schreiben, dass sie einfach hängen nicht über die Endlichkeit oder Unendlichkeit ihrer Eingaben - manchmal ist es unmöglich, aber oft ist es nur eine Frage der Neugestaltung. Anstatt beispielsweise den Durchschnitt der gesamten Liste zu berechnen, können Sie einen laufenden Durchschnitt berechnen, der selbst eine Liste ist. und diese Liste wird selbst unendlich sein, wenn die Eingabeliste unendlich und ansonsten endlich ist.

avg :: [Double] -> [Double] 
avg = drop 1 . scanl f 0.0 . zip [0..] 
    where f avg (n, i) = avg * (dbl n/dbl n') + 
         i   /dbl n'  where n' = n+1 
                 dbl = fromInteger 

, in dem Fall, dass Sie eine unendliche Liste Durchschnitt konnten, nicht seine length nehmen:

*Main> take 10 $ avg [1..] 
[1.0,1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0] 

---

Mit anderen Worten, ist eine Option, wie viel von Ihren Funktionen zu entwerfen, einfach sich nicht um den Unendlichkeitsaspekt kümmern und die (vollständige) Auswertung von Listen und anderen (möglicherweise unendlichen) Datenstrukturen so spät wie möglich in Ihrem Programm verzögern.

Auf diese Weise, denke ich, werden sie auch wiederverwendbar und zusammensetzbar sein - alles mit weniger oder mehr allgemeinen Annahmen über seine Eingaben, neigt dazu, mehr zusammensetzbar zu sein; Umgekehrt neigt alles mit mehr oder mehr spezifischen Annahmen dazu, weniger zusammensetzbar und daher weniger wiederverwendbar zu sein.

Answer 4

Nat s und Faulheit Schlag wieder:

import Data.List 

data Nat = S Nat | Z deriving (Eq) 

instance Num Nat where 
    fromInteger 0 = Z 
    fromInteger n = S (fromInteger (n - 1)) 

    Z + m = m 
    S n + m = S (n + m) 

lazyLength :: [a] -> Nat 
lazyLength = genericLength 

main = do 
    print $ lazyLength [1..] == 100 -- False 
    print $ lazyLength [1..100] == 100 -- True 

Answer 5

Es gibt ein paar verschiedene Möglichkeiten, um eine endliche Liste Typ zu machen. Die erste ist einfach in ihren Stacheln Listen streng zu machen:

data FList a = Nil | Cons a !(FList a) 

Leider ist diese wegwirft alle Effizienzvorteile der Faulheit. Einige davon können stattdessen mithilfe von Länge indizierten Listen zurückgewonnen werden:

{-# LANGUAGE GADTs #-} 
{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE KindSignatures #-} 
{-# LANGUAGE ScopedTypeVariables #-} 
{-# OPTIONS_GHC -fwarn-incomplete-patterns #-} 

data Nat = Z | S Nat deriving (Show, Read, Eq, Ord) 

data Vec :: Nat -> * -> * where 
    Nil :: Vec 'Z a 
    Cons :: a -> Vec n a -> Vec ('S n) a 

instance Functor (Vec n) where 
    fmap _f Nil = Nil 
    fmap f (Cons x xs) = Cons (f x) (fmap f xs) 

data FList :: * -> * where 
    FList :: Vec n a -> FList a 

instance Functor FList where 
    fmap f (FList xs) = FList (fmap f xs) 

fcons :: a -> FList a -> FList a 
fcons x (FList xs) = FList (Cons x xs) 

funcons :: FList a -> Maybe (a, FList a) 
funcons (FList Nil) = Nothing 
funcons (FList (Cons x xs)) = Just (x, FList xs) 

-- Foldable and Traversable instances are straightforward 
-- as well, and in recent GHC versions, Foldable brings 
-- along a definition of length. 

GHC nicht unendlich Arten erlauben, so gibt es keine Möglichkeit, ein unendliches Vec und somit keine Möglichkeit, bauen eine unendliche FList (1) zu bauen. Jedoch kann ein FList etwas träge transformiert und konsumiert werden, mit den damit verbundenen Cache- und Müllsammlungsvorteilen.

(1) Man beachte, dass die Art Systemkräfte fconsstrenge in seinem FList Argumente sein, so dass jeder Versuch, einen Knoten mit FList wird unten heraus zu binden.