3

In other words, can the following be optimized to Just [1..]?

> sequence (map Just [1..])
*** Exception: stack overflow

There is also a more specific example in data61/fp-course where early termination is expected iff an Empty value is present.

seqOptional ::
  List (Optional a)
  -> Optional (List a)
seqOptional =
    foldRight f (Full Nil)
      where
          f Empty _ = Empty
          f _ Empty = Empty
          f (Full a) (Full as) = Full (a :. as)

Why does changing order of the first two patterns make function loop forever as if Empty cannot be ever matched? I vaguely understand that such definition would make f strict in the infinite list, but I don't see what is actually causing this.

Or are these unrelated problems?

Side question: does it matter that stack is exhausted and not heap?

4

2 回答 2

5
于 2018-01-11T16:13:38.193 回答
1

I cannot answer your second question, but can answer your first one.

In theory the compiler can detect and optimize cases like this, but due to the Halting Problem it's impossible for it to detect every instance of this pattern. The best it can do is a bunch of ad-hoc heuristics, and I think it would be more confusing if the termination of your program depended on whether a particular rewrite rule fired or not.

于 2018-01-11T11:00:06.970 回答