Why does the Münster compiler believe a pattern match across ++ is non-deterministic?

Question

I recently installed the Münster Curry Compiler to replace the much slower PAKCS that I was using. The first thing I wanted to test was whether I could use some of the pattern matching features from PAKCS, because I know some implementations (Sloth is the one that comes to mind) don't support all of the pattern matches that PAKCS allows. So I wrote the following program:

import IO

f (a ++ [b]) = a

main = print $ f $ "Hello, World!"

This works in PAKCS and prints Hello, World as expected, but when compiled with MCC I get the error:

Error: cannot duplicate the world

My understanding is that this means MCC can't pattern match across ++, but I don't understand why MCC chooses this error. cannot duplicate the world typically means that the IO is dependent on non-deterministic behavior. This leads me to suspect that MCC believes that my function f is non-deterministic. However to the best of my knowledge f is completely deterministic.

What is MCC doing that causes it to think that my function is non-deterministic?

I don't need to know how to fix the program, that is really easy, the following works:

import IO

f (a : b @ (_:_)) = a : f b
f [a] = []

main = print $ f $ "Hello, World!"

I'm interested in understanding what the compiler is doing here that causes it to error and how that is different from what PAKCS does when it compiles the code.

Answer 1

I don't know anything for sure with respect to MCC, but PAKCS translates functional patterns into a (highly) non-deterministic expression. The observed behaviour boils down to the different behaviour of MCC and PAKCS when using non-deterministic computations in IO. In PAKCS a non-deterministic computation is evaluated and the run-time error only occurs if the expression evaluates to more than one result.

That is, you can do the following in PAKCS without getting a run-time-error.

REPL> putStrLn ("Hello" ? failed)
"Hello"

However, the following computation will yield a (rather late) run-time error.

REPL> putStrLn ("Hello" ? "Hello")
Hello
Hello
ERROR: non-determinism in I/O actions occurred!

I would guess that the MCC makes a different (and more reasonable ; )) check with respect to non-deterministic computations.

Some advertisement at the end: I usually work with KiCS2 -- is there a specific reason you're using the MCC?

Edit: If you like to more about functional patterns and their implementation, you should probably take a look at the following paper.

Declarative Programming with Function Patterns