क्या अनंत और सीमित सूचियों को अलग करने का कोई तरीका है?

Question

उदाहरण के लिए, मैं सूचियों के लिए कुछ समारोह लिख रहा हूँ और मैं लंबाई समारोह

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

का उपयोग कैसे करें किसी को समझ सकते हैं इस समारोह अनंत सूची के साथ है या नहीं किया जा सकता है करना चाहते हैं?

या मैं हमेशा अनंत सूचियों के बारे में सोचते हैं और इस

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

बजाय लंबाई सीधे का उपयोग करने का

की तरह कुछ का उपयोग करना चाहिए?

क्या Haskell FiniteList प्रकार है, तो होगा, इसलिए लंबाई और foo होगा

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

Answer 1

length पूरी सूची को पार करता है, लेकिन n आप केवल पहली बार में देखने की जरूरत है अगर एक सूची के लिए एक विशेष लंबाई निर्धारित करने के लिए n तत्व।

take का उपयोग करने का आपका विचार काम करेगा।

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

आप एक ही विचार का उपयोग कर सकते lengthIsAtLeast और lengthIsAtMost वेरिएंट लिखने के लिए: वैकल्पिक रूप से आप एक lengthIs समारोह इस तरह लिख सकते हैं।

Answer 2

संपादन पर: मैं आपके विशेष उदाहरण के विनिर्देशों के बजाय अपने शीर्षक में प्रश्न का मुख्य जवाब दे रहा हूं, (जिसके लिए एरिकआर का उत्तर उत्कृष्ट है)।

सूचियों पर केवल बहुत सारे फ़ंक्शन (जैसे length स्वयं) सूचियों पर केवल सीमित सूचियों के लिए समझ में आता है। यदि आप जो फ़ंक्शन लिख रहे हैं वह केवल सीमित सूचियों के लिए समझ में आता है, तो दस्तावेज़ में स्पष्ट करें (यदि यह स्पष्ट नहीं है)। प्रतिबंध लागू करने का कोई तरीका नहीं है क्योंकि हलिंग समस्या असफल है। वहाँ बस जाए या नहीं समझ

takeWhile f [1..] 

(जहां f पूर्णांकों पर एक विधेय है) एक परिमित या एक अनंत सूची का उत्पादन समय से आगे निर्धारित करने के लिए कोई एल्गोरिथ्म है।

Answer 3

ErikR और जॉन कोलमैन पहले से ही अपने प्रश्न के मुख्य भागों जवाब दे दिया है, फिर भी मैं अलावा कुछ का कहना चाहते हैं:

यह एक तरह से अपने कार्यों में लिखने के लिए है कि वे केवल निर्भर नहीं है सबसे अच्छा है उनके इनपुट की समाप्ति या अनंतता पर - कभी-कभी यह असंभव है लेकिन बहुत समय यह सिर्फ फिर से डिजाइन करने का मामला है। उदाहरण के लिए पूरी सूची के औसत की गणना करने के बजाय, आप एक चल रहे औसत की गणना कर सकते हैं, जो स्वयं ही एक सूची है; और इनपुट सूची अनंत होने पर यह सूची असीमित होगी, और अन्यथा सीमित होगी।

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 

जिस स्थिति में आप एक अनंत सूची औसत सकता है, लेने के लिए नहीं होने अपने length:

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

---

दूसरे शब्दों में, एक ही विकल्प आपके कार्यों की के रूप में ज्यादा डिजाइन करने के लिए है करने के लिए बस अनन्त पहलू की परवाह नहीं करते हैं, और सूचियों के पूर्ण (पूर्ण) मूल्यांकन, और अन्य (संभावित रूप से अनंत) डेटा संरचनाओं में देरी करते हैं, जितना संभव हो सके आपके कार्यक्रम में एक चरण के अंत तक।

इस तरह, मैं अनुमान लगा रहा हूं, वे भी अधिक पुन: प्रयोज्य और संगत होंगे - इसके इनपुट के बारे में कम या अधिक सामान्य मान्यताओं के साथ कुछ भी अधिक संगत हो सकता है; इसके विपरीत, अधिक से अधिक विशिष्ट धारणाओं वाला कुछ भी कम कंपोज़ेबल होता है और इसलिए कम पुन: प्रयोज्य होता है।

Answer 4

Nat और फिर से आलस्य हड़ताल:

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

वहाँ एक परिमित सूची प्रकार बनाने के लिए एक जोड़े को विभिन्न तरीके हैं।

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

दुर्भाग्य से, यह फेंक देता है आलस्य के सभी दक्षता लाभ: पहले सूचियों उनके कांटा में सख्त बनाने के लिए बस है। इनमें से कुछ के बजाय लंबाई अनुक्रमित सूची का उपयोग करने से बरामद किया जा सकता है:

{-# 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 अनंत प्रकार की अनुमति नहीं है, इसलिए वहाँ के निर्माण के लिए एक अनंत Vec निर्माण करने के लिए कोई रास्ता नहीं है और इस तरह कोई रास्ता नहीं है एक अनंत FList (1)। हालांकि, FList को कैश और कचरा संग्रहण लाभों के साथ कुछ हद तक आलसी रूप से परिवर्तित और उपभोग किया जा सकता है।

(1) ध्यान दें कि प्रकार प्रणाली बलों fconsसख्त अपने FList बहस में है, इसलिए FList नीचे से बाहर होगा के साथ एक शादी करने का कोई भी प्रयास।