Finite comprehension of an infinite list

by

But since a human can prove that the sequence terminates at 4, might there be a way to get the interpreter to do it?

In this simple case, yes. But there cannot exist a general algorithm to determine if an expression is true or false for all natural numbers >n for some n, because Haskell is Turing-complete, so it’s impossible to prove that an expression even represents a terminating program for all natural numbers.

Even if your expression were limited to basic integer arithmetic, its truth would still be undecidable in the general case.

Could this be rewritten in such a way that it does terminate?

As Mog wrote in the comment, it’s takeWhile (< 5) [1..].

More Related Contents:

  1. How to run a for loop in Haskell
  2. What is a monad?
  3. Getting started with Haskell
  4. How is this fibonacci-function memoized?
  5. runST and function composition
  6. Explain this chunk of haskell code that outputs a stream of primes
  7. How to create a polyvariadic haskell function?
  8. What does (f .) . g mean in Haskell?
  9. foldl versus foldr behavior with infinite lists
  10. What is the purpose of Rank2Types?
  11. Why does length return 1 for a tuple with 2 elements, and gives an error for a tuple with more elements?
  12. Are there pronounceable names for common Haskell operators? [closed]
  13. How do functors work in haskell?
  14. Split a number into its digits with Haskell
  15. What indentation is required for a case statement within a let statement?
  16. What is the difference between Int and Integer?
  17. Is Haskell truly pure (is any language that deals with input and output outside the system)?
  18. Euler 43 – is there a monad to help write this list comprehension?
  19. Is there a way to place some impure code inside pure functions?
  20. How to increment a variable in functional programming?
  21. What part of Hindley-Milner do you not understand?
  22. Why is GHC complaining about non-exhaustive patterns?
  23. foldl Implementation with Runtime Errors
  24. Exception handling in Haskell
  25. How to make a type with restrictions
  26. Given a Haskell type signature, is it possible to generate the code automatically?
  27. Haskell: why the convention to name a helper function “go”?
  28. Why does OCaml sometimes require eta expansion?
  29. Explanation of “tying the knot”
  30. Return specific type within Haskell

Leave a Comment