Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

haskell - How to tell if a list is infinite?

Is there a way to tell if a list in Haskell is infinite? The reason is that I don't want to apply functions such as length to infinite lists.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Applying length to unknown lists is generally a bad idea, both practically due to infinite lists, and conceptually because often it turns out that you don't actually care about the length anyway.

You said in a comment:

I'm very new to Haskell, so now, don't infinite structures make my programs very vulnerable?

Not really. While some of us wish there were better ways to distinguish between necessarily finite and necessarily infinite data, you're always safe when you create, process, and examine lazy structures incrementally. Computing the length is clearly not incremental, but checking to see if the length is above or below some cut-off value is, and very often that's all you wanted to do anyway!

A trivial case is testing for nonempty lists. isNonEmpty xs == length xs > 0 is a bad implementation because it examines an unbounded number of elements, when examining a single one would suffice! Compare this:

isNonEmpty [] = False
isNonEmpty (_:_) = True

Not only is this is safe to apply to an infinite list, it's also much more efficient on finite lists--it takes only constant time, instead of time linear in the length of the list. It's also how the standard library function null is implemented.

To generalize this for length testing relative to a cut-off, you'll obviously need to examine as much of the list as the length you're comparing to. We can do exactly this, and no more, using the standard library function drop:

longerThan :: Int -> [a] -> Bool
longerThan n xs = isNonEmpty $ drop n xs

Given a length n and a (possibly infinite) list xs, this drops the first n elements of xs if they exist, then checks to see if the result is non-empty. Because drop produces the empty list if n is larger than the length of the list, this works correctly for all positive n (alas, there's no non-negative integer type, e.g. natural numbers, in the standard libraries).


The key point here is that it's better in most cases to think of lists as iterative streams, not a simple data structure. When possible you want to do things like transform, accumulate, truncate, etc., and either produce another list as output or examine only a known-finite amount of the list, rather than trying to process the entire list in one go.

If you use this approach, not only will your functions work correctly on finite and infinite lists both, but they'll also benefit more from laziness and GHC's optimizer, and be likely to run faster and use less memory.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...