Описание тега undecidable-instances
2
ответа
Могу ли я автоматически создавать экземпляры классов типов для функции преобразования без чрезмерных разрешений?
Недавно я задал вопрос об экземпляре, который я создал, генерируя бесконечный цикл во время выполнения, и получил замечательный ответ! Теперь, когда я понимаю, что происходит, у меня есть новый вопрос: могу ли я исправить мою попытку достичь своей п…
24 май '16 в 17:14
1
ответ
GHC завис из-за UndecidableSuperClasses - ожидаемое поведение или ошибка?
Следующий фрагмент кода приводит к зависанию GHC (проверено с помощью 8.6.2 и 8.4.4) во время компиляции: {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE UndecidableSuperClasses #-} …
29 ноя '18 в 20:14
0
ответов
Написание универсального моноида поверх Cofree; неразрешима?
Я пытаюсь написать следующий экземпляр Monoid для Cofree: instance (Monoid a, Monoid (f (Cofree f a))) => Monoid (Cofree f a) where mempty = mempty :< mempty (a :< rest) `mappend` (b :< rest') = (a `mappend` b) :< (rest `mappend` rest…
04 июл '17 в 00:06
0
ответов
Машина Тьюринга для обычных языков
Теорема 5.3 из книги TOC Сипсера о разрешимости Regular_TM = {M | M - машины Тьюринга (TM), а L(M) - обычные языки}. Для достижения противоречия предполагается, что TM R является решающим для Regular_TM, а затем R используется для решения проблемы п…
21 апр '17 в 17:25
3
ответа
Как неразрешимые экземпляры могут фактически повесить компилятор?
К тому времени, когда я впервые прочитал серьезную критику -XUndecidableInstancesЯ уже полностью привык к этому, рассматривая это как простое снятие раздражающего ограничения, которое Haskell98 должен сделать компиляторами проще в реализации. На сам…
20 фев '17 в 23:50
2
ответа
Почему этот код с использованием UndecidableInstances компилируется, а затем генерирует бесконечный цикл времени выполнения?
При написании кода с использованием UndecidableInstances раньше я столкнулся с чем-то очень странным. Мне удалось непреднамеренно создать некоторый код, который проверяет типы, когда я полагал, что это не должно: {-# LANGUAGE FlexibleInstances #-} {…
23 май '16 в 22:37
1
ответ
Разрешимость машины Тьюринга неоднозначных случаев
1) Является ли машина Тьюринга M, которая принимает язык L = {ε}, не принимая запись? С одной стороны, я думаю, что это может быть ложным, потому что пустое слово может быть записью, но с другой, я думаю, что это может быть неразрешимой проблемой. 2…
24 ноя '17 в 14:52
1
ответ
Ограничение класса типов Haskell не может быть разрешено из-за условий Патерсона
Я пытаюсь построить AST с индексированными вложенными аннотациями. Я добавил класс типов для очистки аннотации на верхнем уровне и попытался предоставить экземпляры по умолчанию, которые фактически говорят: "Если вы знаете, как очищать аннотацию сам…
17 авг '18 в 14:32
0
ответов
Как определить полиномиальную сводимость ТМ?
Рассмотрим язык L: L = {⎪M - машина Тьюринга и L(M) ≤p {0^p 1^2p ⎪p > 0}}, где символ "≤p" относится к полиномиальному сокращаемому времени, который из следующего верно относительно вышеуказанного языка? (a) L неразрешима (b) L разрешима (c) L регул…
03 фев '20 в 13:04
0
ответов
Использование AllBF Барби в голове экземпляра без UndecidableInstances
Я бы хотел использовать AllBF из barbies в головке экземпляра, например: import Barbies import Barbies.Constraints class MyClass a where instance (ConstraintsB b, AllBF MyClass f b) => MyClass (Barbie b f) where Это не удается из-за скрытого поли…
29 авг '20 в 05:37
0
ответов
Решает ли система компиляции Glorious Glasgow Haskell наполовину проблему остановки?
title длинный, потому что SO не разрешил "Решает ли GHC наполовину проблему остановки?" по какой-то причине Конечно, не сама проблема остановки, а подзадача конечной памяти. Я играл с метапрограммированием а-ля Typing the Technical Interview и решил…
26 ноя '20 в 04:55
1
ответ
Остановился бы D когда-либо, если бы имитирующий блок принятия решения о остановке H никогда не переставал бы его моделировать?
Остановился бы D когда-либо, если бы имитирующий блок принятия решения о остановке H никогда не переставал бы его моделировать? #define u32 uint32_t int D(u32 P) { if ( H(P, P) ) return 0; return 1; } int main() { H((u32)D, (u32)D); } H симулирует ч…
30 май '21 в 02:04
2
ответа
Транзитивный класс Subset для наборов уровней типов
Я работаю с библиотекой наборов уровней Доминика Орчарда , которая очень внимательно следует его статье . Я столкнулся с ситуацией, когда у меня есть контексты, предоставляющие Subset s t а также Subset t v, и мне нужно, чтобы GHC каким-то образом п…
02 ноя '21 в 16:53
0
ответов
Пример неразрешимости объединения высшего порядка
Не могли бы вы продемонстрировать неразрешимость унификации высшего порядка на одном примере? Например, покажите на одном примере, что унификация в лямбда-исчислении неразрешима.
14 фев '22 в 16:36
1
ответ
Можно ли избежать UndecidableInstances в этом примере?
Я пытаюсь реализовать двоичное дерево как класс типов: class BinaryTree bt where empty :: bt a -> Bool empty = isNothing . root emptyTree :: bt a branch :: a -> bt a -> bt a -> bt a root :: bt a -> Maybe a lbranch :: bt a -> bt a r…
26 июн '23 в 10:29