2 replaced http://stackoverflow.com/ with https://stackoverflow.com/
source | link

As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:

take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]

This should be a way of deriving the first 100 Pythagorean triples, with duplicates. In practice however, it never halts, because the algorithm itself defies lazy evaluation.

To think about it in terms of actual implementation, the following should be something similar to how the list comprehension is actually evaluated, in an imperative style:

results = []
for (a = 0; a < ∞; a++) {
  for (b = 0; b < ∞; b++) {
    for (c = 0; c < ∞; c++) {
      if (a^2 + b^2 == c^2) {
        results[] = [a, b, c]
      }
    }    
  }
}

When written like this, it becomes obvious that the function can never yield results, because infinite time will be spent testing whether 1^2 + 1^1 == c^2, as only the innermost for loop will advance, and a and b will remain '1'.

The common solution in this particular case is to constrain the values of the smallest two variables to that of the largest:

take 100 [(a, b, c) | c <- [1..],a <- [1..c], b <- [1..c],a^2 + b^2 == c^2]

However, this seems like an obvious oversight for implementors of the language. When you think about it, any list comprehension with more than one infinite source of search space will never halt, for the same reason, except some will yield useful results when (1, 1, x) is useful. There are questionsquestions discussingdiscussing thisthis problemproblem, but most discuss specific cases, rather than the problem overall. Why isn't fixing this within the language with a different iteration pattern trivial?

As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:

take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]

This should be a way of deriving the first 100 Pythagorean triples, with duplicates. In practice however, it never halts, because the algorithm itself defies lazy evaluation.

To think about it in terms of actual implementation, the following should be something similar to how the list comprehension is actually evaluated, in an imperative style:

results = []
for (a = 0; a < ∞; a++) {
  for (b = 0; b < ∞; b++) {
    for (c = 0; c < ∞; c++) {
      if (a^2 + b^2 == c^2) {
        results[] = [a, b, c]
      }
    }    
  }
}

When written like this, it becomes obvious that the function can never yield results, because infinite time will be spent testing whether 1^2 + 1^1 == c^2, as only the innermost for loop will advance, and a and b will remain '1'.

The common solution in this particular case is to constrain the values of the smallest two variables to that of the largest:

take 100 [(a, b, c) | c <- [1..],a <- [1..c], b <- [1..c],a^2 + b^2 == c^2]

However, this seems like an obvious oversight for implementors of the language. When you think about it, any list comprehension with more than one infinite source of search space will never halt, for the same reason, except some will yield useful results when (1, 1, x) is useful. There are questions discussing this problem, but most discuss specific cases, rather than the problem overall. Why isn't fixing this within the language with a different iteration pattern trivial?

As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:

take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]

This should be a way of deriving the first 100 Pythagorean triples, with duplicates. In practice however, it never halts, because the algorithm itself defies lazy evaluation.

To think about it in terms of actual implementation, the following should be something similar to how the list comprehension is actually evaluated, in an imperative style:

results = []
for (a = 0; a < ∞; a++) {
  for (b = 0; b < ∞; b++) {
    for (c = 0; c < ∞; c++) {
      if (a^2 + b^2 == c^2) {
        results[] = [a, b, c]
      }
    }    
  }
}

When written like this, it becomes obvious that the function can never yield results, because infinite time will be spent testing whether 1^2 + 1^1 == c^2, as only the innermost for loop will advance, and a and b will remain '1'.

The common solution in this particular case is to constrain the values of the smallest two variables to that of the largest:

take 100 [(a, b, c) | c <- [1..],a <- [1..c], b <- [1..c],a^2 + b^2 == c^2]

However, this seems like an obvious oversight for implementors of the language. When you think about it, any list comprehension with more than one infinite source of search space will never halt, for the same reason, except some will yield useful results when (1, 1, x) is useful. There are questions discussing this problem, but most discuss specific cases, rather than the problem overall. Why isn't fixing this within the language with a different iteration pattern trivial?

    Tweeted twitter.com/#!/StackProgrammer/status/643577875346624516
1
source | link

Why don't "multi-infinite" list comprehensions work with lazy evaluation?

As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:

take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]

This should be a way of deriving the first 100 Pythagorean triples, with duplicates. In practice however, it never halts, because the algorithm itself defies lazy evaluation.

To think about it in terms of actual implementation, the following should be something similar to how the list comprehension is actually evaluated, in an imperative style:

results = []
for (a = 0; a < ∞; a++) {
  for (b = 0; b < ∞; b++) {
    for (c = 0; c < ∞; c++) {
      if (a^2 + b^2 == c^2) {
        results[] = [a, b, c]
      }
    }    
  }
}

When written like this, it becomes obvious that the function can never yield results, because infinite time will be spent testing whether 1^2 + 1^1 == c^2, as only the innermost for loop will advance, and a and b will remain '1'.

The common solution in this particular case is to constrain the values of the smallest two variables to that of the largest:

take 100 [(a, b, c) | c <- [1..],a <- [1..c], b <- [1..c],a^2 + b^2 == c^2]

However, this seems like an obvious oversight for implementors of the language. When you think about it, any list comprehension with more than one infinite source of search space will never halt, for the same reason, except some will yield useful results when (1, 1, x) is useful. There are questions discussing this problem, but most discuss specific cases, rather than the problem overall. Why isn't fixing this within the language with a different iteration pattern trivial?