Почему компилятор Мюнстера считает, что сопоставление с образцом в ++ недетерминировано?

Question

Недавно я установил Münster Curry Compiler, чтобы заменить гораздо более медленную PAKCS, которую я использовал. Первым делом я хотел проверить, могу ли я использовать некоторые функции сопоставления с образцом из PAKCS, потому что я знаю, что некоторые реализации (которые приходят на ум, - Ленивец) не поддерживают все сопоставления с образцами, которые допускает PAKCS. Поэтому я написал следующую программу:

import IO

f (a ++ [b]) = a

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

Это работает в PAKCS и печатает Hello, World как и ожидалось, но при компиляции с MCC я получаю ошибку:

Error: cannot duplicate the world

Насколько я понимаю, это означает, что MCC не может соответствовать шаблону ++, но я не понимаю, почему MCC выбирает эту ошибку. cannot duplicate the world обычно означает, что IO зависит от недетерминированного поведения. Это заставляет меня подозревать, что MCC считает, что моя функция f является недетерминированным. Однако, насколько мне известно f является полностью детерминированным.

Что делает MCC, что заставляет его думать, что моя функция недетерминирована?

Мне не нужно знать, как исправить программу, это действительно легко, работает следующее:

import IO

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

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

Мне интересно понять, что делает здесь компилятор, что приводит к его ошибке и как это отличается от того, что делает PAKCS при компиляции кода.

Answer 1

Я ничего точно не знаю в отношении MCC, но PAKCS переводит функциональные паттерны в (сильно) недетерминированное выражение. Наблюдаемое поведение сводится к разному поведению MCC и PAKCS при использовании недетерминированных вычислений в IO. В PAKCS выполняется недетерминированное вычисление, и ошибка времени выполнения возникает, только если выражение вычисляет более одного результата.

То есть, вы можете сделать следующее в PAKCS, не получая ошибку времени выполнения.

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

Однако следующие вычисления приведут к (довольно поздней) ошибке во время выполнения.

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

Я бы предположил, что MCC делает другую (и более разумную;)) проверку в отношении недетерминированных вычислений.

Немного рекламы в конце: я обычно работаю с KiCS2 - есть ли конкретная причина, по которой вы используете MCC?

Изменить: Если вам нравится больше о функциональных шаблонах и их реализации, вам, вероятно, стоит взглянуть на следующую статью.

Декларативное программирование с использованием шаблонов функций