Инвертирование члена в Curry (PAKCS) не дает ответов

С этим определением:

member _ [] = False
member x (h:t) = if x == h then True else member x t

PAKCS 2.0.1 (из Ubuntu 18.04) не дает ответов, предупреждений или ошибок:

    Top-level binding with no type signature:
      member :: Prelude.Eq a => a -> [a] -> Prelude.Bool
member> member x [1, 2, 3] =:= True where x free
member> 

Я ожидал увидеть 3 значения. Что я здесь делаю неправильно?


person bobcat    schedule 18.12.2020    source источник
comment
Реализация member с унифицирующим =:= вместо не унифицирующего == была бы неправильной: для оценки терма if then else сначала нужно было бы оценить x =:= h путем поиска решения. Если он успешно объединяет x с h, этот термин имеет значение (всегда True), и оценка переходит к if then else. В противном случае, если решений нет, то и все выражение (вся функция) не имеет решений. Часть else никогда не будет оцениваться и давать результат.   -  person imz -- Ivan Zakharyaschev    schedule 29.12.2020


Ответы (2)


Программа ‹smap.informatik.uni-kiel.de/smap.cgi?75› дает только одно решение, так как правило

member x (h:t) = if x =:= h then True else member x t

объединяет x с первым элементом списка и дает True и ничего больше. Обратите внимание, что (=:=) является ограничением унификации, а не логическим тестом. Это означает, что x =:= 1 связывает x с 1 (чтобы удовлетворить ограничение) и дает True, но никогда False. Следовательно, 2 =:= 1 просто терпит неудачу, а не дает False. С другой стороны, 2 == 1 дает False. Таким образом, вы можете ожидать, что x == 1 связывает x с 1, давая True, или связывает x с 2, 3, 4,... давая False. На самом деле это имеет место в реализации Curry KiCS2, но PAKCS для по какой-то причине более ограниченным, так что он останавливается на этом выражении.

Еще одно замечание: (=:=) можно рассматривать как оптимизацию (==), которую можно использовать в том случае, когда требуется только результат True, например, в условиях правил. Поэтому более новая реализация PAKCS автоматически преобразует (==) в (=:=) в таких случаях, чтобы в исходных программах можно было использовать только (==). Дополнительную информацию можно найти в этой статье.

person Michael Hanus    schedule 20.01.2021

Кажется, что в языке программирования Curry == не является функцией, которая может объединять неопределенные значения.

Провожу некоторые эксперименты с другой реализацией Curry, которая случайно была установлена ​​в моей системе (curry-0.9.12-alt1.dev20141223.x86_64):

Prelude> (x == 'a') =:= True where x free
Suspended
Prelude> let match_a 'a' = True in match_a x =:= True where x free
{x = 'a'}
Prelude> 
person imz -- Ivan Zakharyaschev    schedule 28.12.2020
comment
Если я заменю == на =:= в определении member, то получу 1 ответ (2 по-прежнему отсутствуют) - person bobcat; 29.12.2020
comment
@MaxB Лучше покажите свой код с =:=, потому что его тип возвращаемого значения не Bool, поэтому == и =:= не взаимозаменяемы. У меня работает так: Prelude> let memberConstr x (h:t) = (x =:= h) ? memberConstr x t in memberConstr x [1, 2, 3] where x free дает: {x = 1} More solutions? [Y(es)/n(o)/a(ll)] a {x = 2} {x = 3} Prelude> - person imz -- Ivan Zakharyaschev; 29.12.2020
comment
Буквально 1 символ отличается от кода в Q. :t member дает мне member :: a -> [a] -> Bool. Когда я набираю вашу строку (из комментария выше), я получаю все 3 ответа сразу. Это может быть разница в версиях/реализациях. Вы не используете pakcs? - person bobcat; 29.12.2020
comment
@MaxB Нет, я провел свои тесты в другой реализации (написанной на C, известной под названием Muenster Curry), которая в моем случае также довольно старая. Я попробую вашу разницу в 1 символ и посмотрю, но я ожидаю, что типы не будут совпадать. Возможно, спецификации Curry изменились с тех пор, так что =:= в наше время имеет другой тип. Что показывает :t (=:=) для вас? Мой: Prelude> :t (=:=) _1 -> _1 -> Success Возможно, вместо Success он полиморфен в вашем PAKCS. - person imz -- Ivan Zakharyaschev; 29.12.2020
comment
@MaxB Да, в моем случае: Term: x =:= h Inferred type: Success Expected type: Bool Types Bool and Success are incompatible - person imz -- Ivan Zakharyaschev; 29.12.2020
comment
@MaxB Может быть опция PAKCS во время выполнения для отображения всех решений ... И по умолчанию вы можете видеть только первое решение. - person imz -- Ivan Zakharyaschev; 29.12.2020
comment
PAKCS имеет классы типов. Я думаю, что это то, что отличается. Выход: (=:=) :: a -> a -> Bool и (==) :: Eq a => a -> a -> Bool - person bobcat; 29.12.2020
comment
Вы также можете использовать Curry онлайн: smap.informatik.uni-kiel.de (используйте меню вверху страницы) - person bobcat; 29.12.2020
comment
@MaxB Да, в SmapIE есть такая опция: PAKCS 2.2.0 /all-values - person imz -- Ivan Zakharyaschev; 29.12.2020
comment
По какой-то причине (пока мне непонятной) моя программа с memberConstr выдает все 3 решения ‹smap.informatik.uni-kiel.de/smap.cgi?76› в PAKCS 2.2.0 /all-solutions, но ваш ‹smap.informatik.uni-kiel.de/smap.cgi?75› только один... - person imz -- Ivan Zakharyaschev; 29.12.2020